Design Linked List

Medium Design Data Structures Linked Lists Original on LeetCode

Reported atTCSAirtel

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, Python, C++ and JavaScript, 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.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (1 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

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 code in Java, Python, C++ and JavaScript.

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.
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.
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, LRU Cache, All O`one Data Structure.

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.