Linked Lists: Nodes, Pointers and Trade-offs

The problem linked lists solve

You now know arrays have a weakness. Elements sit in one contiguous block, which makes indexing O(1) but makes inserting or deleting in the middle O(n) — everything after the change has to shift.

There is a second problem. A contiguous block must be reserved up front. If you ask for space for 100 items and need 101, you must allocate a bigger block and copy everything across.

A linked list trades away fast indexing to fix both problems. Instead of one block, it uses many small pieces scattered anywhere in memory, each carrying a pointer to the next.

Nodes and pointers

The building block is a node, which holds two things:

• the data you care about
• a reference to the next node (or None if it is the last)

head
 |
 v
[10 | *]---> [20 | *]---> [30 | None]

The three nodes might sit at completely unrelated memory addresses. They stay connected only because each one remembers where the next one is. Lose the head reference and the whole list is unreachable.

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

# Build the chain by hand to see what is really happening
a = Node(10)
b = Node(20)
c = Node(30)

a.next = b
b.next = c

head = a

# Walk the chain
current = head
while current is not None:
    print("Node holds:", current.data, "| next is:",
          current.next.data if current.next else "None")
    current = current.next

There is no index anywhere. To reach the third node you must go through the first and second. That is the fundamental cost: accessing element i is O(n), not O(1).

The core operations

Traversal. Start at head, follow next until None. O(n).

Insert at head. Make a new node, point its next at the old head, move head to the new node. Two assignments, no shifting, O(1) regardless of list length. This is the operation arrays are bad at and linked lists are excellent at.

Insert at end. Walk to the last node, then attach. O(n) unless you also keep a tail reference, in which case O(1).

Delete a node. Point the previous node's next past it. The removed node becomes unreachable and the memory is reclaimed. The pointer change is O(1); finding the previous node is O(n).

Search. Walk and compare. O(n) always. There is no shortcut.

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

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

    def insert_at_head(self, data):        # O(1)
        node = Node(data)
        node.next = self.head
        self.head = node

    def insert_at_end(self, data):         # O(n)
        node = Node(data)
        if self.head is None:
            self.head = node
            return
        current = self.head
        while current.next is not None:
            current = current.next
        current.next = node

    def delete(self, data):                # O(n)
        current = self.head
        previous = None
        while current is not None:
            if current.data == data:
                if previous is None:       # deleting the head
                    self.head = current.next
                else:
                    previous.next = current.next
                return True
            previous = current
            current = current.next
        return False

    def search(self, data):                # O(n)
        current = self.head
        position = 0
        while current is not None:
            if current.data == data:
                return position
            current = current.next
            position += 1
        return -1

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

ll = LinkedList()
ll.insert_at_end(10)
ll.insert_at_end(20)
ll.insert_at_end(30)
print("After appends:", ll.to_list())

ll.insert_at_head(5)
print("After insert at head:", ll.to_list())

print("Search for 20:", ll.search(20))
print("Search for 99:", ll.search(99))

ll.delete(20)
print("After deleting 20:", ll.to_list())

ll.delete(5)
print("After deleting the head:", ll.to_list())

Read the delete method carefully. The previous is None branch handles deleting the head, which is the case people forget. Almost every linked list bug lives at the head, the tail, or the empty list.

Reversing a linked list

This is the classic interview question, and it is worth understanding rather than memorising. You walk the list flipping each next pointer backwards, keeping three references so you never lose your place.

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

def build(values):
    head = None
    for v in reversed(values):
        node = Node(v)
        node.next = head
        head = node
    return head

def to_list(head):
    out = []
    while head is not None:
        out.append(head.data)
        head = head.next
    return out

def reverse(head):
    previous = None
    current = head
    while current is not None:
        next_node = current.next    # save it before we overwrite
        current.next = previous     # flip the pointer
        previous = current          # move both references forward
        current = next_node
    return previous                 # previous is the new head

head = build([1, 2, 3, 4, 5])
print("Original:", to_list(head))
head = reverse(head)
print("Reversed:", to_list(head))

The line next_node = current.next is the important one. Once you overwrite current.next, the rest of the list is gone unless you saved it first.

Array versus linked list

That last row deserves attention. Modern processors load memory in blocks, so scanning an array pulls several elements into fast cache at once. A linked list jumps around, and each jump can be a cache miss. In practice arrays often beat linked lists even on operations where the Big-O favours the list.

Variants worth knowing by name

• Singly linked list — each node points forward only. What we built here.
• Doubly linked list — each node also points backward. Deletion given only the node is O(1), at the cost of one more pointer per node.
• Circular linked list — the last node points back to the head. Useful for round-robin scheduling.

Common mistakes

Losing the head reference. Assigning head = head.next while traversing destroys your only handle on the list. Always walk with a separate current variable.

Forgetting the empty list. Every method needs to behave sensibly when head is None. This is the most common source of AttributeError: 'NoneType' object has no attribute 'next'.

Forgetting the head case in delete. Deleting the first node requires updating head, not a previous node's pointer.

Checking current.next is not None when you meant current is not None. The first stops one node early, so the last element is never processed.

Overwriting a pointer before saving it. In reversal and insertion, save current.next into a temporary before changing it.

Practice

Try the linked list exercises on the practice page — build, traverse and reverse one from scratch.