Array

A contiguous block of slots in memory. Access by index is O(1) — the runtime computes start + i × size. Insert / delete in the middle costs O(n) because everything to the right has to shift.

Ready.
Access
O(1)
Search
O(n)
Insert end
O(1) amortised
Insert mid
O(n)
Delete end
O(1)
Delete mid
O(n)
When to use: when you need fast index lookup and the size is roughly known. Most "lists" in real programs are dynamic arrays under the hood (Python list, JS Array, Java ArrayList, C++ std::vector). They double their capacity when full — that's why end-insert is amortised O(1).

Linked list (singly)

A chain of nodes; each node stores its value and a pointer to the next. No contiguous memory, no shifting on insert — but you can\'t jump to the middle, you have to walk from the head.

Ready.
Insert head
O(1)
Insert tail
O(n) without tail ptr
Search
O(n)
Delete (known node)
O(1)
Random access
O(n)
When to use: frequent insertions / deletions in the middle when you already have a pointer to the spot. Real example: an LRU cache combines a hash map with a doubly-linked list — O(1) lookup + O(1) reorder. Don\'t use when you need random access — pick an array.

Stack & queue

Two restricted access patterns built on top of arrays or linked lists. Stack is LIFO (last-in, first-out). Queue is FIFO (first-in, first-out).

Stack — push / pop

Ready.

Queue — enqueue / dequeue

Ready.
Where you\'ll meet them: a function call stack stores return addresses; the browser back button pops a stack of pages. Queues power task schedulers, breadth-first search, message buses (RabbitMQ, Kafka), and printer spoolers.

Hash table

A clever array. Run the key through a hash function to get an index, store the value at that slot. Average O(1) for insert / lookup / delete — but collisions can slow you down. We resolve collisions by chaining: each slot is a small list.

Ready.
Lookup avg
O(1)
Lookup worst
O(n)
Insert avg
O(1)
Memory
O(n) + table
How the hash works here: for demo simplicity, we use a small 8-bucket table with hash = sum-of-charcodes mod 8. Real hash tables use a much wider, well-distributed hash (FNV, SipHash, MurmurHash) and resize when the load factor crosses ~0.75.

Binary search tree

Each node has up to two children. The invariant: every left descendant is less than the node, every right descendant is greater. Insert / search by walking left or right based on comparison — O(log n) when the tree is balanced, O(n) when it degenerates into a chain.

Ready.
Search avg
O(log n)
Search worst
O(n)
Insert avg
O(log n)
In-order walk
visits sorted
The balance problem: a plain BST built from sorted input becomes a one-sided chain — same as a linked list. Real implementations use self-balancing variants (Red-Black, AVL, B-Tree) that re-balance on every insert. Java\'s TreeMap is Red-Black; SQLite\'s indices use B-trees.

Which structure should I use?

Pick the structure that makes your most-frequent operation fast.

Need fast index access

→ Array. Constant time, cache-friendly. Use a dynamic array (Python list, JS Array, Java ArrayList).

Need fast insert / delete in the middle

→ Linked list. Just rewire two pointers. Doubly-linked if you need backward traversal.

Need last-in, first-out

→ Stack. Function calls, undo histories, expression evaluation, depth-first search.

Need first-in, first-out

→ Queue. Task scheduling, breadth-first search, fair turn-taking.

Need fast lookup by key

→ Hash table. O(1) average for put / get / delete. Beware ordering — most hash tables don\'t preserve insertion order (Java HashMap), though some do (Python dict 3.7+).

Need lookup AND sorted order

→ BST (Red-Black or AVL). O(log n) for everything; in-order walk gives sorted output for free. C++ std::map, Java TreeMap.

Need to find min / max repeatedly

→ Heap (priority queue). O(log n) insert and extract-min. Used in Dijkstra\'s shortest path, A*, scheduling.

Need set membership only

→ Hash set or Bloom filter. Hash set is exact O(1); Bloom is probabilistic (false positives possible) but uses a fraction of the memory.

0
Score
0
Streak
—
%
Question