The Core Idea
A Chain, Not a Contiguous Block
An array stores its elements in one contiguous block of memory, which is why you can jump straight to any index instantly. A linked list instead stores each element as a separate node — a small object holding the value itself plus a pointer (reference) to the next node in the chain. The nodes can live anywhere in memory; what makes them a 'list' is purely the chain of pointers connecting them in order.
This trade-off is fundamental: because there's no contiguous block, you can't jump to 'the 5th element' directly — you have to walk the chain from the head, one pointer at a time, until you arrive. But because nodes aren't stored contiguously, inserting or removing a node in the middle only requires relinking a couple of pointers, not shifting every element after it.
💡 Memory Trick
Think of a scavenger hunt where each clue tells you where to find the next clue. You can't skip straight to clue #7 — you have to follow clue #1 to clue #2 to clue #3, and so on. But if you want to insert a brand-new clue between #3 and #4, you don't have to renumber or move any other clue — you just change clue #3 to point to the new clue, and have the new clue point to what used to be #4.
The Two Main Types
Singly Linked vs. Doubly Linked
1
Singly Linked List
Each node points only forward, to the next node. You can traverse the list in one direction only — from head to tail. This is the simpler, more memory-efficient version, but you cannot walk backward from a given node without restarting from the head.
2
Doubly Linked List
Each node holds two pointers: one to the next node, and one to the previous node. This allows traversal in both directions and makes certain operations (like removing a node when you only have a reference to it, not its predecessor) more efficient, at the cost of extra memory per node for the second pointer.
Linked List vs. Array
Where Each Operation Wins
Random access (get the element at index i) is O(1) for an array but O(n) for a linked list, because the linked list must walk the chain from the head to reach position i — this is the single biggest weakness of linked lists compared to arrays.
Insertion or deletion at a known position (given a reference to the node) is O(1) for a linked list — just relink a couple of pointers — but O(n) for an array, because every element after the insertion/deletion point must be shifted to close or open the gap. This is the linked list's core advantage, and it's why linked lists are preferred when a program does frequent insertions and deletions in the middle of a sequence, while arrays are preferred when a program does frequent random-access reads.
🖥️ Applied Scenario
You're building a music player's 'up next' playlist queue, where songs are frequently added, removed, and reordered mid-list based on user actions, but users rarely jump directly to 'the 47th song in queue.'
1
You consider an array-backed list, but recognize that every time a song is removed from the middle of the queue, every song after it would need to shift down one position — an O(n) operation on every removal.
2
You choose a doubly linked list instead, since removing a song (given a reference to its node) only requires relinking its neighbors' pointers — O(1) regardless of queue length.
3
You choose doubly (not singly) linked specifically because the player needs a 'skip back' feature, which requires walking backward from the current song — something a singly linked list can't do without restarting from the head.
4
Conclusion: because the access pattern is dominated by mid-list insertion/removal rather than random-index lookups, the linked list's O(1) relinking beats the array's O(n) shifting for this specific use case.
📌 Exam Application
Exam questions frequently ask you to compare the time complexity of specific operations (access by index, insertion at head/tail/middle, deletion) between arrays and linked lists, and to justify which structure fits a described access pattern. You may also be asked to trace through inserting or deleting a node by hand, correctly updating both the new node's pointer(s) and its neighbors' pointers.
⚠️ Most Common Linked Lists Mistakes
The most common mistake is forgetting to update both directions of a doubly linked list's pointers during insertion or deletion — updating the 'next' pointer but forgetting the 'previous' pointer (or vice versa) silently corrupts the list's ability to traverse correctly in one direction. Another frequent error is assuming linked lists are always better than arrays because insertion/deletion is O(1) — that's only true given a reference to the relevant node; finding that node in the first place (if you only have an index or value, not a direct reference) still costs O(n), an important detail that's easy to overlook.
✓ Quick Self-Test
Can you draw a small singly linked list and doubly linked list by hand, showing exactly which pointers exist at each node? Can you explain why array access is O(1) while linked list access is O(n), tying the answer to how each structure is laid out in memory?
Next Lesson
Binary Search Trees
→
← All Data Structures Lessons