Linked lists

A linked list keeps its order with arrows instead of positions. Each node holds a value and a pointer to the next node. There's no index, so you walk from the front, but adding or removing a node is just changing an arrow or two.

1. What it is

A linked list is a chain of nodes. Each node stores a value and next, a reference to the following node; the last node's next is None (null). You hold on to the first node, the head. A doubly linked list also gives each node a prev pointer, so you can walk both ways.

• Fast: inserting or removing at the head, or right after a node you already have: O(1), no shifting.
• Slow: reaching the i-th node or searching: O(n), you walk from the head.
• Where you meet them: interview problems hand you a head; real systems use them inside queues, LRU caches and hash-map buckets.

2. How it sits in memory

Unlike an array, the nodes can be anywhere in memory. Each one remembers the address of the next. That's why you can't jump to node i: you only know where node i is once node i − 1 tells you.

Inserting after a node changes two arrows, and the order matters: first point the new node at the rest of the list, then point the old node at the new one. Do it the other way round and the rest of the list is lost.

3. Operations and what they cost

4. In Python, TypeScript and Java

Python and TypeScript have no built-in singly linked list, so interview problems define the node class for you. Java has LinkedList (doubly linked), but problems still use a ListNode.

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

    head = ListNode(1, ListNode(2, ListNode(3)))   # 1 → 2 → 3
    node = head
    while node:                  # walk to the end
        print(node.val)
        node = node.next

    from collections import deque  # a ready-made doubly linked queue
    q = deque([1, 2, 3]); q.appendleft(0); q.pop()

class ListNode {
      val: number; next: ListNode | null;
      constructor(val = 0, next: ListNode | null = null) { this.val = val; this.next = next; }
    }
    const head = new ListNode(1, new ListNode(2, new ListNode(3)));
    let node: ListNode | null = head;
    while (node) { console.log(node.val); node = node.next; }

class ListNode {
        int val; ListNode next;
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
    ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, null)));
    for (ListNode node = head; node != null; node = node.next) System.out.println(node.val);

    LinkedList<Integer> list = new LinkedList<>(List.of(1, 2, 3));   // doubly linked
    list.addFirst(0); list.removeLast();

5. Core operations, step by step

Three moves cover almost every linked-list problem: walk it, splice a node in, and cut a node out.

def total(head):
    s = 0
    node = head
    while node:
        s += node.val
        node = node.next
    return s

function total(head: ListNode | null): number {
  let s = 0;
  let node = head;
  while (node) {
    s += node.val;
    node = node.next;
  }
  return s;
}

static int total(ListNode head) {
    int s = 0;
    ListNode node = head;
    while (node != null) {
        s += node.val;
        node = node.next;
    }
    return s;
}

def insert_after(head, target, val):
    prev = head
    while prev.val != target:
        prev = prev.next
    node = ListNode(val)
    node.next = prev.next
    prev.next = node
    return head

function insertAfter(head: ListNode, target: number, val: number): ListNode {
  let prev = head;
  while (prev.val !== target) {
    prev = prev.next!;
  }
  const node = new ListNode(val);
  node.next = prev.next;
  prev.next = node;
  return head;
}

static ListNode insertAfter(ListNode head, int target, int val) {
    ListNode prev = head;
    while (prev.val != target) {
        prev = prev.next;
    }
    ListNode node = new ListNode(val, null);
    node.next = prev.next;
    prev.next = node;
    return head;
}

def delete_value(head, val):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next and prev.next.val != val:
        prev = prev.next
    if prev.next:
        prev.next = prev.next.next
    return dummy.next

function deleteValue(head: ListNode | null, val: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  while (prev.next && prev.next.val !== val) {
    prev = prev.next;
  }
  if (prev.next) {
    prev.next = prev.next.next;
  }
  return dummy.next;
}

static ListNode deleteValue(ListNode head, int val) {
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;
    while (prev.next != null && prev.next.val != val) {
        prev = prev.next;
    }
    if (prev.next != null) {
        prev.next = prev.next.next;
    }
    return dummy.next;
}

6. How to remember it

7. Problems solved with it

Two easy problems using exactly the moves above.

def get_decimal_value(head):
    value = 0
    node = head
    while node:
        value = value * 2 + node.val
        node = node.next
    return value

function getDecimalValue(head: ListNode | null): number {
  let value = 0;
  let node = head;
  while (node) {
    value = value * 2 + node.val;
    node = node.next;
  }
  return value;
}

static int getDecimalValue(ListNode head) {
    int value = 0;
    ListNode node = head;
    while (node != null) {
        value = value * 2 + node.val;
        node = node.next;
    }
    return value;
}

def remove_elements(head, val):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next:
        if prev.next.val == val:
            prev.next = prev.next.next
        else:
            prev = prev.next
    return dummy.next

function removeElements(head: ListNode | null, val: number): ListNode | null {
  const dummy = new ListNode(0, head);
  let prev = dummy;
  while (prev.next) {
    if (prev.next.val === val) {
      prev.next = prev.next.next;
    } else {
      prev = prev.next;
    }
  }
  return dummy.next;
}

static ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;
    while (prev.next != null) {
        if (prev.next.val == val) {
            prev.next = prev.next.next;
        } else {
            prev = prev.next;
        }
    }
    return dummy.next;
}

More practice, solved on the pattern pages

8. Common mistakes

9. Self-check quiz

10. Where it shows up next

• 04 · Fast & Slow Pointers: two fingers at different speeds find the middle and detect cycles.
• 05 · LinkedList In-place Reversal: reversing all or part of a list by flipping arrows.
• 19 · Trie & Design: an LRU cache is a hash map plus a doubly linked list.

Next structure: 06 · Stacks, last in, first out.