Design Linked List — Build One from Scratch, Interview Style

Problem Statement#

LeetCode 707 — Design Linked List Difficulty: Medium | Pattern: Data Structure Design

Design your implementation of the linked list. You can choose to use a singly or doubly linked list. Implement the MyLinkedList class:

• get(index) — Return the value of the indexth node. Return -1 if the index is invalid.
• addAtHead(val) — Add a node of value val before the first element.
• addAtTail(val) — Append a node of value val as the last element.
• addAtIndex(index, val) — Add before the indexth node. If index == length, append. If index > length, do not insert.
• deleteAtIndex(index) — Delete the indexth node if the index is valid.

Constraints:

• 0 <= index, val <= 1000
• At most 2000 calls will be made to all methods.

Example:

MyLinkedList list = new MyLinkedList();
list.addAtHead(1);       // list: [1]
list.addAtTail(3);       // list: [1, 3]
list.addAtIndex(1, 2);   // list: [1, 2, 3]
list.get(1);             // returns 2
list.deleteAtIndex(1);   // list: [1, 3]
list.get(1);             // returns 3

Why This Problem Matters#

Designing a linked list from scratch separates candidates who truly understand data structures from those who have only used them as a black box. Amazon, Google, and Microsoft use this problem (or close variants) in early-stage interviews to verify that a candidate has genuine programming fundamentals before moving on to system design or harder algorithmic questions.

Unlike questions where you simply traverse a given list, this problem asks you to build the machinery itself — managing node creation, pointer updates, boundary conditions, and size tracking. Every addAtIndex call has four edge cases. Every deleteAtIndex has two. Getting all of them right under pressure is a genuine test of attention to detail and pointer discipline.

In system design interviews, the follow-up is often "how would you implement a doubly linked list?" or "how does Python's deque work internally?" The doubly linked list variant is directly used in the LRU Cache problem (LC 146), one of the most frequently asked hard design questions at top tech companies.

Learning to implement a linked list cleanly — especially using a sentinel dummy head node — is a skill that pays dividends across dozens of interview problems involving linked list manipulation.

The Core Insight#

The cleanest implementation uses a sentinel (dummy) head node. This is a node that always exists at position -1 and holds no real value. Its only purpose is to eliminate the special case of inserting or deleting at the actual head of the list.

Without a dummy head, every addAtHead and deleteAtIndex(0) requires a separate code path that is easy to mess up. With a dummy head, every insertion becomes "find the node at index - 1 and splice in," and every deletion becomes "find the node at index - 1 and skip the next node." The code becomes uniform.

Also maintain a size counter. Updating it on every mutation and checking it at the start of every method catches out-of-bounds indices before any pointer manipulation happens — this avoids null pointer crashes in the middle of an operation.

Visual Dry Run#

Starting state: dummy -> null (size = 0)

addAtHead(1):     dummy -> [1] -> null           size=1
addAtTail(3):     dummy -> [1] -> [3] -> null    size=2
addAtIndex(1,2):  dummy -> [1] -> [2] -> [3] -> null   size=3
get(1):           traverse to index 1 -> value=2
deleteAtIndex(1): dummy -> [1] -> [3] -> null    size=2
get(1):           traverse to index 1 -> value=3

For addAtIndex(1, 2) — finding the predecessor at index 0:

Solution (Optimal)#

class ListNode:
    def __init__(self, val=0):
        self.val = val
        self.next = None
 
class MyLinkedList:
    def __init__(self):
        self.dummy = ListNode(0)  # sentinel head
        self.size = 0
 
    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1
        curr = self.dummy.next
        for _ in range(index):
            curr = curr.next
        return curr.val
 
    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)
 
    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)
 
    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        index = max(0, index)  # treat negative index as 0
        # Walk to predecessor at position (index - 1) from dummy
        pred = self.dummy
        for _ in range(index):
            pred = pred.next
        node = ListNode(val)
        node.next = pred.next
        pred.next = node
        self.size += 1
 
    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        pred = self.dummy
        for _ in range(index):
            pred = pred.next
        pred.next = pred.next.next
        self.size -= 1

class ListNode {
    constructor(val = 0) {
        this.val = val;
        this.next = null;
    }
}
 
class MyLinkedList {
    constructor() {
        this.dummy = new ListNode(0); // sentinel head
        this.size = 0;
    }
 
    get(index) {
        if (index < 0 || index >= this.size) return -1;
        let curr = this.dummy.next;
        for (let i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr.val;
    }
 
    addAtHead(val) {
        this.addAtIndex(0, val);
    }
 
    addAtTail(val) {
        this.addAtIndex(this.size, val);
    }
 
    addAtIndex(index, val) {
        if (index > this.size) return;
        index = Math.max(0, index);
        let pred = this.dummy;
        for (let i = 0; i < index; i++) {
            pred = pred.next;
        }
        const node = new ListNode(val);
        node.next = pred.next;
        pred.next = node;
        this.size++;
    }
 
    deleteAtIndex(index) {
        if (index < 0 || index >= this.size) return;
        let pred = this.dummy;
        for (let i = 0; i < index; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
        this.size--;
    }
}

Complexity:

Common Mistakes#

1. Skipping the dummy head: Without a sentinel, inserting or deleting at index 0 requires a special case that is easy to bungle under pressure.
2. Not maintaining size: Without a size counter, validating every index requires an O(n) scan, and off-by-one errors are easy to introduce.
3. Forgetting to update size on every mutation: Forgetting to increment or decrement on add or delete leads to incorrect boundary checks later.
4. Confusing get traverse vs add traverse: get(index) walks to the node itself (loop index times from dummy.next). addAtIndex(index) walks to the predecessor (loop index times from dummy).
5. Ignoring negative index in addAtIndex: The problem allows negative index to mean insert at head — handle with max(0, index).

Interview Tips#

• State your design choice upfront: "I'll use a singly linked list with a dummy head and a size counter to eliminate edge cases."
• Explain the dummy head insight: Showing you understand why it simplifies code demonstrates genuine data structure knowledge.
• Unify addAtHead and addAtTail: Tell the interviewer they are just addAtIndex(0) and addAtIndex(size) — no duplicate code.
• Offer the doubly linked list extension: If they ask about O(1) addAtTail, propose a tail pointer. If they ask about O(1) deletion given a node reference, propose a doubly linked list.
• Discuss real-world usage: Python's collections.deque, Java's LinkedList, and the LRU Cache all use doubly linked lists internally.

Follow-up Questions#

1. Implement a doubly linked list: Add prev pointers so deletion of a node is O(1) given a reference to that node.
2. Support O(1) addAtTail: Store a tail pointer alongside dummy.
3. LeetCode 146 — LRU Cache: Uses a doubly linked list plus hashmap. Can you design that next?
4. How does addAtIndex change for a circular list? You must handle the wrap-around and cannot use null as the list terminator.
5. Thread-safe linked list: Discuss per-node locking versus a global list-level lock and their tradeoffs.

Key Takeaways#

• A sentinel dummy head eliminates special-case code for head insertions and deletions — use it in every linked list design problem.
• Maintain a size counter so boundary validation is O(1) and does not require traversal.
• addAtHead and addAtTail are simply addAtIndex(0) and addAtIndex(size) — no duplicate code needed.
• For addAtIndex, traverse to the predecessor (index steps from dummy). For get, traverse to the node itself (index steps from dummy.next).
• The doubly linked list variant with a tail pointer achieves O(1) for head and tail operations and is the foundation of the LRU Cache.
• This problem is a direct prerequisite for LC 146 (LRU Cache) and any system design question involving ordered in-memory storage.