Singly Linked List

A linked list solves the exact weakness we called out in arrays: inserting near the front of an array costs O(n) because everything after has to shift. A linked list gives up array's O(1) random access in exchange for O(1) insertion and deletion at the head, by storing elements as separate objects connected by references instead of packed into contiguous memory.

Why Linked Lists Exist

The Node Class

Every linked list starts with the same tiny building block: a value, and a reference to the next node.

class Node {
    int val;
    Node next;

    Node(int val) {
        this.val = val;
        this.next = null;
    }
}

Time complexity: O(1) to construct a Node — a fixed amount of field assignment. Space complexity: O(1) per node — one int field and one reference field, regardless of list size.

Insert at Head — O(1)

public void insertAtHead(int val) {
    Node node = new Node(val);
    node.next = head;
    head = node;
    size++;
}

Time complexity: O(1) — no traversal needed; we only touch the new node and the head reference. Space complexity: O(1) — one new node allocated.

Insert at Tail — O(n)

Without a dedicated tail pointer, appending means walking the entire list to find the current last node. (Many production implementations, including Java's own LinkedList, keep a tail reference specifically to make this O(1) — we show the O(n) walk here because it's the version interviewers usually expect you to derive and discuss.)

public void insertAtTail(int val) {
    Node node = new Node(val);
    if (head == null) {
        head = node;
    } else {
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next; // walk to the last node
        }
        curr.next = node;
    }
    size++;
}

Time complexity: O(n) — must traverse all existing nodes to reach the end. Space complexity: O(1) — one new node, no extra structures.

Delete by Value — O(n)

Deletion requires finding the target node first (a scan), and then relinking its predecessor's next pointer to skip over it.

public boolean deleteValue(int val) {
    if (head == null) return false;

    if (head.val == val) { // special case: deleting the head itself
        head = head.next;
        size--;
        return true;
    }

    Node prev = head;
    while (prev.next != null && prev.next.val != val) {
        prev = prev.next;
    }

    if (prev.next == null) return false; // value not found

    prev.next = prev.next.next; // skip over the target node
    size--;
    return true;
}

Time complexity: O(n) — the search for the target (or its absence) requires walking up to the whole list. Space complexity: O(1) — no new nodes allocated, and the old node just becomes eligible for garbage collection.

Traversal — O(n)

public void printAll() {
    Node curr = head;
    while (curr != null) {
        System.out.print(curr.val + " -> ");
        curr = curr.next;
    }
    System.out.println("null");
}

Time complexity: O(n) — visits every node exactly once. Space complexity: O(1) — a single traversal pointer, independent of list length.

Putting It Together — the Full LinkedList Class

public class LinkedList {
    private Node head;
    private int size = 0;

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

    public void insertAtHead(int val) {
        Node node = new Node(val);
        node.next = head;
        head = node;
        size++;
    }

    public void insertAtTail(int val) {
        Node node = new Node(val);
        if (head == null) {
            head = node;
        } else {
            Node curr = head;
            while (curr.next != null) curr = curr.next;
            curr.next = node;
        }
        size++;
    }

    public boolean deleteValue(int val) {
        if (head == null) return false;
        if (head.val == val) { head = head.next; size--; return true; }

        Node prev = head;
        while (prev.next != null && prev.next.val != val) prev = prev.next;
        if (prev.next == null) return false;

        prev.next = prev.next.next;
        size--;
        return true;
    }

    public int size() { return size; } // O(1): maintained incrementally, not recomputed
}

Time complexity: constructing the class itself is O(1); each method carries the complexity noted above it (O(1) for head insert and size, O(n) for tail insert, delete, and any full traversal). Space complexity: O(n) overall for n stored nodes, plus O(1) extra working space per operation.