Linked Lists

A linked list chains elements through pointers so insertion and deletion cost constant time, at the price of losing random access.

Nodes and links

A singly linked list stores each element in a node that holds a value and a pointer to the next node. A head pointer names the first node; the last node points to null. Unlike an array, the nodes need not be contiguous in memory, which is why the structure can grow one node at a time without reallocation.

What links buy you

Given a pointer to a node, inserting or deleting adjacent to it is O(1): you rewire a couple of pointers rather than shifting elements. This makes linked lists a natural backing store for stacks, queues, and hash-table collision chains.

• Insert or delete at a known position: O(1)
• Access the k-th element: O(k) — you must walk the chain
• Search for a value: O(n)
• Prepend to the front: O(1)

The cost of chasing pointers

The price is random access. To reach the k-th element you follow k links, so indexing is O(n). Each node also carries pointer overhead, and because nodes scatter through memory, traversal has poor cache locality compared with an array's tight loop. On modern hardware a linked list often loses to an array even for workloads it should theoretically win.

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

def push_front(head, val):
    node = Node(val)
    node.next = head
    return node  # new head

When to use one

Reach for a linked list when you splice and unsplice at known positions constantly, when you need stable references to elements that survive insertions, or when you cannot tolerate the copy cost of growing an array. Otherwise a dynamic array is usually simpler and faster.