---
title: 'Linked Lists'
source: 'https://academia.sh/en/courses/data-structures/linked-lists'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:56+00:00'
license: 'CC BY-SA 4.0'
---

# Linked Lists

Node and link structure, singly and doubly linked lists, the cost of pointer relinking, and their practical limits.

An array's insertion and deletion cost arose from a single requirement: elements
staying contiguous. If contiguity is abandoned, shifting disappears with it.

A **linked list** makes this trade-off. Elements sit wherever they like in memory;
order is established by each element carrying the address of the next one.

## Node and Link

The structure's unit is the **node**: a value and the address of the next node.

```
head → [12 | •] → [18 | •] → [7 | •] → [25 | ⏚]
```

The last node's link is empty; this emptiness marks the end of the list. The list
itself is represented by a single thing: the address of the first node, that is, the
**head**.

Address arithmetic does not apply here. Where the third element is cannot be computed;
two links must be followed starting from the head. This means losing the array's
constant-time access: in a linked list, access to the $i$-th element is $O(n)$.

```python
class Node:
    """A value and the link to the next node."""

    def __init__(self, value: int) -> None:
        self.value = value
        self.next: "Node | None" = None


class LinkedList:
    def __init__(self) -> None:
        self.head: Node | None = None
        self.length = 0

    def prepend(self, value: int) -> None:
        """Links the new node at the head: constant time."""
        new_node = Node(value)
        new_node.next = self.head
        self.head = new_node
        self.length += 1

    def find(self, value: int) -> int:
        """Returns the value's index; -1 if absent. Takes as many steps as the links followed."""
        index = 0
        node = self.head
        while node is not None:
            if node.value == value:
                return index
            node = node.next
            index += 1
        return -1

    def values(self) -> list[int]:
        result = []
        node = self.head
        while node is not None:
            result.append(node.value)
            node = node.next
        return result


linked_list = LinkedList()
for measurement in (25, 7, 18, 12):    # inserted in reverse order
    linked_list.prepend(measurement)

print(linked_list.values())                        # [12, 18, 7, 25]
print(linked_list.find(7), linked_list.find(99))    # 2 -1
print(linked_list.length)                           # 4
```

Prepending is constant time: two links are written, no element is moved. The same
operation shifted every element in an array.

## Locating Versus Linking

The most commonly misunderstood aspect of the linked list is this: **insertion and
deletion are cheap, but locating the position is expensive.**

If a node reference is already in hand, inserting after it is a few pointer writes —
$O(1)$. But if the request is "insert after the tenth element," nine links must be
followed first; the total cost is $O(n)$ after all.

This distinction determines the linked list's proper use: the structure pays off if
the reference to the relevant node is already held; it does not if every operation
searches from the head.

## Doubly Linked List

Deleting a node in a singly linked list requires changing the **previous** node's
link, yet there is no way to go backward from the node. The solution is to add a
back-link to every node as well.

In a **doubly linked list**, every node knows both its next and its previous.
Consequences:

- Deletion is $O(1)$ when a node reference is already in hand.
- The list can be traversed in either direction.
- Every node carries one more pointer; memory overhead increases.
- Every insertion and deletion updates four links instead of two; the code is more
  error-prone.

If both head and tail pointers are kept, insertion at either end of the list becomes
constant time. This is the natural foundation of the stack and queue structures in the
next two lessons.

A third variant is the **circular list**, in which the last node links back to the
head; it is used in scheduling and buffering applications that keep cycling to the
next item.

## Sentinel Node

The source of errors in linked list code is edge cases: inserting into an empty list,
deleting the first node, inserting after the last node. Each requires a separate `if`
block, and when one of these blocks is forgotten, the bug shows up only in that
specific case.

A **sentinel node** is a dummy node that carries no value and is placed permanently at
the head of the list. Because the head always exists, "deleting the first node" stops
being a separate case — every node has a predecessor.

```python
class SentinelList:
    """Deletion runs with a single code path thanks to the head sentinel node."""

    def __init__(self) -> None:
        self.sentinel = Node(0)        # its value is never used

    def insert(self, value: int) -> None:
        new_node = Node(value)
        new_node.next = self.sentinel.next
        self.sentinel.next = new_node

    def remove(self, value: int) -> bool:
        previous = self.sentinel       # a valid "previous" always exists
        while previous.next is not None:
            if previous.next.value == value:
                previous.next = previous.next.next
                return True
            previous = previous.next
        return False


sentinel_list = SentinelList()
for measurement in (7, 18, 12):
    sentinel_list.insert(measurement)
print(sentinel_list.remove(12), sentinel_list.remove(99))    # True False
```

The same technique is also used in circular doubly linked lists, and it markedly
reduces the number of edge cases in the code.

## Memory Overhead and Cache

The linked list's advertised advantages are limited in practice by two costs.

**Extra space.** Every node carries one or two pointers alongside its value. With
eight-byte pointers, in a singly linked list of four-byte integers the structural data
outweighs the actual data. Compared to an array, memory usage can grow by a
multiplicative factor.

**Locality.** Nodes sit scattered on the heap. Moving from one node to the next means
jumping to an unpredictable address in memory; fetching a cache line brings no
benefit, and prefetching does not work. The difference calculated in the cache lesson
of the How Computers Work course works in reverse here: while array traversal uses
many elements per cache line, list traversal carries a separate miss risk for every
node.

The result is this: a linked list insertion that is $O(1)$ on paper can, in actual
measurements, be slower than an array insertion that is $O(n)$ — especially when the
element count is small or moderate. The complexity class ignores constant factors;
hardware does not.

## When to Use a Linked List

The structure's legitimate use cases are narrow but real:

- **When a node reference is already held.** The best-known example is a doubly
  linked list used together with a hash table: the table hands over the node
  directly, and the list updates the ordering in constant time.
  Least-recently-used cache designs are built on this pair.
- **When reallocation is unacceptable.** A dynamic array's growth makes a single
  operation take a long time; systems with a latency bound may not tolerate this.
- **When reference stability is required.** A node's address in a linked list does
  not change when new elements are added to the list; in a dynamic array,
  reallocation invalidates every address.
- **When lists are frequently merged.** Joining two lists end to end amounts to
  writing a single link.

Outside of these, the default choice is the array.

## Cost Table

| Structure | Access | Search | Insert at start | Insert at end | Delete (node in hand) |
|---|---|---|---|---|---|
| Array (fixed size) | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$* | $O(n)$ |
| Dynamic array | $O(1)$ | $O(n)$ | $O(n)$ | $O(1)$ amortized | $O(n)$ |
| Singly linked list | $O(n)$ | $O(n)$ | $O(1)$ | $O(n)$** | $O(n)$ |
| Doubly linked list | $O(n)$ | $O(n)$ | $O(1)$ | $O(1)$** | $O(1)$ |

\* As long as room remains.  \*\* $O(1)$ if a tail pointer is kept.

## Summary

- In a linked list, elements do not sit contiguously; order is established by each
  node carrying the address of the next one.
- Address arithmetic does not apply; access to the $i$-th element is linear time.
- Insertion and deletion are cheap because they amount to writing pointers; what is
  expensive is locating the position.
- In a doubly linked list, the back-link makes deletion constant time when a node is
  in hand; the cost is extra memory and more complex updates.
- Pointer overhead and scattered layout can pull the list's practical performance
  below its theoretical cost.
- The structure is chosen when a node reference is already held, when reallocation is
  unacceptable, or when reference stability is required.

## Next Step

The next two lessons take up two abstract data types built on top of the structures
defined so far. The first is the stack, which permits access only to the most
recently added element; how function calls are managed will be recalled from the
previous course.