Design Linked List

MediumDesign · Linked List · Sentinel Nodes🧩 Linked List Techniques LeetCode #707 ↗Updated Oct 30, 2026

Problem

Implement your own list class MyLinkedList (0-indexed) without built-in list types. get(i) returns the value at index i or -1 if invalid; addAtHead(v) / addAtTail(v) insert at the ends; addAtIndex(i, v) inserts before index i (appends if i == size, ignored if i > size); deleteAtIndex(i) removes index i if it exists.

InputaddAtHead(1) addAtTail(3) addAtIndex(1,2)Outputlist = 1 → 2 → 3

Inputget(1)Output2

InputdeleteAtIndex(1) get(1)Output3 (list = 1 → 3)

0 ≤ index, val ≤ 1000 · at most 2000 calls · do not use a built-in linked list

Try it yourself

Java

class MyLinkedList {
    public MyLinkedList() {
        
    }

    public int get(int index) {
        
    }

    public void addAtHead(int val) {
        
    }

    public void addAtTail(int val) {
        
    }

    public void addAtIndex(int index, int val) {
        
    }

    public void deleteAtIndex(int index) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Sentinel (dummy) nodes remove every special case for the head and tail: each insert or delete becomes “find the neighbour, relink two pointers”. With a doubly linked list plus a size counter you can also walk from whichever end is closer.

PatternLinked List Techniques

Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.

Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.

Open the Linked List Techniques guide →

Approaches

Brute ForceGrowable Array (Not Really a List)

Time get O(1), add/delete O(n)Space O(n)

Store values in an int[] that doubles when full. Inserting or deleting at index i shifts everything after it by one slot with System.arraycopy. Index checks are the same as in a real list.

Java

class MyLinkedList {
    private int[] data = new int[8];
    private int size = 0;
    public MyLinkedList() {}
    public int get(int index) {
        return index >= 0 && index < size ? data[index] : -1;
    }
    public void addAtHead(int val) { addAtIndex(0, val); }
    public void addAtTail(int val) { addAtIndex(size, val); }
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        if (size == data.length) data = Arrays.copyOf(data, size * 2);
        System.arraycopy(data, index, data, index + 1, size - index); // shift right
        data[index] = val;
        size++;
    }
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        System.arraycopy(data, index + 1, data, index, size - index - 1); // shift left
        size--;
    }
}

Fast random access, but addAtHead is O(n) and it dodges the point of the exercise.

BetterSingly Linked List + Dummy Head

Time O(index) per op, addAtTail O(n)Space O(n)

A dummy node sits before the real head, so the predecessor of index i is always reached by walking i steps from the dummy — even for i = 0. Insert and delete then just relink prev.next. A size field makes bounds checks O(1).

Java

class MyLinkedList {
    private class Node {
        int val; Node next;
        Node(int val, Node next) { this.val = val; this.next = next; }
    }
    private final Node dummy = new Node(0, null); // sits before the real head
    private int size = 0;
    public MyLinkedList() {}
    private Node before(int index) { // node at position index - 1 (dummy for 0)
        Node cur = dummy;
        for (int i = 0; i < index; i++) cur = cur.next;
        return cur;
    }
    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        return before(index).next.val;
    }
    public void addAtHead(int val) { addAtIndex(0, val); }
    public void addAtTail(int val) { addAtIndex(size, val); }
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        Node prev = before(index);
        prev.next = new Node(val, prev.next);
        size++;
    }
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node prev = before(index);
        prev.next = prev.next.next;
        size--;
    }
}

A real linked list with O(1) addAtHead, but every tail operation walks the whole list.

OptimalDoubly Linked List + Two Sentinels

Time O(min(i, n−i)), head/tail O(1)Space O(n)

Sentinels head and tail bracket the real nodes, so every insert is “insert before some node” and every delete unlinks a node whose neighbours always exist. Knowing size, locate index i from the front or the back, whichever is shorter.

Java

class MyLinkedList {
    private class Node {
        int val; Node prev, next;
        Node(int val) { this.val = val; }
    }
    private final Node head = new Node(0), tail = new Node(0); // sentinels
    private int size = 0;
    public MyLinkedList() {
        head.next = tail;
        tail.prev = head;
    }
    private Node nodeAt(int index) { // index == size gives the tail sentinel
        if (index < size / 2) {
            Node cur = head.next;
            for (int i = 0; i < index; i++) cur = cur.next;
            return cur;
        }
        Node cur = tail;
        for (int i = size; i > index; i--) cur = cur.prev;
        return cur;
    }
    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        return nodeAt(index).val;
    }
    public void addAtHead(int val) { insertBefore(head.next, val); }
    public void addAtTail(int val) { insertBefore(tail, val); }
    public void addAtIndex(int index, int val) {
        if (index < 0 || index > size) return;
        insertBefore(nodeAt(index), val);
    }
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node node = nodeAt(index);
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }
    private void insertBefore(Node succ, int val) {
        Node node = new Node(val);
        node.prev = succ.prev;
        node.next = succ;
        succ.prev.next = node;
        succ.prev = node;
        size++;
    }
}

O(1) at both ends and half the walking in the middle — the strongest answer.

Pro tip

Funnel all inserts through one insertBefore helper — fewer pointer updates to get wrong under pressure.

At a glance

Level	Approach	Time	Space
Brute Force	Growable Array (Not Really a List)	`get O(1), add/delete O(n)`	`O(n)`
Better	Singly Linked List + Dummy Head	`O(index) per op, addAtTail O(n)`	`O(n)`
Optimal	Doubly Linked List + Two Sentinels	`O(min(i, n−i)), head/tail O(1)`	`O(n)`

Common pitfalls

Treating addAtIndex(size, v) as invalid — it must append.
Forgetting to update size on one of the paths, which breaks every later bounds check.
Without a dummy head, inserting or deleting at index 0 needs separate code that is easy to get wrong.

Interview tips

Ask singly vs doubly first; then choose sentinels to remove edge cases.
Write a single “find node / predecessor” helper and reuse it everywhere.
Test index 0, index == size, and index > size for each method.

Pattern

Sentinel nodes + size counter → implement list operations without head/tail special cases.

My notes saved in this browser