Adding and Removing Nodes

Our own linked list class

We wrap the nodes in a class that remembers the head. Adding at the front just makes a new node point at the old head. Removing a node just makes the node before it skip over it:

class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
}

class MyLinkedList {
    Node head;

    void addFirst(int v) {                // O(1)
        Node n = new Node(v);
        n.next = head;
        head = n;
    }

    void addLast(int v) {                 // O(n): walk to the end first
        Node n = new Node(v);
        if (head == null) { head = n; return; }
        Node cur = head;
        while (cur.next != null) cur = cur.next;
        cur.next = n;
    }

    boolean remove(int v) {               // remove the first node with value v
        if (head == null) return false;
        if (head.value == v) { head = head.next; return true; }
        Node cur = head;
        while (cur.next != null && cur.next.value != v) cur = cur.next;
        if (cur.next == null) return false;
        cur.next = cur.next.next;         // skip over it
        return true;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (Node cur = head; cur != null; cur = cur.next) sb.append(cur.value).append(" -> ");
        return sb.append("null").toString();
    }
}

public class Main {
    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        list.addLast(20);
        list.addLast(30);
        list.addFirst(10);
        System.out.println(list);
        list.remove(20);
        System.out.println(list);
        System.out.println(list.remove(99));
    }
}

Output

10 -> 20 -> 30 -> null
10 -> 30 -> null
false

Tip: Draw boxes and arrows on paper before changing next. Ask: what does each arrow point to before and after? Most linked list bugs are an arrow changed in the wrong order.

Java's own LinkedList

java.util.LinkedList is a doubly linked list (each node also points back). It has addFirst, addLast, removeFirst, removeLast – all O(1). But get(i) is O(n), so never loop over one with get(i).

Common mistake: Calling a method on null – for example cur.next.value when cur.next is null – stops the program with NullPointerException. Check for null first.