Start practising

Design Linked List

Medium Design Data Structures Linked Lists Original on LeetCode

Design Linked List is a medium design data structures problem solved with the linked lists pattern. The best approach, dummy head + size counter, runs in O(index) per operation time and O(n) space. Below are 2 approaches in Java, from singly linked list without a dummy up.

Problem

Implement your own linked list with get(index), addAtHead(val), addAtTail(val), addAtIndex(index, val) and deleteAtIndex(index), using 0-based indices.

Examples

Example 1

Input
addAtHead(1); addAtTail(3); addAtIndex(1, 2); get(1); deleteAtIndex(1); get(1)
Output
2, 3
Why
List goes 1 → 1,3 → 1,2,3 → 1,3.

Constraints

  • 0 <= index, val <= 1000; at most 2000 calls.
  • Invalid indices: get returns -1; add/delete do nothing.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Singly linked list without a dummyO(index) per operationO(n)
Dummy head + size counterO(index) per operationO(n)

1Singly linked list without a dummy

TimeO(index) per operation
SpaceO(n)

Handle index 0 separately for add and delete, and walk to index - 1 otherwise. It works, but has more branches.

  1. Special-case index 0; otherwise walk to the predecessor.
Java
class MyLinkedList {
    private static class Node { int val; Node next; Node(int v, Node n) { val = v; next = n; } }
    private Node head;
    private int size;

    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node p = head;
        for (int i = 0; i < index; i++) p = p.next;
        return p.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;
        if (index == 0) head = new Node(val, head);
        else {
            Node p = head;
            for (int i = 0; i < index - 1; i++) p = p.next;
            p.next = new Node(val, p.next);
        }
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        if (index == 0) head = head.next;
        else {
            Node p = head;
            for (int i = 0; i < index - 1; i++) p = p.next;
            p.next = p.next.next;
        }
        size--;
    }
}

2Dummy head + size counter

TimeO(index) per operation
SpaceO(n)

A permanent dummy node sits before index 0, so the predecessor of any index is reached by walking index steps from the dummy. One code path handles head, middle and tail.

  1. prev(index) = walk index steps from dummy.
  2. add: prev.next = new Node(val, prev.next). delete: prev.next = prev.next.next.
Java
class MyLinkedList {
    private static class Node { int val; Node next; Node(int v, Node n) { val = v; next = n; } }
    private final Node dummy = new Node(0, null);
    private int size;

    private Node prev(int index) {
        Node p = dummy;
        for (int i = 0; i < index; i++) p = p.next;
        return p;
    }

    public int get(int index) {
        return index < 0 || index >= size ? -1 : prev(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 p = prev(index);
        p.next = new Node(val, p.next);
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node p = prev(index);
        p.next = p.next.next;
        size--;
    }
}

Edge cases to test

  • addAtIndex(size, val) appends to the tail
  • Deleting the head or the tail
  • Index out of range

Hints

Hint 1

A dummy head removes every head special case, and a size counter makes index checks O(1).

FAQ

What is the best time complexity for Design Linked List?

Dummy head + size counter runs in O(index) per operation time and O(n) extra space.

Which pattern does Design Linked List use?

It is a design data structures problem that uses the linked lists pattern. Other problems with the same pattern: Design Front Middle Back Queue.

Is there a brute force solution for Design Linked List?

Yes. Singly linked list without a dummy takes O(index) per operation time and O(n) space. Handle index 0 separately for add and delete, and walk to index - 1 otherwise.

Which edge cases should I test for Design Linked List?

addAtIndex(size, val) appends to the tail; Deleting the head or the tail; Index out of range.