Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Singly Linked Lists

4 min read

You'll learn to

-Explain how a chain of Node objects, each holding a value and a next reference, forms a list
-Compare front insertion (O(1) here, O(n) for a Python list) with index access (the reverse)
-State the trade-off: cheap insertion at the ends, no random access

Every structure built so far this tier, the stack, the circular-buffer queue, the hashmap's buckets, leaned on a Python list, a contiguous array under the hood. A linked list throws that away and builds a chain of separate objects instead, trading random access for genuinely cheap insertion and removal at the ends.

An Analogy: A Treasure Hunt

In a treasure hunt, each clue tells you only where the next clue is. To reach clue number 500 you must follow clues 1 to 499 first. But adding a new first clue is easy: write it and tell people it leads to the old first clue. A linked list is that chain of clues. Reaching a position is slow, and adding at the start is instant.

The Node: value + next

The building block of a linked list: one value, one pointer to the next node

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

A linked list is just a chain of these Node objects. Each points to the next, and the list itself only needs to remember where the chain starts (the head) and, usually, where it ends (the tail).

Press Run: a LinkedList with prepend and append, and the real cost of reaching index 500

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

    def prepend(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self._size += 1

    def append(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self._size += 1

    def to_list(self):
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result

    def __len__(self):
        return self._size

ll = LinkedList()
for name in ["b", "c", "d"]:
    ll.append(name)
ll.prepend("a")
print("contents:", ll.to_list(), "| length:", len(ll))

def hops_to_reach(linked_list, index):
    current, hops = linked_list.head, 0
    while hops < index:
        current = current.next                 # walk the chain, one next reference at a time
        hops += 1
    return current.value, hops

big = LinkedList()
for number in range(1000):
    big.append(number)
value, hops = hops_to_reach(big, 500)
print("reaching index 500 in a linked list took", hops, "hops (a Python list reaches it in 1 step)")

python_list = list(range(1000))
print("inserting at the front of a Python list shifts", len(python_list), "items;",
      "a linked list prepend changes just 2 references")

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self._size = 0

def prepend(self, value):
        node = Node(value)
        node.next = self.head
        self.head = node
        if self.tail is None:
            self.tail = node
        self._size += 1

def append(self, value):
        node = Node(value)
        if self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            self.tail = node
        self._size += 1

def to_list(self):
        result = []
        current = self.head
        while current is not None:
            result.append(current.value)
            current = current.next
        return result

def __len__(self):
        return self._size

ll = LinkedList()
for name in ["b", "c", "d"]:
    ll.append(name)
ll.prepend("a")
print("contents:", ll.to_list(), "| length:", len(ll))

def hops_to_reach(linked_list, index):
    current, hops = linked_list.head, 0
    while hops < index:
        current = current.next                 # walk the chain, one next reference at a time
        hops += 1
    return current.value, hops

big = LinkedList()
for number in range(1000):
    big.append(number)
value, hops = hops_to_reach(big, 500)
print("reaching index 500 in a linked list took", hops, "hops (a Python list reaches it in 1 step)")

python_list = list(range(1000))
print("inserting at the front of a Python list shifts", len(python_list), "items;",
      "a linked list prepend changes just 2 references")

Why Head Insertion Is O(1) Here but O(n) for a Python List

Inserting at the front of a Python list with list.insert(0, x) forces every existing element to shift one slot to the right, which is O(n). It is the same shifting cost as the naive queue's pop(0) from the previous module. A linked list's prepend touches only one new node and the existing head reference: two pointer assignments, whatever the chain's length. That is O(1), always.

The Trade-off: No Random Access

The cost of that flexibility is that a linked list cannot jump straight to "the 500th element" the way arr[500] can on a Python list. Reaching any node other than the head, or the tail if you track it, means walking the chain one next reference at a time from the head. That is an O(n) operation, even though the same lookup on a Python list is O(1). The demo made it concrete: 500 hops against one step.

Operation comparison

O(1)

Insert at front (LinkedList)

O(n)

Insert at front (Python list)

O(n)

Access by index (LinkedList)

O(1)

Access by index (Python list)

This is why ordinary code defaults to a Python list, and keeps a hand-built linked list for specific situations: implementing another structure's internals (a queue, a stack, an LRU cache's eviction order in this tier's capstone), or anywhere O(1) insertion and removal at both ends is needed without ever needing random access.

Interview Signal is part of Pro

See a real weak answer next to a real strong one for this exact topic.

Quiz is part of Pro

Test what you just read with a short quiz, and bank the XP.

Building a HashMap Reversal & Fast/Slow Pointers

Discussion0

Join the Discussion

No comments yet. Be the first to start the thread!