commonwrite
← All stories

Day 8: Singly Linked List | Nodes, Pointers & O(1) Insertions

How scattered nodes and memory pointers eliminate array shifting bottlenecks.

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 10 next 25 next 40 next None
   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

  1. Create the Node Blueprint: Define a Node class containing two attributes: data and next (initialized to None).
  2. Track the Entry Point (head): Maintain a head reference pointing to the first node. If the list is empty, head is None.
  3. Insert at the Front ($O(1)$): Create a new node, point its next reference to the current head, and update head to become this new node. Zero elements need to shift!
  4. Traverse Sequentially ($O(N)$): Start a temporary pointer at head and hop via current = current.next until current hits None.

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

StepAction TakenCurrent Data Structure StateOutput / Result
1Create new_node = Node(10)new_node: [10 | None], head: [25 | None]New node allocated in memory.
2Set new_node.next = self.headnew_node: [10 | *] -> [25 | None]Link attached to old head.
3Update self.head = new_nodehead -> [10 | *] -> [25 | None]List updated in $O(1)$ steps.

Speed & Memory

OperationBest CaseAverage CaseWorst CaseWhy?
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 head before linking new_node.next.
    Fix: Always connect new_node.next = head first, then update head = new_node.
  • Trap 2: Writing while current: instead of while current.next: when stopping at the tail.
    Fix: Stop when current.next is None so 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 avoid NoneType attribute errors.

Practice

  1. Easy: Write a method count_nodes(head) that returns the total number of nodes in a singly linked list.
  2. Medium: Write a function reverse_list(head) that reverses a singly linked list in-place. (Hint: Use three pointers: prev, current, and next_temp.)
  3. 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


Covered Log Update

Already covered: [Big-O notation, Arrays, Two Pointers, Strings, Sliding Window, Prefix Sums, Recursion basics, Singly Linked List]