Data Structures: Arrays, Linked Lists, Trees, Heaps & Hash Tables

Access by index O(1); search O(n) (O(log n) if sorted); insert or delete in the middle O(n) because elements shift.

When it fills up it allocates a bigger block (typically about double) and copies. Copies are rare enough that the average cost per append stays constant.

Access or search O(n), since you must walk the nodes. Insert or delete at the head O(1); anywhere else O(1) once you hold a reference to the neighboring node.

Singly: each node points to the next. Doubly: each node also points to the previous, which allows O(1) deletion of a known node and backward traversal, at the cost of extra memory.

Stack: push/pop. Queue: enqueue/dequeue. All O(1).

Function call stack, undo/redo, matching parentheses, evaluating expressions, iterative depth-first search, backtracking.

Breadth-first search, task scheduling, print and request buffers, producer-consumer pipelines.

A double-ended queue: insert and remove at both ends in O(1)

Average O(1) for insert, lookup and delete. Worst case O(n) when many keys collide into the same bucket.

Separate chaining: each bucket holds a list of entries Open addressing: probe for another empty slot (linear probing, quadratic probing, double hashing)

Number of stored entries divided by number of buckets. When it passes a threshold (often around 0.75), the table resizes and rehashes.

For every node, all keys in the left subtree are smaller and all keys in the right subtree are larger.

O(h) where h is the height: O(log n) when balanced, but O(n) in the worst case (inserting sorted data makes a linked-list-shaped tree).

In-order traversal: left subtree, node, right subtree.

Pre-order: node, left, right (copying a tree). Post-order: left, right, node (deleting a tree, evaluating expression trees). Level-order: breadth-first, row by row, using a queue.

A complete binary tree. In a min-heap every parent is ≤ its children, so the minimum is at the root (max-heap: the reverse).

Peek min/max O(1); insert O(log n); extract min/max O(log n); build a heap from n items O(n).

Children of i : 2i + 1 and 2i + 2 . Parent of i : \lfloor (i - 1)/2 \rfloor .

A binary heap.

Matrix: O(V²) space, O(1) edge check; good for dense graphs. List: O(V + E) space, iterate neighbors quickly; good for sparse graphs (most real graphs).

A prefix tree storing strings character by character; lookup and insert take O(L) for a key of length L. Used for autocomplete.

2^{h+1} - 1 (counting height as edges from the root)

Tracks which elements are in the same set. With path compression and union by rank, find and union run in nearly constant amortized time. Used in Kruskal's algorithm.

A hash map from key to node plus a doubly linked list ordered by recent use.