Linked List

How a linked list works

Imagine a treasure hunt: each clue tells you where the next clue is hidden, but you start with only the first one. To find clue ten, you have to read clues one through nine in order. A linked list works the same way. The data isn't laid out in a tidy row — it's scattered across memory, with each node carrying a pointer to wherever the next one happens to live.

A node in a singly linked list looks like this:

Node {
  value: T
  next:  Node | null
}

The list itself is just a reference to the head node. The last node's next is null, signaling the end. To traverse, you start at the head and keep following .next until you hit null.

Singly vs doubly linked

A doubly linked list adds a prev pointer to each node, so you can walk in both directions:

Node {
  value: T
  next:  Node | null
  prev:  Node | null
}

The doubling matters more than it sounds. With prev available, you can delete any node in O(1) given only a reference to it (node.prev.next = node.next; node.next.prev = node.prev). In a singly linked list, deleting an arbitrary node requires walking from the head to find its predecessor — O(n).

The cost is memory. A doubly linked list spends two pointer-widths per node (16 bytes on 64-bit) on overhead. For a list of 64-bit integers, that's a 3× memory blowup compared to a plain array.

When to use a linked list

• Frequent insertion or deletion at the head. Push-front is O(1); array-based push-front is O(n) because every other element must shift. Stacks, FIFO queues (with a tail pointer), and undo histories live here.
• You need O(1) splice. Cutting a sublist and re-attaching it elsewhere costs one or two pointer updates with a doubly linked list. No array can match that.
• Unknown or wildly variable size. No re-allocation, no doubling, no resize spikes. Each node lives independently.
• Building other structures. Hash table chaining (collision buckets), graph adjacency lists, OS scheduler ready-queues, the LRU cache eviction list — all use doubly linked lists internally.

If your workload is mostly random access, sequential iteration, or sorting, an array (or array-list) wins comfortably. Cache prefetchers fetch adjacent memory for free; linked lists defeat them.

Linked list vs array

	Linked list	Array
Access by index	O(n)	O(1)
Insert at head	O(1)	O(n)
Insert at tail (with tail ptr)	O(1)	O(1) amortized
Insert at known interior node	O(1)	O(n)
Search by value	O(n)	O(n) unsorted, O(log n) sorted
Memory per element	Value + 1-2 pointers	Value only
Cache locality	Poor	Excellent
Resize cost	None	O(n) on doubling

The cache column is what flips the calculus. A modern CPU pulls 64 bytes from main memory per cache miss, and a missed prefetch costs ~100 ns. Walking a million-element linked list can take 100 ms purely in cache stalls. Walking a million-element array takes maybe 1 ms because the prefetcher keeps the cache full of upcoming elements. That 100× factor swamps the algorithmic difference.

Pseudo-code

// Singly linked list operations.

insertAtHead(list, value):
    new_node = Node(value, next=list.head)
    list.head = new_node

deleteByValue(list, value):
    if list.head == null: return
    if list.head.value == value:
        list.head = list.head.next
        return
    prev = list.head
    while prev.next != null:
        if prev.next.value == value:
            prev.next = prev.next.next
            return
        prev = prev.next

reverse(list):
    prev = null
    curr = list.head
    while curr != null:
        next = curr.next
        curr.next = prev
        prev = curr
        curr = next
    list.head = prev

JavaScript implementation

class Node {
  constructor(value, next = null) {
    this.value = value;
    this.next = next;
  }
}

class LinkedList {
  constructor() { this.head = null; this.length = 0; }

  prepend(value) {
    this.head = new Node(value, this.head);
    this.length++;
  }

  append(value) {
    const node = new Node(value);
    if (!this.head) { this.head = node; }
    else {
      let curr = this.head;
      while (curr.next) curr = curr.next;
      curr.next = node;
    }
    this.length++;
  }

  remove(value) {
    if (!this.head) return false;
    if (this.head.value === value) { this.head = this.head.next; this.length--; return true; }
    let prev = this.head;
    while (prev.next) {
      if (prev.next.value === value) { prev.next = prev.next.next; this.length--; return true; }
      prev = prev.next;
    }
    return false;
  }

  reverse() {
    let prev = null, curr = this.head;
    while (curr) { const next = curr.next; curr.next = prev; prev = curr; curr = next; }
    this.head = prev;
  }

  hasCycle() {
    let slow = this.head, fast = this.head;
    while (fast && fast.next) {
      slow = slow.next; fast = fast.next.next;
      if (slow === fast) return true;
    }
    return false;
  }
}

Python implementation

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)

    def remove(self, value):
        if self.head is None: return False
        if self.head.value == value:
            self.head = self.head.next
            return True
        prev = self.head
        while prev.next:
            if prev.next.value == value:
                prev.next = prev.next.next
                return True
            prev = prev.next
        return False

    def reverse(self):
        prev, curr = None, self.head
        while curr:
            curr.next, prev, curr = prev, curr, curr.next
        self.head = prev

    def has_cycle(self):
        slow = fast = self.head
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow is fast: return True
        return False

Python's standard library doesn't ship a singly linked list — list is a dynamic array, collections.deque is a doubly linked list of fixed-size blocks (the best of both worlds). For most production work in Python, deque is the right answer.

Common bugs and edge cases

• Forgetting to update the tail pointer. If your list maintains a tail pointer for O(1) appends, you must update it when the list becomes empty (delete-last) or when inserting after the current tail.
• Memory leaks in manual-memory languages. In C/C++, removing a node requires free() or delete — otherwise the node leaks.
• Cycles cause infinite loops. A traversal that doesn't check for null termination will loop forever if a node's next points back into the list. Use Floyd's tortoise-and-hare to detect cycles in O(n) / O(1).
• Edge cases with the head. Inserting before the head and deleting the head both need special branches because they change the list's external entry point. A sentinel head (an empty dummy node) eliminates both special cases.
• Off-by-one in length tracking. If you maintain a length field, every mutation must update it. Forgetting to decrement on delete is a classic bug that goes undetected for hours.