Day 8: Singly Linked List Explained Simply
Why lock your data into rigid, side-by-side memory seats when you can scatter it anywhere in RAM and connect the dots with arrows?
In 30 Seconds
A Singly Linked List is a linear collection of data elements called nodes [individual containers holding both a value and a directional link]. Unlike an array, where items sit side-by-side in one contiguous block of memory, linked list nodes live in scattered locations across your computer's RAM. Each node holds two things: your actual data, and a pointer [a memory address reference] pointing forward to the very next node in line.
The Real-World Analogy: A Clue-by-Clue Scavenger Hunt
Imagine you are organizing a birthday scavenger hunt across town.
- You hand the player the first clue (we call this the Head [the entry-point pointer to the very first node]).
- That clue contains a small chocolate (the data) and a sticky note saying, "Go to the red bench by the fountain" (the next pointer).
- When the player reaches the red bench, they find another chocolate and a note pointing to the library. The final prize at the library has a note saying "Game Over!" (None / Null).
If you want to add a new stop right after the red bench, you don't have to move the library; you just rewrite the red bench's sticky note!
Picture This
Here is a visual diagram showing a 3-node Singly Linked List with its HEAD pointer and directional next links:
HEAD
|
v
+-------+------+ +-------+------+ +-------+------+
| 10 | *---+---->| 25 | *---+---->| 40 | None |
+-------+------+ +-------+------+ +-------+------+
Data Next Data Next Data Next
And here is how inserting a new node (18) at the very front works in just two pointer updates:
Step 1: Point new node's 'next' to current HEAD (10)
+-------+------+
| 18 | *---+----+
+-------+------+ |
v
HEAD -> [10 | *] ---> [25 | *] ---> [40 | None]
Step 2: Move HEAD label to the new node (18)
HEAD
|
v
[18 | *] ---> [10 | *] ---> [25 | *] ---> [40 | None]
How It Actually Works
- Create the Node Blueprint: Define a
Nodeclass containing two attributes:dataandnext(initialized toNone). - Track the Entry Point (
head): Maintain aheadreference pointing to the first node. If the list is empty,headisNone. - Insert at the Front ($O(1)$): Create a new node, point its
nextreference to the currenthead, and updateheadto become this new node. Zero elements need to shift! - Traverse Sequentially ($O(N)$): Start a temporary pointer at
headand hop viacurrent = current.nextuntilcurrenthitsNone.
Show Me The Code
# Day 8: Singly Linked List Implemented from Scratch in Python
class Node:
def __init__(self, data):
self.data = data # Stores the actual value
self.next = None # Points to the next Node (None by default)
class SinglyLinkedList:
def __init__(self):
self.head = None # Starts empty; head points to nothing
def insert_at_front(self, data):
"""Adds a new node at the beginning in O(1) constant time."""
new_node = Node(data)
new_node.next = self.head # Link new node to the old first node
self.head = new_node # Move head pointer to the new node
def insert_at_end(self, data):
"""Walks to the tail and attaches a new node in O(N) linear time."""
new_node = Node(data)
if self.head is None:
self.head = new_node
return
current = self.head
while current.next is not None:
current = current.next
current.next = new_node
def display(self):
elements = []
current = self.head
while current:
elements.append(str(current.data))
current = current.next
print(" -> ".join(elements) + " -> None")
if __name__ == "__main__":
chain = SinglyLinkedList()
chain.insert_at_front(25)
chain.insert_at_front(10)
chain.insert_at_end(40)
chain.display() # Output: 10 -> 25 -> 40 -> None
Dry Run
| Step | Action Taken | Current Data Structure State | Output / Result |
|---|---|---|---|
| 1 | Create new_node = Node(10) | new_node: [10 | None], head: [25 | None] | New node allocated in memory. |
| 2 | Set new_node.next = self.head | new_node: [10 | *] -> [25 | None] | Link attached to old head. |
| 3 | Update self.head = new_node | head -> [10 | *] -> [25 | None] | List updated in $O(1)$ steps. |
Speed & Memory
| Operation | Best Case | Average Case | Worst Case | Why? |
|---|---|---|---|---|
| Access / Search | $O(1)$ | $O(N)$ | $O(N)$ | Must walk node-by-node starting from head. |
| Insert at Front | $O(1)$ | $O(1)$ | $O(1)$ | Just re-wires two pointers regardless of list size. |
| Insert at End | $O(1)$ | $O(N)$ | $O(N)$ | Must walk to the last node unless a tail pointer is kept. |
| Delete at Front | $O(1)$ | $O(1)$ | $O(1)$ | Simply moves head = head.next. |
Where You'll See It In Real Life
- Image Viewer Slideshows: Clicking "Next Photo" advances a pointer from the current image node to the next photo in memory.
- Blockchain Ledgers: Each block contains data plus a cryptographic pointer linking back to the previous block.
- OS Free-Memory Lists: Operating systems track scattered chunks of available RAM by linking free blocks together.
Traps To Avoid
- Trap 1: Overwriting
headbefore linkingnew_node.next.
Fix: Always connectnew_node.next = headfirst, then updatehead = new_node. - Trap 2: Writing
while current:instead ofwhile current.next:when stopping at the tail.
Fix: Stop whencurrent.next is Noneso you stay on the last node instead of falling off the list. - Trap 3: Forgetting to check if
self.head is None.
Fix: Always guard operations against an empty list to avoidNoneTypeattribute errors.
Practice
- Easy: Write a method
count_nodes(head)that returns the total number of nodes in a singly linked list. - Medium: Write a function
reverse_list(head)that reverses a singly linked list in-place. (Hint: Use three pointers: prev, current, and next_temp.) - Hard: Merge two sorted singly linked lists into a single sorted list by splicing existing nodes.
TL;DR
- Singly Linked Lists store data in scattered nodes, each pointing forward to the next node.
- Front insertions and deletions take $O(1)$ time because no elements need to shift in memory.
- Searching or indexing takes $O(N)$ time because you must follow arrows one by one from the
head.
References Consulted
- GeeksforGeeks - Singly Linked List Tutorial — referenced for verification — all content above is original.
- Programiz - Linked List Data Structure — referenced for verification — all content above is original.
Covered Log Update
Already covered: [Big-O notation, Arrays, Two Pointers, Strings, Sliding Window, Prefix Sums, Recursion basics, Singly Linked List]