# Linked list
A **linked list** is a sequence of nodes where each node holds a value and a pointer to the next node. The nodes need not be contiguous in memory; the pointer is what links them. The head pointer is the entry point; the last node's next pointer is NULL. Insertion and deletion at any position where you already hold a pointer costs O(1) — no elements shift — but reaching a position by index requires traversing from the head, costing O(n).

```c
struct node {
    int         val;
    struct node *next;
};

struct node *head = NULL;

// prepend 42
struct node *n = malloc(sizeof *n);
n->val  = 42;
n->next = head;
head    = n;
```

The primary advantage over an [[array]] is O(1) insertion and deletion without moving other elements: splice in a node by redirecting two pointers. The primary disadvantage is poor cache behaviour — nodes are scattered in memory and each `next` pointer dereference is a potential cache miss. Sequential iteration over a linked list is significantly slower than over an array in practice, even though both are O(n) asymptotically.

A **doubly linked list** adds a `prev` pointer to each node, allowing traversal in both directions and O(1) deletion given a pointer to the node itself (no need to find the predecessor). The cost is an extra pointer of storage per node.

| Operation | Time |
|---|---|
| Access by index | O(n) |
| Insert/delete at head | O(1) |
| Insert/delete (given pointer to node) | O(1) |
| Search | O(n) |