#707 Design Linked List

frequently reported atMicrosoft Amazon

the problem

In plain words

Write your own MyLinkedList with 0-indexed operations. get(index) returns the value, or -1 if the index is invalid. addAtHead(val) and addAtTail(val) insert at the ends. addAtIndex(index, val) inserts before position index: index equal to the length appends, and a larger index does nothing. deleteAtIndex(index) removes the node if the index is valid. Don't use the built-in LinkedList.

in addAtHead(1), addAtTail(3), addAtIndex(1, 2), get(1), deleteAtIndex(1), get(1)

out null, null, null, 2, null, 3

The list goes [1] → [1, 3] → [1, 2, 3]; get(1) is 2. After deleting index 1 the list is [1, 3], so get(1) is 3.

0 ≤ index, val ≤ 1000
At most 2000 calls in total
Do not use the built-in LinkedList

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternIn-place linked-list rewiring Class design: state + operations

where this runsjava.util.LinkedList is a doubly linked list of private static class Node objects whose get(index) walks from the nearer end, like the optimal approach.

Every operation is "walk to the node before position index, then rewire one or two arrows". A dummy node before the head means position 0 also has a node before it, so no special cases remain.

solutions

From brute force to optimal

Let ArrayList do the indexing.

get: bounds check, then items.get(index).
addAtIndex / addAtHead / addAtTail: items.add(index, val) after checking 0 ≤ index ≤ size.
deleteAtIndex: items.remove(index); the int overload removes by index.

timeget O(1); add or delete at the front or middle O(n)

Inserting or removing shifts every later element by one.

spaceO(n)

The backing array plus a boxed Integer per value.

javajava.util.*

1// On LeetCode, name this class MyLinkedList.2class MyLinkedListArray {3    private final List<Integer> items = new ArrayList<>();4 5    public int get(int index) {6        return index >= 0 && index < items.size() ? items.get(index) : -1;7    }8 9    public void addAtHead(int val) {10        items.add(0, val);                           // shifts every element right: O(n)11    }12 13    public void addAtTail(int val) {14        items.add(val);                              // amortized O(1)15    }16 17    public void addAtIndex(int index, int val) {18        if (index >= 0 && index <= items.size()) items.add(index, val);19    }20 21    public void deleteAtIndex(int index) {22        if (index >= 0 && index < items.size()) items.remove(index);   // remove(int index)23    }24}

A dummy node before the head and a size field; walk prev to the node before index.

Fields: dummy and size.
before(index): start at dummy and step index times.
addAtIndex: check 0 ≤ index ≤ size; node.next = prev.next; prev.next = node; size++.
deleteAtIndex: check 0 ≤ index < size; prev.next = prev.next.next; size--.

timeO(index) per call; addAtTail O(n)

Each call walks from the front to the position.

spaceO(n)

One Node per value.

javajava.util.*

1// On LeetCode, name this class MyLinkedList.2class MyLinkedListSingly {3    private static class Node {4        int val;5        Node next;6 7        Node(int val) {8            this.val = val;9        }10    }11 12    private final Node dummy = new Node(0);          // sentinel before the real head13    private int size = 0;14 15    private Node before(int index) {                 // the node just BEFORE position index16        Node prev = dummy;17        for (int i = 0; i < index; i++) prev = prev.next;18        return prev;19    }20 21    public int get(int index) {22        if (index < 0 || index >= size) return -1;23        return before(index).next.val;24    }25 26    public void addAtHead(int val) {27        addAtIndex(0, val);28    }29 30    public void addAtTail(int val) {31        addAtIndex(size, val);32    }33 34    public void addAtIndex(int index, int val) {35        if (index < 0 || index > size) return;       // index == size means append36        Node prev = before(index);37        Node node = new Node(val);38        node.next = prev.next;                       // link forward first...39        prev.next = node;                            // ...then hook it in40        size++;41    }42 43    public void deleteAtIndex(int index) {44        if (index < 0 || index >= size) return;45        Node prev = before(index);46        prev.next = prev.next.next;                  // the skipped node becomes garbage47        size--;48    }49}

sim

Dry run

loading simulation…

javajava.util.*

1// On LeetCode, name this class MyLinkedList.2class MyLinkedListSingly {3    private static class Node {4        int val;5        Node next;6 7        Node(int val) {8            this.val = val;9        }10    }11 12    private final Node dummy = new Node(0);          // sentinel before the real head13    private int size = 0;14 15    private Node before(int index) {                 // the node just BEFORE position index16        Node prev = dummy;17        for (int i = 0; i < index; i++) prev = prev.next;18        return prev;19    }20 21    public int get(int index) {22        if (index < 0 || index >= size) return -1;23        return before(index).next.val;24    }25 26    public void addAtHead(int val) {27        addAtIndex(0, val);28    }29 30    public void addAtTail(int val) {31        addAtIndex(size, val);32    }33 34    public void addAtIndex(int index, int val) {35        if (index < 0 || index > size) return;       // index == size means append36        Node prev = before(index);37        Node node = new Node(val);38        node.next = prev.next;                       // link forward first...39        prev.next = node;                            // ...then hook it in40        size++;41    }42 43    public void deleteAtIndex(int index) {44        if (index < 0 || index >= size) return;45        Node prev = before(index);46        prev.next = prev.next.next;                  // the skipped node becomes garbage47        size--;48    }49}

head and tail sentinels; walk from whichever end is closer.

Sentinels head ⇄ tail and a size field.
nodeAt(index): walk forward from head if index < size / 2, else backward from tail.
insertBefore(at, val): link the new node between at.prev and at.
delete: node.prev.next = node.next; node.next.prev = node.prev.

timeO(min(index, n − index)); addAtHead and addAtTail O(1)

At most half the list is walked, and the sentinels make both ends instant.

spaceO(n)

Two references per node instead of one.

javajava.util.*

1class MyLinkedList {2    private static class Node {3        int val;4        Node prev;5        Node next;6 7        Node(int val) {8            this.val = val;9        }10    }11 12    private final Node head = new Node(0);           // sentinel before the first node13    private final Node tail = new Node(0);           // sentinel after the last node14    private int size = 0;15 16    public MyLinkedList() {17        head.next = tail;18        tail.prev = head;19    }20 21    private Node nodeAt(int index) {                 // 0 <= index <= size; index == size gives tail22        if (index < size / 2) {                      // closer to the front: walk forward23            Node cur = head.next;24            for (int i = 0; i < index; i++) cur = cur.next;25            return cur;26        }27        Node cur = tail;                             // closer to the back: walk backward28        for (int i = size; i > index; i--) cur = cur.prev;29        return cur;30    }31 32    public int get(int index) {33        if (index < 0 || index >= size) return -1;34        return nodeAt(index).val;35    }36 37    public void addAtHead(int val) {38        insertBefore(head.next, val);39    }40 41    public void addAtTail(int val) {42        insertBefore(tail, val);                     // O(1): no walk at all43    }44 45    public void addAtIndex(int index, int val) {46        if (index < 0 || index > size) return;47        insertBefore(nodeAt(index), val);48    }49 50    public void deleteAtIndex(int index) {51        if (index < 0 || index >= size) return;52        Node node = nodeAt(index);53        node.prev.next = node.next;                  // both neighbours skip the node54        node.next.prev = node.prev;55        size--;56    }57 58    private void insertBefore(Node at, int val) {59        Node node = new Node(val);60        node.prev = at.prev;61        node.next = at;62        at.prev.next = node;63        at.prev = node;64        size++;65    }66}

in the room

How to say it in the interview

talk track

Write the Node class and the fields (dummy, size) first, and say why the dummy node exists.
Write one helper that returns the node before index; every method reuses it.
Insert in the safe order: set the new node's next before changing prev.next.
Test aloud: index 0, index == size (append), index > size (ignored), deleting the last node.

traps

Setting prev.next = node before node.next = prev.next: the rest of the list is lost.
Forgetting size++ or size--, so later bounds checks are wrong.
Using index <= size in get or delete (it must be < size), or index < size in addAtIndex (it must allow == size).

what they ask next

Follow-ups

Why keep a size field instead of counting nodes?

Counting is O(n) per call. A size field makes every bounds check O(1), and the doubly linked version needs it to pick the nearer end.

How does java.util.LinkedList compare?

It is the doubly linked version with first and last fields instead of sentinels, and its internal node(index) walks from the nearer end, just like the optimal approach.

before you submit

Edge cases to test

get or deleteAtIndex on an empty list.
addAtIndex with index == size (append) and with index > size (ignored).
Deleting the head and deleting the tail.
Deleting the only node, then adding again.

practise next