Linked Lists from Scratch
A linked list stores elements in separate nodes connected by references, instead of one contiguous block like an array. That single design change flips the cost profile: insertion at the front becomes O(1), but indexing becomes O(n). Linked lists are also the first structure you build from nodes and pointers, the same building blocks used by trees and graphs later in this course.
What You'll Learn
- How nodes and references form a linked list
- Building a singly linked list class with append, prepend, and delete
- Traversal and why indexing is O(n)
- The classic in-place reversal technique
Nodes and References
Each node holds a value and a reference to the next node. The list itself only remembers the head (the first node):
That while current walk is the fundamental linked-list move. Everything else (search, insert, delete) is a variation of it.
A LinkedList Class
Wrapping the head pointer in a class gives us a clean API. Open this one fullscreen; it is the core of the lesson:
Notice how delete works: you never remove a node directly, you make the previous node's next skip over it. The garbage collector reclaims the orphaned node.
Linked List vs Python List
| Operation | Linked list | Python list |
|---|---|---|
| Insert/delete at front | O(1) | O(n) |
| Append at end | O(n), or O(1) with a tail pointer | O(1) amortized |
| Access by index | O(n) | O(1) |
| Search by value | O(n) | O(n) |
| Memory | Extra pointer per node | Compact block |
In day-to-day Python you will usually reach for list or deque. Linked lists earn their keep when you hold a reference to a middle node and need O(1) insertion there, and as the conceptual foundation for trees and graphs. In interviews, they test whether you can manipulate pointers without losing nodes.
The Classic: Reverse a Linked List
The most famous linked-list interview question. Walk the list once, reversing each next pointer as you go, using three variables: prev, current, and a temporary for the next node:
Trace it on paper once with three nodes. The order of the four lines inside the loop is everything: save, flip, advance, advance.
Exercises
Key Takeaways
- A linked list is nodes plus references; the list only stores the head
- Prepend is O(1), but indexing and append (without a tail pointer) are O(n)
- Deleting means bypassing: point the previous node past the victim
- Reversal uses three pointers: save next, flip, advance both
- The slow/fast two-pointer walk finds middles and detects cycles