Data Structures Flashcards
Think of the definition and time/space complexity (for access, search, insertion/deletion)
Array ( Java )
Definition:
A contiguous block of memory storing elements of the same type, enabling random access by index.
- Access: O(1)
- Search: O(n)
- Insertion/Deletion: O(n) (in the worst case)
- Space: O(n) (fixed size).
Dynamic Array (e.g., Python list)
Definition:
A resizable array that automatically reallocates memory when capacity is exceeded.
- Access: O(1) amortized
- Search: O(n)
- Insertion (append): O(1) amortized, can be O(n) worst case
- Space: O(n).
Singly Linked List
Definition:
Each node stores data and a pointer to the next node.
- Access/Search: O(n)
- Insertion/Deletion at head: O(1)
- Space: O(n).
Doubly Linked List
Definition:
Each node stores pointers to both its next and previous nodes.
- Access/Search: O(n)
- Insertion/Deletion given a node reference: O(1)
- Space: O(n).
Stack
Definition:
A LIFO (Last In, First Out) structure supporting push and pop at one end.
- Push/Pop/Peek: O(1)
- Space: O(n)
- Commonly used for function calls, undo operations, expression parsing.
Queue
Definition:
A FIFO (First In, First Out) structure supporting enqueue (add) at one end and dequeue (remove) at the other.
- Enqueue/Dequeue: O(1)
- Space: O(n).
Hash Table
Definition:
Binary Search Tree (BST)
Definition:
Heap (Min-Heap/Max-Heap)
Definition:
A complete binary tree that satisfies the heap property (parent < children in a min-heap).
- Peek (min/max): O(1)
- Insert/Remove: O(log n)
- Space: O(n)
- Often used in priority queues.
Trie
Definition:
A prefix tree that stores strings character by character in nodes.
- Insert/Search/Delete: O(k), where k is the string length
- Space: O(n * k) in worst case
- Used in auto-completion, spell-checking, IP routing.
Red-Black Tree
Definition:
A generalization of BST where each node can have multiple children, commonly used in databases/filesystems.
- Search/Insert/Delete: O(log n)
- Space: O(n)
- Minimizes disk access by storing multiple keys per node.
Disjoint Set (Union-Find)
Definition:
Manages elements partitioned into disjoint sets and efficiently merges them.
- Union/Find: ~O(α(n)), where α is the inverse Ackermann function
- Space: O(n)
- Useful in Kruskal’s MST and connectivity problems.