Arrays and linked lists

Use an array when you need the item at position 20. Use linked nodes when you already know where to change the links.

Trace the same edit

Insert B between A and C, then remove C:

Array:   [A, C, D, _] -> [A, B, C, D] -> [A, B, D, _]
                   shift C,D right       shift D left

Nodes:   A -> C -> D  -> A -> B -> C -> D -> A -> B -> D
                        change links        bypass C

An array stores slots next to one another. Its address calculation finds index i directly. Slots may hold values or references to values elsewhere.

A linked list stores a value and a next link per node. A doubly linked list also stores a previous link. Finding position i requires following i links from the head.

The array invariant is that live elements occupy indices 0 through length − 1. Capacity counts allocated slots, including unused ones. The list invariant is that following next links visits the sequence in order and ends at null. A doubly linked list also keeps neighboring next and previous links consistent.

Fixed array versus dynamic array

A fixed array has a length chosen when it is created. Its slots support O(1) indexing, but it has no automatic append operation. A buffer may track a smaller live length inside that allocation.

A dynamic array adds a live length and a capacity. When full, it allocates a larger array and moves or copies the live elements. This makes append possible while preserving direct indexing. Python's list is one dynamic-array implementation; the concept is independent of Python.

Neither kind stays sorted automatically. In an unsorted array, finding a value takes O(n). In a sorted array, binary search takes O(log n), but an insertion still has to shift elements.

What the costs assume

A singly linked node cannot generally remove itself in O(1): you need its predecessor. A doubly linked node can, provided you also update head or tail when needed.

Dynamic arrays usually grow capacity geometrically. Doubling capacity costs O(n) for that resize, but leaves room for n more appends. Growing by one slot each time would make n appends cost O(n²).

Arrays often benefit from nearby memory accesses. Linked lists pay for links and often separate allocations. O(1) pointer edits alone do not make linked lists faster for every workload.

Trace lookup and deletion

To find C in A → B → C → D, visit A, then B, then C. Keep B as the predecessor. Delete C by making B point to D. Reading C's old next link first prevents losing the rest of the list.

Predict and modify

1. Capacity is 4 and length is 4. How much work can the next append require?
2. You have only a singly linked tail node. Can you remove it in O(1)?
3. Add a tail pointer. Which edits must update it?

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


def insert_after(previous, value):
    node = Node(value, previous.next)
    previous.next = node
    return node


def remove_after(previous):
    removed = previous.next
    if removed is None:
        raise IndexError("no next node")
    previous.next = removed.next
    removed.next = None
    return removed.value


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


head = Node()
a = insert_after(head, "A")
c = insert_after(a, "C")
insert_after(c, "D")
b = insert_after(a, "B")
assert values(head) == ["A", "B", "C", "D"]
assert remove_after(b) == "C"
assert values(head) == ["A", "B", "D"]
assert remove_after(head) == "A"
assert values(head) == ["B", "D"]

Apply the link invariant in Reverse Linked List.

Next: Stacks, queues, and deques.