Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Introduction to Linked Lists

Editorial

A chain of clues

Picture a treasure hunt. The first clue tells you where the second one is hidden, the second tells you where the third is, and so on. To read the fifth clue you have to find the first four. And if someone throws away the third clue, the fourth and fifth are as good as gone, because nothing else says where they are.

A linked list is that hunt. Each value lives in a node, and the node also holds the address of the next node: a pointer called next. The last node's next is null. All you keep is a pointer to the first node, the head, and every other node is reached by following next from there.

Top: an array holding 3, 7, 1, 5 and 8 in one block of memory at addresses 100, 104, 108, 112 and 116, so a[3] is found in one step at 100 + 3 × 4. Bottom: a linked list holding 3, 7, 1 and 5 in nodes scattered across memory at addresses 720, 312, 948 and 456. Each node holds its value and the next node's address; head points to the node holding 3, the last node's next is null, and the arrows number the three hops it takes to reach the fourth node.

Here's the node, and a walk that prints the list and one that counts it. Both walk with their own pointer, curr, so head stays where it is:

struct Node {
    int val;
    Node* next;
    Node(int v, Node* n = nullptr) : val(v), next(n) {}
};

string show(Node* head) {
    string out;
    for (Node* curr = head; curr != nullptr; curr = curr->next)   // a copy walks; head stays put
        out += to_string(curr->val) + " -> ";
    return out + "null";
}

int length(Node* head) {
    int count = 0;
    for (Node* curr = head; curr != nullptr; curr = curr->next)
        count++;
    return count;
}

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

def show(head):
    parts = []
    curr = head                         # a copy walks; head stays put
    while curr is not None:
        parts.append(str(curr.val))
        curr = curr.next
    return " -> ".join(parts + ["null"])

def length(head):
    count, curr = 0, head
    while curr is not None:
        count += 1
        curr = curr.next
    return count

static class Node {
    int val;
    Node next;
    Node(int val, Node next) { this.val = val; this.next = next; }
}

static String show(Node head) {
    StringBuilder out = new StringBuilder();
    for (Node curr = head; curr != null; curr = curr.next)   // a copy walks; head stays put
        out.append(curr.val).append(" -> ");
    return out.append("null").toString();
}

static int length(Node head) {
    int count = 0;
    for (Node curr = head; curr != null; curr = curr.next)
        count++;
    return count;
}

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

function show(head) {
    const parts = [];
    for (let curr = head; curr !== null; curr = curr.next)   // a copy walks; head stays put
        parts.push(String(curr.val));
    return [...parts, "null"].join(" -> ");
}

function length(head) {
    let count = 0;
    for (let curr = head; curr !== null; curr = curr.next)
        count++;
    return count;
}

With 3 → 7 → 1 built by hand, each one printed 3 -> 7 -> 1 -> null and a length of 3. An empty list is just a head that's null: null and 0.

Walking costs a step per node

There's no index. To reach the fifth node you start at the head and follow next four times: the node at index k is k steps away, where an array jumps straight to it. Counting the nodes is the same walk:

Walk the list and count it — curr moves one node per step; the teal nodes are counted. head never moves.

On our judge, walking to node 500,000 of a 1,000,000-node list took 43.9 ms in Python, and reading index 500,000 of a Python list took 0.13 µs.

Big-O hides a second gap. Summing 4,000,000 ints in C++: an array took 2.5 ms, a linked list whose nodes sat in order in memory 9.0 ms, and the same list with its nodes scattered 436.5 ms. All three do the same O(n) work. The scattered list jumps to a far-off address at every node, and each jump misses the CPU's cache, which loads the memory next to whatever was just read. An array's next value is always right next door.

Inserting: two writes, in the right order

Inserting a node moves nothing. You hold the node just before the spot and change two pointers: the new node points to whatever came next, then the node before points to the new one.

The order is the whole trick. Before the insert, the node before the spot holds the only pointer to the rest of the list. Overwrite it first, and the rest is gone before the new node can pick it up:

curr = head.next                # holds 2 in 1 -> 2 -> 3 -> 4
node = Node(9)

node.next = curr.next           # right: the new node takes the rest of the list first,
curr.next = node                # then 2 points to it

# wrong, in the other order:
# curr.next = node              # the only pointer to 3 is gone
# node.next = curr.next         # and curr.next is now 9 itself

Run on 1 → 2 → 3 → 4, the right order printed 1 -> 2 -> 9 -> 3 -> 4 -> null. The wrong order printed 1 -> 2 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> ..., and we had to cut it off: after curr.next = node, curr.next is the new node, so node.next = curr.next points 9 at itself, and nothing points to 3 or 4 any more.

Two ways to insert 9 after 2 in the list 1, 2, 3, 4. Right order: first node.next = curr.next points 9 at 3, then curr.next = node points 2 at 9, giving 1, 2, 9, 3, 4. Wrong order: curr.next = node first overwrites the only pointer to 3, so 3 and 4 are lost, and node.next = curr.next then points 9 at itself.

To insert at index p, stop on the node before it: p − 1 steps from the head. Index 0 has no node before it, and that's the case first attempts get wrong. A dummy node fixes it: a spare node placed in front of the head, so every position, the first one included, has a node before it. Walk from the dummy, and return dummy.next, which is the new head if the head changed.

Insert at an index, from a dummy — The dashed box is the dummy. prev walks to the node before the index; the new node waits below until both writes are done, and each green arrow is the write just made.

Node* insertAt(Node* head, int index, int val) {
    Node dummy(0, head);                 // a node before the head: every position has one before it
    Node* prev = &dummy;
    for (int k = 0; k < index; k++)      // stop on the node before position index
        prev = prev->next;
    Node* node = new Node(val);
    node->next = prev->next;             // 1. the new node takes the rest of the list
    prev->next = node;                   // 2. then prev points to the new node
    return dummy.next;                   // the head may have changed
}

Node* removeAll(Node* head, int target) {
    Node dummy(0, head);
    Node* prev = &dummy;
    while (prev->next != nullptr) {
        if (prev->next->val == target) {
            Node* gone = prev->next;
            prev->next = gone->next;     // skip it; prev stays, the new prev->next may match too
            delete gone;
        } else {
            prev = prev->next;
        }
    }
    return dummy.next;
}

def insert_at(head, index, val):
    dummy = Node(0, head)               # a node before the head: every position has one before it
    prev = dummy
    for _ in range(index):              # stop on the node before position index
        prev = prev.next
    node = Node(val)
    node.next = prev.next               # 1. the new node takes the rest of the list
    prev.next = node                    # 2. then prev points to the new node
    return dummy.next                   # the head may have changed

def remove_all(head, target):
    dummy = Node(0, head)
    prev = dummy
    while prev.next is not None:
        if prev.next.val == target:
            prev.next = prev.next.next  # skip it; prev stays, the new prev.next may match too
        else:
            prev = prev.next
    return dummy.next

static Node insertAt(Node head, int index, int val) {
    Node dummy = new Node(0, head);      // a node before the head: every position has one before it
    Node prev = dummy;
    for (int k = 0; k < index; k++)      // stop on the node before position index
        prev = prev.next;
    Node node = new Node(val, null);
    node.next = prev.next;               // 1. the new node takes the rest of the list
    prev.next = node;                    // 2. then prev points to the new node
    return dummy.next;                   // the head may have changed
}

static Node removeAll(Node head, int target) {
    Node dummy = new Node(0, head);
    Node prev = dummy;
    while (prev.next != null) {
        if (prev.next.val == target)
            prev.next = prev.next.next;  // skip it; prev stays, the new prev.next may match too
        else
            prev = prev.next;
    }
    return dummy.next;
}

function insertAt(head, index, val) {
    const dummy = new Node(0, head);     // a node before the head: every position has one before it
    let prev = dummy;
    for (let k = 0; k < index; k++)      // stop on the node before position index
        prev = prev.next;
    const node = new Node(val);
    node.next = prev.next;               // 1. the new node takes the rest of the list
    prev.next = node;                    // 2. then prev points to the new node
    return dummy.next;                   // the head may have changed
}

function removeAll(head, target) {
    const dummy = new Node(0, head);
    let prev = dummy;
    while (prev.next !== null) {
        if (prev.next.val === target)
            prev.next = prev.next.next;  // skip it; prev stays, the new prev.next may match too
        else
            prev = prev.next;
    }
    return dummy.next;
}

Each printed 10 -> 20 -> 99 -> 30 -> 40 -> null, 5 -> 10 -> 20 -> 30 -> 40 -> null, 7 -> null for inserts at index 2, at index 0 and into an empty list, then 1 -> 2 -> null, null, null for removing every 6 from [6, 1, 6, 6, 2], from [6, 6] and from an empty list. How the removal works is next.

Deleting: skip the node

Deleting is one write from the node before: prev.next = prev.next.next. Nothing points to the skipped node after that. Java, Python and JavaScript free it on their own; C++ code deletes it.

The dummy covers the head here too. remove_all above removes every node holding a value, and when it removes one, prev stays where it is, because the node now after it is new and hasn't been checked:

Remove every 6, from a dummy — prev is indigo. Removed nodes turn red and dashed; their old pointers fade. Each green arrow is the write just made.

One problem turns this around. Delete Node in a Linked List hands you only the node to delete, never the head and never the tail, so there's no node before it to rewrite. The way out: copy the next node's value into this one, then skip the next node.

def delete_node(node):                # node is never the tail
    node.val = node.next.val            # become the next node...
    node.next = node.next.next          # ...and skip it

Deleting the 5 from 4 → 5 → 1 → 9 this way left 4 -> 1 -> 9 -> null.

Now you write the pointers

Each task below is a real list. Pick the pointer to change, then what it should point to; the write runs on the spot, and any node that nothing points to any more fades out. In the first task, try the wrong order on purpose, then undo it. The dummy task is the one to remember: the head stops being a special case.

Rewire the Links: write the pointers for each change, one write at a time

Doubly linked lists

A doubly linked node also points back to the node before it, through prev. That costs one pointer per node and buys two things: you can walk backwards, and you can remove a node you're holding without walking to the one before it, because it knows both neighbours.

Inserting between two nodes takes four writes. The new node's own two pointers go first, since they overwrite nothing. Then the neighbours, and of those, the one reached through node.next goes before node.next itself changes:

Insert into a doubly linked list — next pointers run above, prev pointers below. The new node waits under the gap; each green arrow is the write just made.

Real implementations put two sentinel nodes at the ends, a dummy head and a dummy tail, so every real node has a neighbour on both sides and no write ever meets null. LRU Cache is built exactly like this, with a hash map to find each node:

struct DNode {
    int val;
    DNode* prev = nullptr;
    DNode* next = nullptr;
    explicit DNode(int v = 0) : val(v) {}
};

struct DoublyLinkedList {
    DNode* head = new DNode();           // sentinels: the real nodes always sit between them
    DNode* tail = new DNode();

    DoublyLinkedList() {
        head->next = tail;
        tail->prev = head;
    }

    DNode* insertAfter(DNode* node, int val) {
        DNode* fresh = new DNode(val);
        fresh->prev = node;              // the new node's two links first: they overwrite nothing
        fresh->next = node->next;
        node->next->prev = fresh;        // then the neighbours, the far one before node->next changes
        node->next = fresh;
        return fresh;
    }

    void remove(DNode* node) {           // O(1): the node knows both neighbours
        node->prev->next = node->next;
        node->next->prev = node->prev;
        delete node;
    }

    vector<int> forward() const {
        vector<int> out;
        for (DNode* curr = head->next; curr != tail; curr = curr->next) out.push_back(curr->val);
        return out;
    }

    vector<int> backward() const {
        vector<int> out;
        for (DNode* curr = tail->prev; curr != head; curr = curr->prev) out.push_back(curr->val);
        return out;
    }
};

class DNode:
    def __init__(self, val=None):
        self.val = val
        self.prev = None
        self.next = None

class DoublyLinkedList:
    def __init__(self):
        self.head = DNode()             # sentinels: the real nodes always sit between them
        self.tail = DNode()
        self.head.next = self.tail
        self.tail.prev = self.head

    def insert_after(self, node, val):
        new = DNode(val)
        new.prev = node                 # the new node's two links first: they overwrite nothing
        new.next = node.next
        node.next.prev = new            # then the neighbours, the far one before node.next changes
        node.next = new
        return new

    def remove(self, node):             # O(1): the node knows both neighbours
        node.prev.next = node.next
        node.next.prev = node.prev

    def forward(self):
        out, curr = [], self.head.next
        while curr is not self.tail:
            out.append(curr.val)
            curr = curr.next
        return out

    def backward(self):
        out, curr = [], self.tail.prev
        while curr is not self.head:
            out.append(curr.val)
            curr = curr.prev
        return out

static class DNode {
    int val;
    DNode prev, next;
    DNode(int val) { this.val = val; }
}

static class DoublyLinkedList {
    final DNode head = new DNode(0), tail = new DNode(0);   // sentinels: real nodes sit between them

    DoublyLinkedList() {
        head.next = tail;
        tail.prev = head;
    }

    DNode insertAfter(DNode node, int val) {
        DNode fresh = new DNode(val);
        fresh.prev = node;               // the new node's two links first: they overwrite nothing
        fresh.next = node.next;
        node.next.prev = fresh;          // then the neighbours, the far one before node.next changes
        node.next = fresh;
        return fresh;
    }

    void remove(DNode node) {            // O(1): the node knows both neighbours
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    List<Integer> forward() {
        List<Integer> out = new ArrayList<>();
        for (DNode curr = head.next; curr != tail; curr = curr.next) out.add(curr.val);
        return out;
    }

    List<Integer> backward() {
        List<Integer> out = new ArrayList<>();
        for (DNode curr = tail.prev; curr != head; curr = curr.prev) out.add(curr.val);
        return out;
    }
}

class DNode {
    constructor(val = null) {
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

class DoublyLinkedList {
    constructor() {
        this.head = new DNode();         // sentinels: the real nodes always sit between them
        this.tail = new DNode();
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    insertAfter(node, val) {
        const fresh = new DNode(val);
        fresh.prev = node;               // the new node's two links first: they overwrite nothing
        fresh.next = node.next;
        node.next.prev = fresh;          // then the neighbours, the far one before node.next changes
        node.next = fresh;
        return fresh;
    }

    remove(node) {                       // O(1): the node knows both neighbours
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    forward() {
        const out = [];
        for (let curr = this.head.next; curr !== this.tail; curr = curr.next) out.push(curr.val);
        return out;
    }

    backward() {
        const out = [];
        for (let curr = this.tail.prev; curr !== this.head; curr = curr.prev) out.push(curr.val);
        return out;
    }
}

Each printed [1, 2, 9, 3] [3, 9, 2, 1], then [1, 9, 3] [3, 9, 1] after removing 2. Forward and backward agree, and that's the check to run on any doubly linked code you write.

A circular list's last node points back to the first instead of to null. With no null to stop at, a walk stops when it comes back to where it started:

def show_circular(start):
    parts, curr = [], start
    while True:
        parts.append(str(curr.val))
        curr = curr.next
        if curr is start:               # back where it started: there's no null to stop at
            break
    return " -> ".join(parts) + " -> (back to " + str(start.val) + ")"

On 1 → 2 → 3 with the last node pointing back to the first, it printed 1 -> 2 -> 3 -> (back to 1).

Array or linked list?

ArrayLinked list
Read the kth valueO(1)O(k): walk from the head
Insert or delete next to a node you holdO(n): shift what followsO(1): one or two writes
Insert or delete at the frontO(n)O(1)
Memory for one int (C++)4 bytes16 bytes a node, plus the allocator's own
Walk all of itone block: 2.5 ms for 4,000,000436.5 ms when the nodes are scattered

So an array (a vector, an ArrayList, a Python list) is the default. A linked list earns its place when you already hold the node and need it in or out in O(1): an LRU cache, an undo history, a queue. In an interview you rarely choose; the problem hands you a head.

Spotting it. The statement gives you head and a node class. Then the wording tells you what to reach for:

  • "return the head of the modified list": the head can change, so start from a dummy;
  • "you are given only the node": copy the next value in and skip the next node;
  • "in O(1) extra space": rewire the pointers you have instead of copying.

The near-miss. When extra space is allowed, copying the values into an array is a fair first answer for many list problems. Say it out loud as your brute force, then do the pointer version.

Bugs that cost a submission

The two writes in the wrong order. curr.next = node before node.next = curr.next: on 1 → 2 → 3 → 4 it printed 1 -> 2 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> 9 -> ..., with 9 pointing at itself and 3 and 4 lost.

Moving on after a removal. Here prev advances even when it just removed a node:

def remove_all(head, target):
    dummy = Node(0, head)
    prev = dummy
    while prev.next is not None:
        if prev.next.val == target:
            prev.next = prev.next.next
        prev = prev.next                # moves on even after a removal
    return dummy.next

On [1, 6, 6, 2] it returned 1 -> 6 -> 2 -> null: the second 6 was never checked. On [1, 6] it crashed with AttributeError, because removing the last node left prev.next null and the loop then read from it.

Stopping on the node instead of the one before it.

def insert_at(head, index, val):
    curr = head
    for _ in range(index):              # walks onto the node at index, one too far
        curr = curr.next
    node = Node(val)
    node.next = curr.next
    curr.next = node
    return head

Inserting 99 at index 2 of [10, 20, 30, 40] gave 10 -> 20 -> 30 -> 99 -> 40 -> null: one place late. Walk index − 1 steps, or walk index steps from a dummy.

Changing head inside a function.

def push_front(head, val):
    node = Node(val, head)
    head = node                         # changes this function's own head only

After push_front(head, 0) the caller's list still printed 1 -> 2 -> null. Java, Python and JavaScript pass the reference by value, and so does C++ with a plain Node*: in C++, by value printed 1 -> 2 -> null and with Node*& printed 0 -> 1 -> 2 -> null. Return the new head instead.

The empty list. This version checks the head and then walks curr.next:

static Node removeFirst(Node head, int target) {
    if (head != null && head.val == target) return head.next;   // the head, as a special case
    Node curr = head;                                           // null when the list is empty...
    while (curr.next != null && curr.next.val != target)       // ...and this reads null.next
        curr = curr.next;
    if (curr.next != null) curr.next = curr.next.next;
    return head;
}

Given an empty list it threw a NullPointerException, because curr was null. The dummy version returned null.

A missing prev write. An insert into a doubly linked list that skips node.next.prev = new printed [1, 9, 2, 3] [3, 2, 1]: the forward walk is right and the backward walk misses 9. Printing only forward hides it, so walk both ways.

Check yourself

Quiz

1 / 6

Multiple choice

curr holds 2 in 1 → 2 → 3, and node holds a new 9 to go after it. Which write comes first?

Practice problems

From easier to harder:

  1. Linked List Fundamentals: build a list and walk it.
  2. Length of a linked list: the walk, counting.
  3. Search in Linked List: the walk, comparing.
  4. Insertion at a Given Position in a Linked List: stop one node early, or start from a dummy.
  5. Delete Node in a Linked List: you hold only the node.

Doubly linked:

  1. Doubly Linked List Fundamentals: both directions, and the null at each end.
  2. Inserting into a Doubly Linked List: the four writes.
  3. Deleting from a Doubly Linked List: the two writes.
  4. Find pairs with given sum in doubly linked list: a pointer from each end of a sorted list.
  5. Flatten a Multilevel Doubly Linked List: splice a child list in, all four writes.
  6. Delete all occurrences of a given key in a doubly linked list: removing while you walk.
  7. Remove duplicates from a sorted doubly linked list: the same, against the previous value.

Next, Reversing a Linked List: turning every pointer around in one pass.