Lesson 5 of 14

Linked Lists

Imagine a treasure hunt where each note gives the location of the next note. The notes need not sit next to each other. A linked list stores a link from each item to the next.

Nodes and the first item

• Node: An item containing a value and a reference to the next node.
• Head: A reference to the first node, where traversal begins.
• End: None means there is no next node.

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

head = Node("A", Node("C"))
head.next = Node("B", head.next)

current = head
while current is not None:
    print(current.value)
    current = current.next

This prints A, B, and C. The class defines a node’s structure; self.value and self.next hold each node’s data.

What changes during insertion?

Initially, the chain is A → C → None. Point the new node B to C, then point A to B. The result is A → B → C → None. C does not move to another memory slot.

The order matters: connect the new node before losing the existing reference to the following node. To delete a node, make its predecessor point to the node after it.

When is insertion fast?

If you already know the node before the insertion point, changing the links takes O(1). But finding the fifth position requires walking from the head. Locating a position takes O(n) in the worst case.

Links also require storage. An array accesses a position directly; a linked list follows references. Instead of assuming that frequent insertion always calls for a linked list, consider how you locate the insertion point.

Check your understanding

To remove B from A → B → C, which link changes if you already know A? Does the cost change if you only know head and must search for B by value?