The only question that matters
A data structure is not about storing things. Storage is easy. A data structure is about which operations you want to be fast, because you cannot have them all.
Every structure on this page holds exactly the same numbers. They differ only in what they make cheap and what they make expensive.
Array: one contiguous block
An array is a single unbroken run of memory. Because every element is the same size and they sit shoulder to shoulder, the computer can find element i with one multiplication: address = base + i × size. No searching. That is O(1) random access, and it is the array's superpower.
The price: inserting at the front means physically shifting every other element one slot right. That is O(n), and it gets worse the more data you have.
Switch to Linked list and press Get [2]. Notice the cost flips: the array reads instantly, the list has to walk. Then press Add front and watch the costs flip back.
Linked list: nodes holding hands
A linked list gives up contiguity. Each node stores its value plus a pointer to the next node, scattered anywhere in memory.
Inserting at the front is now trivial — make a new node, point it at the old head, done. O(1). But to reach element 2 you must start at the head and walk. There is no formula for where node 2 lives. O(n).
The trade in one sentence
Arrays are fast to read and slow to reshape. Linked lists are fast to reshape and slow to read. Choose based on which one your program does more often.
Stack and queue: arrays with a rule
A stack is LIFO — last in, first out. Only the top is reachable. Think of a stack of plates, or the browser back button, or how your program tracks nested function calls.
A queue is FIFO — first in, first out. You add at the back and remove from the front, exactly like a queue at a shop. Print jobs, task schedulers, and breadth-first search all run on queues.
Neither adds new capability. They add a restriction, and the restriction is the point: fewer legal operations means fewer ways for your code to be wrong.
Trees: when linear is not enough
A binary search tree keeps everything sorted by an invariant: everything smaller goes left, everything larger goes right. Searching then halves the remaining candidates at every step, giving O(log n) lookup — a million items in about twenty comparisons.
That is only true while the tree stays balanced. Insert already-sorted data into a naive BST and it degenerates into a linked list with O(n) lookup, which is why real systems use self-balancing variants like AVL or red-black trees.
Run In-order on this binary search tree. The visit sequence comes out perfectly sorted: 10, 20, 25, 30… That is not a coincidence, it is the BST invariant made visible.
Cost summary
| Structure | Access | Search | Insert front | Insert end |
|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(1) amortised |
| Linked list | O(n) | O(n) | O(1) | O(n) singly |
| Stack | O(1) top only | O(n) | — | O(1) push |
| Queue | O(1) front only | O(n) | — | O(1) enqueue |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) |
| Hash table | O(1) average | O(1) average | O(1) average | O(1) average |
Choosing a structure for a real problem
Exam questions rarely ask what a stack is. They describe a situation and ask which structure suits it, which is a different skill: read the problem for the order in which items must come out, and for whether the size is known in advance.
| The problem says | Structure | Because |
|---|---|---|
| undo the last action | stack | last in, first out |
| print jobs in the order sent | queue | first in, first out |
| a fixed number of exam marks | array | size known, direct access by index |
| a list that grows unpredictably | linked list | no fixed size, cheap insertion |
| look up a student by roll number | hash table or dictionary | near-instant lookup by key |
| a folder containing folders | tree | naturally hierarchical |
| cities joined by roads | graph | many-to-many connections |
Stack or queue — read for the order
Both hold items waiting to be processed; they differ only in which one leaves first. A stack is last in, first out — undo, the back button, a call stack. A queue is first in, first out — print jobs, a ticket line, buffering. The question always contains the answer: "the most recent" means a stack, "in the order they arrived" means a queue.
Why the trade-off is unavoidable
There is no structure that is best at everything, and the reason is physical rather than a failure of imagination.
An array stores its items in one contiguous block, so the address of item 5000 can be calculated directly and reached instantly. That same contiguity is why inserting at the front requires shifting every later item along, and why the size must be fixed in advance.
A linked list stores each item wherever there is room, with a pointer to the next. Inserting is therefore cheap — change two pointers — and the list can grow indefinitely. But reaching item 5000 means following 5000 pointers, because there is no formula for where it lives.
Fast access and cheap insertion pull in opposite directions. Every structure in the chapter is a different point on that line.
A program maintains a list of students that is searched constantly by position but almost never changed. Then a second program maintains a list that changes constantly but is only ever read from the start. Which structure suits each?
- First program: frequent access by position, rare modification → array.Direct indexing is instant, and the cost of insertion never arises because insertions are rare.
- Second program: frequent insertion and deletion, sequential reading only → linked list.Insertion is a pointer change, and reading from the start does not need indexing.
- Note that neither answer is about which structure is better.The question is which cost the program can afford to pay, and that depends entirely on what it does most often.
Array for the first, linked list for the second — decided by which operation is frequent.