Singly Linked Lists: Nodes and Chains

The Treasure Hunt

Imagine a treasure hunt where the organizer has hidden 10 clues across a city. Clue #1 is at the park entrance. When you solve it, it tells you to go to the library. The library clue points to the coffee shop. The coffee shop clue points to the train station. And so on.

There is no map. There is no list of all locations. The only way to find clue #5 is to start at clue #1 and follow the chain: 1 → 2 → 3 → 4 → 5. You cannot skip ahead. You cannot go backward. Each clue only knows where the next clue is.

That is a singly linked list.

Each "clue" is a node — a container holding a piece of data and a pointer to the next node. The nodes do not need to be physically near each other (unlike array elements). They can be scattered anywhere in memory. What connects them is the chain of pointers.

Why Linked Lists Exist: The Array Problem

Arrays are powerful, but they have a fundamental limitation rooted in how they work: all elements must be stored in contiguous memory.

Imagine an array of 1,000 integers sitting in memory from address 2000 to 5999. If you want to insert a new element at position 500, every element from position 500 to 999 must shift one slot to the right. That is 500 copy operations — O(n).

Now imagine you need to do this thousands of times per second (building a text editor, managing a task queue, implementing an undo system). The cost adds up fast.

Linked lists solve the insertion problem. Because nodes are independent, adding a new node anywhere requires only changing two pointers — O(1) — regardless of how long the list is.

The trade-off: you give up O(1) random access. To reach node 500, you must traverse 499 nodes before it.

The Node Structure

Every linked list is built from nodes. Each node has exactly two things:

1. Data — the value being stored
2. Next pointer — a reference to the next node in the chain (or None if this is the last node)

The nodes may be stored kilobytes apart in physical memory. The next pointer bridges that gap.

Full Python Implementation from Scratch

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None   # Initially points to nothing


class LinkedList:
    def __init__(self):
        self.head = None   # Empty list: head points to nothing

    def append(self, data):
        """Add a new node at the END of the list. O(n)"""
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        current = self.head
        while current.next:         # Traverse until the last node
            current = current.next
        current.next = new_node     # Point last node at the new node

    def prepend(self, data):
        """Add a new node at the BEGINNING of the list. O(1)"""
        new_node = Node(data)
        new_node.next = self.head   # New node points at current head
        self.head = new_node        # Head now points at new node

    def delete(self, data):
        """Remove the first node with the given value. O(n)"""
        if not self.head:
            return
        # Special case: deleting the head node
        if self.head.data == data:
            self.head = self.head.next
            return
        # Find the node just BEFORE the one we want to delete
        current = self.head
        while current.next:
            if current.next.data == data:
                current.next = current.next.next   # Skip over deleted node
                return
            current = current.next
        # Data not found — do nothing

    def search(self, data):
        """Return index of first occurrence, or -1. O(n)"""
        current = self.head
        index = 0
        while current:
            if current.data == data:
                return index
            current = current.next
            index += 1
        return -1

    def display(self):
        """Print the list in visual chain format."""
        elements = []
        current = self.head
        while current:
            elements.append(str(current.data))
            current = current.next
        print(" -> ".join(elements) + " -> None")

    def length(self):
        """Count the number of nodes. O(n)"""
        count = 0
        current = self.head
        while current:
            count += 1
            current = current.next
        return count


# --- Demo ---
ll = LinkedList()

for val in [1, 2, 3, 4, 5]:
    ll.append(val)
ll.display()    # Output: 1 -> 2 -> 3 -> 4 -> 5 -> None

ll.prepend(0)
ll.display()    # Output: 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> None

ll.delete(3)
ll.display()    # Output: 0 -> 1 -> 2 -> 4 -> 5 -> None

print(ll.search(4))    # Output: 4  (index 4 in the remaining list)
print(ll.search(99))   # Output: -1 (not found)
print(ll.length())     # Output: 5

What Each Method Does to Pointers

• prepend: New node's .next points at old head. self.head updated to new node. Two pointer changes. O(1).
• append: Traverse to last node (current.next is None). Set last.next = new_node. One traversal + one pointer change. O(n).
• delete: Find the node before the target. Set prev.next = target.next. The deleted node becomes unreachable and is garbage-collected. One traversal + one pointer change. O(n).

Array vs Linked List: The Trade-Off Table

*O(1) with a tail pointer maintained separately

The linked list wins decisively when insertions and deletions at the front or middle are frequent and you do not need random access by index.

Classic Interview Problems

1. Reverse a Linked List

Reverse the direction of all pointers in a linked list in-place.

def reverse(self):
    prev = None
    current = self.head
    while current:
        next_node = current.next    # Save next before overwriting
        current.next = prev         # Reverse the pointer
        prev = current              # Move prev forward
        current = next_node         # Move current forward
    self.head = prev

# Add this method to LinkedList, then:
ll = LinkedList()
for val in [1, 2, 3, 4, 5]:
    ll.append(val)
ll.reverse()
ll.display()   # Output: 5 -> 4 -> 3 -> 2 -> 1 -> None

Trace for [1 -> 2 -> 3]:

Time: O(n). Space: O(1) — purely pointer manipulation.

2. Detect a Cycle (Floyd's Tortoise and Hare Algorithm)

A cycle in a linked list means some node's .next pointer points back to an earlier node, creating an infinite loop. Floyd's algorithm uses two pointers: a slow one that moves one step at a time, and a fast one that moves two steps at a time.

def has_cycle(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next        # Move 1 step
        fast = fast.next.next   # Move 2 steps

        if slow is fast:        # They meet only if there's a cycle
            return True
    return False   # fast reached None → no cycle

Why it works: If there is a cycle, the fast pointer laps the slow pointer. They are guaranteed to meet inside the cycle because fast gains exactly 1 step on slow per iteration. If there is no cycle, fast reaches None and the loop ends.

Time: O(n). Space: O(1) — no extra data structures needed.

Real-World Uses of Linked Lists

Python's collections.deque is implemented as a doubly linked list under the hood, which is why both appendleft() and popleft() are O(1) — operations that would be O(n) on a regular list.

Key Takeaways

• A linked list is a chain of nodes, each storing data and a pointer to the next node
• Nodes can live anywhere in memory — no contiguous allocation required
• Prepend and delete-at-front are O(1) — linked lists' killer advantage over arrays
• Index access is O(n) — linked lists' critical weakness compared to arrays
• The classic linked list operations — reverse, cycle detection — appear frequently in technical interviews
• Python's collections.deque is a production-grade doubly linked list with O(1) operations at both ends

You now have a solid foundation in the most fundamental sequential data structures. The next step is building on these to understand stacks and queues — higher-level structures built from arrays and linked lists, each solving a specific class of ordering problems.