Linked lists

Inserting in the middle of an array is expensive because everything after the insertion point must move. A linked list removes that cost by refusing to keep its elements together. Each element lives in its own node with a pointer to the next, so changing the chain means rewriting a pointer or two — at the price of losing random access entirely.

Use the panel to prepend, append, remove the head and walk the chain. The cursor shows how traversal actually moves.

The node #

A node is a tiny record: some data and a reference to the next node (or None at the end). The list itself is just a reference to the head.

class Node:
    def __init__(self, value, next=None):
        self.value = value
        self.next = next
 
class LinkedList:
    def __init__(self):
        self.head = None
 
    def prepend(self, value):
        self.head = Node(value, self.head)   # O(1)

prepend rewrites one pointer regardless of the list length, which is exactly what an array cannot do.

The costs #

• Prepend at the head: $O(1)$.
• Insert or delete after a known node: $O(1)$.
• Search / access index k: $O(n)$ — you must walk.
• Append without a tail pointer: $O(n)$; keep a tail reference to make it $O(1)$.

Notice the trade is the mirror image of the array: cheap anywhere insertion, expensive indexing. Neither is better; they are good at opposite things.

Variants #

• A doubly linked list adds a prev pointer, so you can delete a node given only the node itself, and traverse backward. Each node pays one extra pointer.
• A circular list points the tail back at the head, useful for round-robin scheduling.
• A sentinel node at the front removes the special case of inserting into an empty list, simplifying the code.

Linked lists matter less in Python than in C because a Python list is already a fast dynamic array, but the pointer-chasing pattern behind them reappears in every tree and graph you will meet later.

Where next: trees — imposing an order on linked nodes so search becomes logarithmic instead of linear.