Before studying stacks, queues, trees, or graphs, you need to understand one fundamental question: where exactly does data live in memory, and how do we find it again? The answer determines everything — how fast we can access it, insert into it, or delete from it. Two fundamental strategies exist: arrays and linked lists.
Think of computer memory as a very long street of numbered houses. Each house has an address (a number) and can hold exactly one value. When your program stores data, the operating system assigns it houses on this street. The question is: do you get houses that are next to each other, or houses scattered anywhere on the street?
This single choice — contiguous vs scattered — is what separates an array from a linked list. Every other difference in performance follows directly from it.
arr[3], the computer computes the address of slot 3 by arithmetic — it does not search for it. This is why array access is O(1).An array stores all its elements in consecutive memory addresses. If the array starts at address 0x04 and each integer takes 4 bytes, then element 0 is at 0x04, element 1 at 0x08, element 2 at 0x0C, and so on. The address of any element can be computed instantly with a simple formula.
Because of this formula, random access is O(1) — you can jump directly to any element by index without scanning through others. This is the array's greatest strength.
A linked list stores elements anywhere in memory — elements do not need to be adjacent. Instead, each element (called a node) stores two things: its data value and the memory address of the next node. This address is called a pointer.
By following pointers from one node to the next, you can traverse the entire list — even though the nodes are physically scattered across memory.
The basic node structure can be extended in different ways, each adding new capabilities at the cost of a little extra memory per node.
Each node has one pointer — to the next node. Traversal goes in one direction only. 2 fields per node. Used for stacks, simple queues, and hash table chaining.
Each node has two pointers — to the next node AND to the previous node. Traversal works in both directions. 3 fields per node. Used for browser history, undo/redo, and deques.
Like a singly linked list, but the last node's NEXT points back to the first node instead of NULL. There is no end — traversal keeps going in a circle. Used for round-robin scheduling (CPU task management) and music playlist loops.
Elements are always maintained in ascending order. Every insertion finds the correct position first (O(n) scan), then wires the new node in — keeping the list sorted at all times. Used as the basis for priority queues implemented with linked lists.
| Operation | Array | Singly Linked List | Doubly Linked List |
|---|---|---|---|
| Access by index | O(1) ✓ | O(n) ✗ | O(n) ✗ |
| Search (unsorted) | O(n) | O(n) | O(n) |
| Insert at beginning | O(n) — shift all | O(1) ✓ | O(1) ✓ |
| Insert at end | O(1) — if space | O(n) — find tail | O(n) — find tail* |
| Insert at position i | O(n) — shift | O(n) — traverse | O(n) — traverse |
| Delete by value | O(n) — shift | O(n) — find pred. | O(n) find, O(1) delete ✓ |
| Memory per element | 1 word (data only) | 2 words (data + next) | 3 words (prev + data + next) |
| Dynamic resize | ❌ Fixed at declaration | ✓ Any time | ✓ Any time |
| Reverse traversal | O(1) — decrement index | ❌ Not possible | O(1) — follow prev ✓ |
* O(1) if a TAIL pointer is maintained separately
A heap is a tree — but it is always stored as an array, not as a linked list. This seems counterintuitive at first. The reason is the parent-child address formula: in a heap stored as an array, the children of node at index i are always at indices 2i+1 and 2i+2, and the parent of node at index i is at index ⌊(i-1)/2⌋.
This formula lets you jump directly to any parent or child in O(1) — no pointer chasing, no traversal. Storing the same heap as a linked list would lose this formula entirely, forcing O(n) searches for parent nodes.
Heap Array vs Linked List shows you the exact moment the array formula O(1) vs linked list O(log n) matters for a heap structure. Node Forge lets you build linked list nodes from scratch — dragging DATA and NEXT fields together and wiring them into a live list.