Design Linked List (Full Implementation)

🎯

Design Linked List (Full Implementation)

mediumLINKED_LISTAmazonGoogleMicrosoft

Imagine building a custom playlist manager where songs can be added, removed, or retrieved at any position efficiently. Designing a linked list from scratch is the foundation for such dynamic data structures.

💡 This problem requires implementing a linked list from the ground up, which is challenging for beginners because it involves managing pointers/references carefully and handling edge cases like empty lists or invalid indices. Understanding how nodes connect and how to maintain list integrity is crucial.

📋

Problem Statement

Design a singly linked list with the following functionalities: - get(index): Get the value of the index-th node in the linked list. If the index is invalid, return -1. - addAtHead(val): Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. - addAtTail(val): Append a node of value val to the last element of the linked list. - addAtIndex(index, val): Add a node of value val before the index-th node in the linked list. If index equals the length of the linked list, the node will be appended to the end. If index is greater than the length, the node will not be inserted. - deleteAtIndex(index): Delete the index-th node in the linked list, if the index is valid.

0 ≤ index ≤ 10^5All values will be in the range [1, 1000]At most 10^4 calls will be made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex.

💡

Example

Input"addAtHead(1), addAtTail(3), addAtIndex(1, 2), get(1), deleteAtIndex(1), get(1)"

Output[null, null, null, 2, null, 3]

After adding 1 at head and 3 at tail, list is [1,3]. Adding 2 at index 1 makes list [1,2,3]. get(1) returns 2. Deleting index 1 removes 2, list becomes [1,3]. get(1) now returns 3.

• get from empty list → returns -1
• addAtIndex with index greater than length → no insertion
• deleteAtIndex with invalid index → no deletion
• addAtIndex at length (append) → node added at tail

⚠️

Common Mistakes

Not handling empty list cases properly

Null pointer exceptions or incorrect results when list is empty

✅ Use dummy nodes or check for null before accessing next pointers

Incorrectly updating tail pointer after deletions

Tail pointer points to deleted node causing errors on addAtTail

✅ Update tail pointer to previous node if tail node is deleted

Off-by-one errors in traversal loops

Insertions or deletions happen at wrong positions

✅ Carefully define loop ranges and test with small examples

Not checking index bounds before operations

Operations on invalid indices cause runtime errors or incorrect behavior

✅ Maintain size and check index validity before traversals

Memory leaks in C++ by not deleting removed nodes

Program uses more memory over time

✅ Explicitly delete nodes when removing them

🧠

Brute Force (Naive Traversal for Each Operation)

💡 Starting with a straightforward implementation helps understand the linked list mechanics and the cost of each operation before optimizing.

Intuition

Implement each operation by traversing the list from the head to the required position every time, without any shortcuts or extra pointers.

Algorithm

1. Define a Node class with value and next pointer.
2. Maintain a head pointer for the linked list.
3. For get(index), traverse from head to index-th node and return its value or -1 if invalid.
4. For addAtHead(val), create a new node and point it to current head, then update head.
5. For addAtTail(val), traverse to the last node and append the new node.
6. For addAtIndex(index, val), traverse to (index-1)-th node and insert new node after it; if index is 0, add at head.
7. For deleteAtIndex(index), traverse to (index-1)-th node and remove the next node by adjusting pointers.

💡 The main challenge is correctly traversing and updating pointers without losing nodes or corrupting the list.

</>

Code

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList:
    def __init__(self):
        self.head = None

    def get(self, index: int) -> int:
        curr = self.head
        for _ in range(index):
            if not curr:
                return -1
            curr = curr.next
        return curr.val if curr else -1

    def addAtHead(self, val: int) -> None:
        self.head = Node(val, self.head)

    def addAtTail(self, val: int) -> None:
        if not self.head:
            self.head = Node(val)
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = Node(val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index == 0:
            self.addAtHead(val)
            return
        curr = self.head
        for _ in range(index - 1):
            if not curr:
                return
            curr = curr.next
        if curr:
            curr.next = Node(val, curr.next)

    def deleteAtIndex(self, index: int) -> None:
        if not self.head:
            return
        if index == 0:
            self.head = self.head.next
            return
        curr = self.head
        for _ in range(index - 1):
            if not curr.next:
                return
            curr = curr.next
        if curr.next:
            curr.next = curr.next.next

# Driver code to test
if __name__ == '__main__':
    linkedList = MyLinkedList()
    linkedList.addAtHead(1)
    linkedList.addAtTail(3)
    linkedList.addAtIndex(1, 2)  # linked list becomes 1->2->3
    print(linkedList.get(1))    # returns 2
    linkedList.deleteAtIndex(1) # now the linked list is 1->3
    print(linkedList.get(1))    # returns 3

Line Notes

class Node:Defines the basic building block of the linked list

self.head = NoneInitialize the linked list as empty

for _ in range(index):Traverse node by node to reach the desired index

if not curr:Check for invalid index or end of list

self.head = Node(val, self.head)Insert new node at the head by pointing it to current head

while curr.next:Traverse to the last node for addAtTail

curr.next = Node(val)Append new node at the tail

for _ in range(index - 1):Traverse to node before insertion/deletion point

curr.next = Node(val, curr.next)Insert new node by adjusting pointers

self.head = self.head.nextDelete head node by moving head pointer

curr.next = curr.next.nextDelete node by skipping it in the chain

class MyLinkedList {
    private class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }
    private Node head;

    public MyLinkedList() {
        head = null;
    }

    public int get(int index) {
        Node curr = head;
        for (int i = 0; i < index; i++) {
            if (curr == null) return -1;
            curr = curr.next;
        }
        return curr == null ? -1 : curr.val;
    }

    public void addAtHead(int val) {
        Node newNode = new Node(val);
        newNode.next = head;
        head = newNode;
    }

    public void addAtTail(int val) {
        if (head == null) {
            head = new Node(val);
            return;
        }
        Node curr = head;
        while (curr.next != null) {
            curr = curr.next;
        }
        curr.next = new Node(val);
    }

    public void addAtIndex(int index, int val) {
        if (index == 0) {
            addAtHead(val);
            return;
        }
        Node curr = head;
        for (int i = 0; i < index - 1; i++) {
            if (curr == null) return;
            curr = curr.next;
        }
        if (curr != null) {
            Node newNode = new Node(val);
            newNode.next = curr.next;
            curr.next = newNode;
        }
    }

    public void deleteAtIndex(int index) {
        if (head == null) return;
        if (index == 0) {
            head = head.next;
            return;
        }
        Node curr = head;
        for (int i = 0; i < index - 1; i++) {
            if (curr.next == null) return;
            curr = curr.next;
        }
        if (curr.next != null) {
            curr.next = curr.next.next;
        }
    }

    // Main method to test
    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
        System.out.println(linkedList.get(1)); // returns 2
        linkedList.deleteAtIndex(1); // now the linked list is 1->3
        System.out.println(linkedList.get(1)); // returns 3
    }
}

Line Notes

private class Node {Inner class encapsulates node structure

head = null;Initialize empty linked list

for (int i = 0; i < index; i++) {Traverse to target index for get

if (curr == null) return -1;Handle invalid index gracefully

newNode.next = head;Insert new node at head by linking to current head

while (curr.next != null) {Traverse to last node for addAtTail

curr.next = new Node(val);Append new node at tail

for (int i = 0; i < index - 1; i++) {Traverse to node before insertion/deletion

newNode.next = curr.next;Link new node to next node before insertion

head = head.next;Delete head by moving head pointer

curr.next = curr.next.next;Delete node by skipping it

#include <iostream>
using namespace std;

class MyLinkedList {
    struct Node {
        int val;
        Node* next;
        Node(int v) : val(v), next(nullptr) {}
    };
    Node* head;
public:
    MyLinkedList() : head(nullptr) {}

    int get(int index) {
        Node* curr = head;
        for (int i = 0; i < index; i++) {
            if (!curr) return -1;
            curr = curr->next;
        }
        return curr ? curr->val : -1;
    }

    void addAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = head;
        head = newNode;
    }

    void addAtTail(int val) {
        if (!head) {
            head = new Node(val);
            return;
        }
        Node* curr = head;
        while (curr->next) {
            curr = curr->next;
        }
        curr->next = new Node(val);
    }

    void addAtIndex(int index, int val) {
        if (index == 0) {
            addAtHead(val);
            return;
        }
        Node* curr = head;
        for (int i = 0; i < index - 1; i++) {
            if (!curr) return;
            curr = curr->next;
        }
        if (curr) {
            Node* newNode = new Node(val);
            newNode->next = curr->next;
            curr->next = newNode;
        }
    }

    void deleteAtIndex(int index) {
        if (!head) return;
        if (index == 0) {
            Node* temp = head;
            head = head->next;
            delete temp;
            return;
        }
        Node* curr = head;
        for (int i = 0; i < index - 1; i++) {
            if (!curr->next) return;
            curr = curr->next;
        }
        if (curr->next) {
            Node* temp = curr->next;
            curr->next = curr->next->next;
            delete temp;
        }
    }
};

int main() {
    MyLinkedList linkedList;
    linkedList.addAtHead(1);
    linkedList.addAtTail(3);
    linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
    cout << linkedList.get(1) << endl; // returns 2
    linkedList.deleteAtIndex(1); // now the linked list is 1->3
    cout << linkedList.get(1) << endl; // returns 3
    return 0;
}

Line Notes

struct Node {Defines node structure with value and pointer

Node* head;Pointer to the start of the linked list

for (int i = 0; i < index; i++) {Traverse to the index-th node for get

if (!curr) return -1;Check for invalid index or end of list

newNode->next = head;Insert new node at head by linking to current head

while (curr->next) {Traverse to last node for addAtTail

curr->next = new Node(val);Append new node at tail

for (int i = 0; i < index - 1; i++) {Traverse to node before insertion/deletion

newNode->next = curr->next;Link new node to next node before insertion

Node* temp = head;Store node to delete to free memory

curr->next = curr->next->next;Delete node by skipping it

class Node {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

class MyLinkedList {
    constructor() {
        this.head = null;
    }

    get(index) {
        let curr = this.head;
        for (let i = 0; i < index; i++) {
            if (!curr) return -1;
            curr = curr.next;
        }
        return curr ? curr.val : -1;
    }

    addAtHead(val) {
        this.head = new Node(val, this.head);
    }

    addAtTail(val) {
        if (!this.head) {
            this.head = new Node(val);
            return;
        }
        let curr = this.head;
        while (curr.next) {
            curr = curr.next;
        }
        curr.next = new Node(val);
    }

    addAtIndex(index, val) {
        if (index === 0) {
            this.addAtHead(val);
            return;
        }
        let curr = this.head;
        for (let i = 0; i < index - 1; i++) {
            if (!curr) return;
            curr = curr.next;
        }
        if (curr) {
            curr.next = new Node(val, curr.next);
        }
    }

    deleteAtIndex(index) {
        if (!this.head) return;
        if (index === 0) {
            this.head = this.head.next;
            return;
        }
        let curr = this.head;
        for (let i = 0; i < index - 1; i++) {
            if (!curr.next) return;
            curr = curr.next;
        }
        if (curr.next) {
            curr.next = curr.next.next;
        }
    }
}

// Test code
const linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
console.log(linkedList.get(1)); // returns 2
linkedList.deleteAtIndex(1); // now the linked list is 1->3
console.log(linkedList.get(1)); // returns 3

Line Notes

class Node {Defines node structure with value and next pointer

this.head = null;Initialize empty linked list

for (let i = 0; i < index; i++) {Traverse to index-th node for get

if (!curr) return -1;Handle invalid index gracefully

this.head = new Node(val, this.head);Insert new node at head by linking to current head

while (curr.next) {Traverse to last node for addAtTail

curr.next = new Node(val);Append new node at tail

for (let i = 0; i < index - 1; i++) {Traverse to node before insertion/deletion

curr.next = new Node(val, curr.next);Insert new node by adjusting pointers

this.head = this.head.next;Delete head node by moving head pointer

curr.next = curr.next.next;Delete node by skipping it

⏱

Complexity

TimeO(n) per operation in worst case

SpaceO(n) for storing nodes

Each operation may require traversing up to n nodes, so time complexity is linear per operation. Space is linear due to storing nodes.

💡 For n=1000, each operation might traverse up to 1000 nodes, which is acceptable but can be slow for large n.

Interview Verdict: Accepted but inefficient for large inputs

This approach works correctly but is slow because it traverses the list for many operations. It is a good starting point to understand the problem.

🧠

Better Approach (Using Sentinel Head and Tail Pointers)

💡 Using sentinel (dummy) nodes for head and tail simplifies edge cases and maintaining tail pointer allows O(1) addAtTail operation.

Intuition

Add dummy head node to avoid null checks on head and maintain a tail pointer to append nodes quickly without traversal.

Algorithm

1. Initialize dummy head node and tail pointer pointing to dummy.
2. For addAtHead, insert new node after dummy head.
3. For addAtTail, append new node after tail and update tail pointer.
4. For get and addAtIndex, traverse from dummy head to target index.
5. For deleteAtIndex, traverse to node before target and remove it; update tail if needed.

💡 Sentinel nodes reduce special cases for head/tail operations and tail pointer avoids full traversal for tail insertions.

</>

Code

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList:
    def __init__(self):
        self.dummy = Node(0)
        self.tail = self.dummy
        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:
        newNode = Node(val, self.dummy.next)
        self.dummy.next = newNode
        if self.size == 0:
            self.tail = newNode
        self.size += 1

    def addAtTail(self, val: int) -> None:
        newNode = Node(val)
        self.tail.next = newNode
        self.tail = newNode
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size or index < 0:
            return
        if index == self.size:
            self.addAtTail(val)
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev.next
        newNode = Node(val, prev.next)
        prev.next = newNode
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev.next
        to_delete = prev.next
        prev.next = to_delete.next
        if to_delete == self.tail:
            self.tail = prev
        self.size -= 1

# Driver code
if __name__ == '__main__':
    linkedList = MyLinkedList()
    linkedList.addAtHead(1)
    linkedList.addAtTail(3)
    linkedList.addAtIndex(1, 2)  # linked list becomes 1->2->3
    print(linkedList.get(1))    # returns 2
    linkedList.deleteAtIndex(1) # now the linked list is 1->3
    print(linkedList.get(1))    # returns 3

Line Notes

self.dummy = Node(0)Dummy node simplifies head operations by providing a fixed start

self.tail = self.dummyTail pointer initialized to dummy to track last node

if index < 0 or index >= self.size:Bounds check to avoid invalid access

self.tail.next = newNodeAppend new node after tail for O(1) addAtTail

if to_delete == self.tail:Update tail pointer if last node is deleted

self.size += 1Maintain size to quickly check bounds

prev = self.dummyStart traversal from dummy to simplify insertion/deletion

prev.next = newNodeInsert new node by adjusting pointers

class MyLinkedList {
    private class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }
    private Node dummy;
    private Node tail;
    private int size;

    public MyLinkedList() {
        dummy = new Node(0);
        tail = dummy;
        size = 0;
    }

    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node curr = dummy.next;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr.val;
    }

    public void addAtHead(int val) {
        Node newNode = new Node(val);
        newNode.next = dummy.next;
        dummy.next = newNode;
        if (size == 0) tail = newNode;
        size++;
    }

    public void addAtTail(int val) {
        Node newNode = new Node(val);
        tail.next = newNode;
        tail = newNode;
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index > size || index < 0) return;
        if (index == size) {
            addAtTail(val);
            return;
        }
        Node prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node newNode = new Node(val);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node toDelete = prev.next;
        prev.next = toDelete.next;
        if (toDelete == tail) tail = prev;
        size--;
    }

    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
        System.out.println(linkedList.get(1)); // returns 2
        linkedList.deleteAtIndex(1); // now the linked list is 1->3
        System.out.println(linkedList.get(1)); // returns 3
    }
}

Line Notes

dummy = new Node(0);Dummy node to simplify edge cases at head

tail = dummy;Tail pointer tracks last node for O(1) tail insertions

if (index < 0 || index >= size) return -1;Bounds check for get

tail.next = newNode;Append new node at tail efficiently

if (toDelete == tail) tail = prev;Update tail if last node deleted

size++;Track size for quick boundary checks

Node prev = dummy;Start traversal from dummy for insert/delete

prev.next = newNode;Insert new node by pointer adjustment

#include <iostream>
using namespace std;

class MyLinkedList {
    struct Node {
        int val;
        Node* next;
        Node(int v) : val(v), next(nullptr) {}
    };
    Node* dummy;
    Node* tail;
    int size;
public:
    MyLinkedList() {
        dummy = new Node(0);
        tail = dummy;
        size = 0;
    }

    int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node* curr = dummy->next;
        for (int i = 0; i < index; i++) {
            curr = curr->next;
        }
        return curr->val;
    }

    void addAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = dummy->next;
        dummy->next = newNode;
        if (size == 0) tail = newNode;
        size++;
    }

    void addAtTail(int val) {
        Node* newNode = new Node(val);
        tail->next = newNode;
        tail = newNode;
        size++;
    }

    void addAtIndex(int index, int val) {
        if (index > size || index < 0) return;
        if (index == size) {
            addAtTail(val);
            return;
        }
        Node* prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        Node* newNode = new Node(val);
        newNode->next = prev->next;
        prev->next = newNode;
        size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node* prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        Node* toDelete = prev->next;
        prev->next = toDelete->next;
        if (toDelete == tail) tail = prev;
        delete toDelete;
        size--;
    }
};

int main() {
    MyLinkedList linkedList;
    linkedList.addAtHead(1);
    linkedList.addAtTail(3);
    linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
    cout << linkedList.get(1) << endl; // returns 2
    linkedList.deleteAtIndex(1); // now the linked list is 1->3
    cout << linkedList.get(1) << endl; // returns 3
    return 0;
}

Line Notes

dummy = new Node(0);Dummy node anchors the list start

tail = dummy;Tail pointer tracks last node for efficient tail insertions

if (index < 0 || index >= size) return -1;Bounds check for get

tail->next = newNode;Append new node at tail in O(1)

if (toDelete == tail) tail = prev;Update tail pointer if last node deleted

size++;Maintain size for quick boundary checks

Node* prev = dummy;Start traversal from dummy for insert/delete

prev->next = newNode;Insert new node by pointer adjustment

class Node {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

class MyLinkedList {
    constructor() {
        this.dummy = new Node(0);
        this.tail = this.dummy;
        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) {
        const newNode = new Node(val, this.dummy.next);
        this.dummy.next = newNode;
        if (this.size === 0) this.tail = newNode;
        this.size++;
    }

    addAtTail(val) {
        const newNode = new Node(val);
        this.tail.next = newNode;
        this.tail = newNode;
        this.size++;
    }

    addAtIndex(index, val) {
        if (index > this.size || index < 0) return;
        if (index === this.size) {
            this.addAtTail(val);
            return;
        }
        let prev = this.dummy;
        for (let i = 0; i < index; i++) {
            prev = prev.next;
        }
        const newNode = new Node(val, prev.next);
        prev.next = newNode;
        this.size++;
    }

    deleteAtIndex(index) {
        if (index < 0 || index >= this.size) return;
        let prev = this.dummy;
        for (let i = 0; i < index; i++) {
            prev = prev.next;
        }
        const toDelete = prev.next;
        prev.next = toDelete.next;
        if (toDelete === this.tail) this.tail = prev;
        this.size--;
    }
}

// Test code
const linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
console.log(linkedList.get(1)); // returns 2
linkedList.deleteAtIndex(1); // now the linked list is 1->3
console.log(linkedList.get(1)); // returns 3

Line Notes

this.dummy = new Node(0);Dummy node simplifies head operations

this.tail = this.dummy;Tail pointer tracks last node for O(1) tail insertions

if (index < 0 || index >= this.size) return -1;Bounds check for get

this.tail.next = newNode;Append new node at tail efficiently

if (toDelete === this.tail) this.tail = prev;Update tail if last node deleted

this.size++;Track size for quick boundary checks

let prev = this.dummy;Start traversal from dummy for insert/delete

prev.next = newNode;Insert new node by pointer adjustment

⏱

Complexity

TimeO(n) per get, addAtIndex, deleteAtIndex; O(1) for addAtHead and addAtTail

SpaceO(n) for storing nodes

Maintaining tail pointer reduces addAtTail to O(1). Other operations still require traversal up to O(n).

💡 For n=1000, addAtTail is now constant time, improving performance for frequent tail insertions.

Interview Verdict: Accepted and more efficient for tail insertions

This approach improves efficiency and code clarity by using sentinel nodes and tail pointer, a common interview optimization.

🧠

Optimal Approach (Maintain Size and Use Sentinel Nodes with Tail Pointer)

💡 Tracking size allows quick boundary checks, and sentinel nodes plus tail pointer optimize all operations with minimal edge case handling.

Intuition

Keep track of the list size to avoid unnecessary traversals for invalid indices and use dummy head and tail pointer to simplify insertions and deletions.

Algorithm

1. Initialize dummy head node, tail pointer, and size counter.
2. For get, immediately return -1 if index is invalid using size.
3. For addAtHead, insert after dummy head and update tail if list was empty.
4. For addAtTail, append after tail pointer and update tail.
5. For addAtIndex, check index validity using size, then traverse and insert.
6. For deleteAtIndex, check index validity, traverse, delete node, and update tail if needed.

💡 Size tracking prevents invalid operations early, sentinel nodes simplify pointer updates, and tail pointer optimizes tail insertions.

</>

Code

class Node:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList:
    def __init__(self):
        self.dummy = Node(0)
        self.tail = self.dummy
        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:
        newNode = Node(val, self.dummy.next)
        self.dummy.next = newNode
        if self.size == 0:
            self.tail = newNode
        self.size += 1

    def addAtTail(self, val: int) -> None:
        newNode = Node(val)
        self.tail.next = newNode
        self.tail = newNode
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size or index < 0:
            return
        if index == self.size:
            self.addAtTail(val)
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev.next
        newNode = Node(val, prev.next)
        prev.next = newNode
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev.next
        to_delete = prev.next
        prev.next = to_delete.next
        if to_delete == self.tail:
            self.tail = prev
        self.size -= 1

# Driver code
if __name__ == '__main__':
    linkedList = MyLinkedList()
    linkedList.addAtHead(1)
    linkedList.addAtTail(3)
    linkedList.addAtIndex(1, 2)  # linked list becomes 1->2->3
    print(linkedList.get(1))    # returns 2
    linkedList.deleteAtIndex(1) # now the linked list is 1->3
    print(linkedList.get(1))    # returns 3

Line Notes

if index < 0 or index >= self.size:Quickly reject invalid indices using size

self.dummy = Node(0)Dummy node anchors the list start

self.tail = self.dummyTail pointer tracks last node for O(1) tail insertions

newNode = Node(val, self.dummy.next)Insert new node at head by linking to current first node

self.tail.next = newNodeAppend new node at tail efficiently

if to_delete == self.tail:Update tail pointer if last node deleted

self.size += 1Maintain size for boundary checks and correctness

prev.next = newNodeInsert new node by adjusting pointers

class MyLinkedList {
    private class Node {
        int val;
        Node next;
        Node(int val) { this.val = val; }
    }
    private Node dummy;
    private Node tail;
    private int size;

    public MyLinkedList() {
        dummy = new Node(0);
        tail = dummy;
        size = 0;
    }

    public int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node curr = dummy.next;
        for (int i = 0; i < index; i++) {
            curr = curr.next;
        }
        return curr.val;
    }

    public void addAtHead(int val) {
        Node newNode = new Node(val);
        newNode.next = dummy.next;
        dummy.next = newNode;
        if (size == 0) tail = newNode;
        size++;
    }

    public void addAtTail(int val) {
        Node newNode = new Node(val);
        tail.next = newNode;
        tail = newNode;
        size++;
    }

    public void addAtIndex(int index, int val) {
        if (index > size || index < 0) return;
        if (index == size) {
            addAtTail(val);
            return;
        }
        Node prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node newNode = new Node(val);
        newNode.next = prev.next;
        prev.next = newNode;
        size++;
    }

    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node toDelete = prev.next;
        prev.next = toDelete.next;
        if (toDelete == tail) tail = prev;
        size--;
    }

    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        linkedList.addAtHead(1);
        linkedList.addAtTail(3);
        linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
        System.out.println(linkedList.get(1)); // returns 2
        linkedList.deleteAtIndex(1); // now the linked list is 1->3
        System.out.println(linkedList.get(1)); // returns 3
    }
}

Line Notes

if (index < 0 || index >= size) return -1;Bounds check using size for get

dummy = new Node(0);Dummy node simplifies head operations

tail = dummy;Tail pointer tracks last node for efficient tail insertions

newNode.next = dummy.next;Insert new node at head by linking to current first node

tail.next = newNode;Append new node at tail in O(1)

if (toDelete == tail) tail = prev;Update tail pointer if last node deleted

size++;Maintain size for correctness and boundary checks

prev.next = newNode;Insert new node by pointer adjustment

#include <iostream>
using namespace std;

class MyLinkedList {
    struct Node {
        int val;
        Node* next;
        Node(int v) : val(v), next(nullptr) {}
    };
    Node* dummy;
    Node* tail;
    int size;
public:
    MyLinkedList() {
        dummy = new Node(0);
        tail = dummy;
        size = 0;
    }

    int get(int index) {
        if (index < 0 || index >= size) return -1;
        Node* curr = dummy->next;
        for (int i = 0; i < index; i++) {
            curr = curr->next;
        }
        return curr->val;
    }

    void addAtHead(int val) {
        Node* newNode = new Node(val);
        newNode->next = dummy->next;
        dummy->next = newNode;
        if (size == 0) tail = newNode;
        size++;
    }

    void addAtTail(int val) {
        Node* newNode = new Node(val);
        tail->next = newNode;
        tail = newNode;
        size++;
    }

    void addAtIndex(int index, int val) {
        if (index > size || index < 0) return;
        if (index == size) {
            addAtTail(val);
            return;
        }
        Node* prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        Node* newNode = new Node(val);
        newNode->next = prev->next;
        prev->next = newNode;
        size++;
    }

    void deleteAtIndex(int index) {
        if (index < 0 || index >= size) return;
        Node* prev = dummy;
        for (int i = 0; i < index; i++) {
            prev = prev->next;
        }
        Node* toDelete = prev->next;
        prev->next = toDelete->next;
        if (toDelete == tail) tail = prev;
        delete toDelete;
        size--;
    }
};

int main() {
    MyLinkedList linkedList;
    linkedList.addAtHead(1);
    linkedList.addAtTail(3);
    linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
    cout << linkedList.get(1) << endl; // returns 2
    linkedList.deleteAtIndex(1); // now the linked list is 1->3
    cout << linkedList.get(1) << endl; // returns 3
    return 0;
}

Line Notes

if (index < 0 || index >= size) return -1;Bounds check using size for get

dummy = new Node(0);Dummy node anchors the list start

tail = dummy;Tail pointer tracks last node for O(1) tail insertions

newNode->next = dummy->next;Insert new node at head by linking to current first node

tail->next = newNode;Append new node at tail efficiently

if (toDelete == tail) tail = prev;Update tail pointer if last node deleted

size++;Maintain size for correctness and boundary checks

prev->next = newNode;Insert new node by pointer adjustment

class Node {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

class MyLinkedList {
    constructor() {
        this.dummy = new Node(0);
        this.tail = this.dummy;
        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) {
        const newNode = new Node(val, this.dummy.next);
        this.dummy.next = newNode;
        if (this.size === 0) this.tail = newNode;
        this.size++;
    }

    addAtTail(val) {
        const newNode = new Node(val);
        this.tail.next = newNode;
        this.tail = newNode;
        this.size++;
    }

    addAtIndex(index, val) {
        if (index > this.size || index < 0) return;
        if (index === this.size) {
            this.addAtTail(val);
            return;
        }
        let prev = this.dummy;
        for (let i = 0; i < index; i++) {
            prev = prev.next;
        }
        const newNode = new Node(val, prev.next);
        prev.next = newNode;
        this.size++;
    }

    deleteAtIndex(index) {
        if (index < 0 || index >= this.size) return;
        let prev = this.dummy;
        for (let i = 0; i < index; i++) {
            prev = prev.next;
        }
        const toDelete = prev.next;
        prev.next = toDelete.next;
        if (toDelete === this.tail) this.tail = prev;
        this.size--;
    }
}

// Test code
const linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
console.log(linkedList.get(1)); // returns 2
linkedList.deleteAtIndex(1); // now the linked list is 1->3
console.log(linkedList.get(1)); // returns 3

Line Notes

if (index < 0 || index >= this.size) return -1;Bounds check using size for get

this.dummy = new Node(0);Dummy node simplifies head operations

this.tail = this.dummy;Tail pointer tracks last node for O(1) tail insertions

const newNode = new Node(val, this.dummy.next);Insert new node at head by linking to current first node

this.tail.next = newNode;Append new node at tail efficiently

if (toDelete === this.tail) this.tail = prev;Update tail if last node deleted

this.size++;Maintain size for correctness and boundary checks

prev.next = newNode;Insert new node by pointer adjustment

⏱

Complexity

TimeO(n) per get, addAtIndex, deleteAtIndex; O(1) for addAtHead and addAtTail

SpaceO(n) for storing nodes

Size tracking allows quick invalid index checks; tail pointer makes addAtTail O(1). Other operations still require traversal.

💡 This is the best practical implementation for interviews, balancing simplicity and efficiency.

Interview Verdict: Accepted and optimal for this problem

This approach is the recommended solution in interviews due to its clarity, correctness, and efficiency.

📊

All Approaches - One-Glance Tradeoffs

💡 Use the optimal approach with sentinel nodes, tail pointer, and size tracking in 95% of interviews for clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n) per operation	O(n)	No	N/A	Mention only - never code
2. Better (Sentinel + Tail Pointer)	O(1) addAtTail, O(n) others	O(n)	No	N/A	Good to code if asked to optimize tail insertion
3. Optimal (Sentinel + Tail + Size)	O(1) addAtHead/addAtTail, O(n) others	O(n)	No	N/A	Best approach to implement in interview

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before your interview. Start by clarifying requirements, then explain the brute force approach to show understanding. Progress to optimizations and discuss tradeoffs. Practice coding and testing edge cases.

How to Present

Clarify the problem and confirm input/output expectations.Describe the brute force approach with simple traversal for each operation.Explain its limitations and introduce sentinel nodes and tail pointer for optimization.Discuss maintaining size for boundary checks and final optimal approach.Write clean, modular code and test with edge cases.

Time Allocation

Clarify: 3min → Approach explanation: 5min → Code: 15min → Testing & edge cases: 7min. Total ~30min

What the Interviewer Tests

Interviewer checks your understanding of linked list mechanics, pointer manipulation, handling edge cases, and ability to optimize operations like addAtTail to O(1).

Common Follow-ups

• How would you implement a doubly linked list? → Add prev pointers and update accordingly.
• Can you optimize get operation? → Use additional data structures or indexing, but usually not required.

💡 These follow-ups test your ability to extend the design and think about performance tradeoffs.

🔍

Pattern Recognition

When to Use

1) Need to implement a dynamic data structure with insert/delete at arbitrary positions, 2) Operations require O(1) insertion/deletion at head/tail, 3) Index-based access with get, 4) Handling edge cases like empty list or invalid indices.

Signature Phrases

design linked listaddAtHeadaddAtTailaddAtIndexdeleteAtIndexget node value

NOT This Pattern When

Problems that only require traversal or searching without insert/delete operations, or array-based problems.

Similar Problems

Design Doubly Linked List - extends this with prev pointersReverse Linked List - manipulates pointers in linked listMerge Two Sorted Lists - merges two linked lists maintaining order

Practice

1. Consider the following code snippet implementing the optimal approach to copy a list with random pointers. Given the input list: 1 -> 2 -> 3, where node 1's random points to node 3, node 2's random points to node 1, and node 3's random is null, what is the value of copy_curr.random.val after the last iteration of the separation step (Step 3)?

easy

A. 1

B. 3

C. None (random pointer is null)

D. 2

Solution

1. Step 1: Trace Step 1 (Interleaving nodes)

   Original list: 1->2->3. After interleaving: 1->1'->2->2'->3->3'.

2. Step 2: Trace Step 2 (Assign random pointers)

   Node 1's random points to 3, so 1'.random = 3'. Node 2's random points to 1, so 2'.random = 1'. Node 3's random is null, so 3'.random = null.

3. Step 3: Trace Step 3 (Separate lists)

   After separation, copy_curr starts at 1'. After last iteration, copy_curr is at 3'. Its random pointer is null, so copy_curr.random.val does not exist.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   copy_curr.random is null after last iteration [OK]

Hint: Random pointers point to copied nodes via original's next [OK]

Common Mistakes:

• Confusing original and copied nodes during separation
• Off-by-one error in advancing copy_curr
• Assuming random pointers remain unchanged

2. Consider the following Python code implementing browser history with two stacks. After executing the sequence of operations below, what is the output of the last back call?

browserHistory = BrowserHistory("leetcode.com")
browserHistory.visit("google.com")
browserHistory.visit("facebook.com")
browserHistory.visit("youtube.com")
print(browserHistory.back(1))
print(browserHistory.back(1))
print(browserHistory.forward(1))

easy

A. "youtube.com"

B. "google.com"

C. "facebook.com"

D. "leetcode.com"

Solution

1. Step 1: Trace back(1) after visiting youtube.com

   back_stack = ["leetcode.com", "google.com", "facebook.com", "youtube.com"] Pop "youtube.com" to forward_stack, back_stack top is "facebook.com".

2. Step 2: Trace back(1) again and forward(1)

   Second back(1): pop "facebook.com" to forward_stack, top is "google.com". Forward(1): pop "facebook.com" from forward_stack back to back_stack, top is "facebook.com".

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Last forward returns "facebook.com" as expected [OK]

Hint: Back and forward operations move URLs between stacks correctly [OK]

Common Mistakes:

• Off-by-one errors in popping stacks
• Confusing forward and back stacks
• Returning wrong top element after operations

3. What is the space complexity of the optimal approach that copies a linked list with random pointers by weaving copied nodes into the original list and then separating them?

medium

A. O(n) due to storing copied nodes in a hash map

B. O(n) because each node's random pointer requires extra space

C. O(n) due to recursion stack in the copying process

D. O(1) because no extra data structures are used besides new nodes

Solution

1. Step 1: Identify auxiliary space usage

   The optimal approach weaves copied nodes directly into the original list without using extra hash maps or recursion.

2. Step 2: Confirm space complexity

   Only new nodes are created, which is required output space, so auxiliary space is O(1).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   No extra data structures or recursion stack used [OK]

Hint: Weaving nodes avoids extra mapping space [OK]

Common Mistakes:

• Confusing output space with auxiliary space
• Assuming recursion is used and adds stack space
• Thinking random pointers require extra space

4. What is the time complexity of the optimal iterative approach that reverses a linked list in groups of k nodes, and why?

medium

A. O(nk), because each group reversal takes O(k) and there are n/k groups.

B. O(n), because each node is visited and reversed exactly once.

C. O(n log k), because reversing each group involves log k steps due to pointer updates.

D. O(n + k), because the algorithm traverses the list plus reverses k nodes.

Solution

1. Step 1: Analyze group reversal cost

   Each group of k nodes is reversed in O(k) time.

2. Step 2: Count total groups and total nodes processed

   There are approximately n/k groups, so total time is O(k * n/k) = O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each node is processed once during reversal [OK]

Hint: Total nodes processed once -> O(n) time [OK]

Common Mistakes:

• Multiplying n by k incorrectly
• Assuming log k factor in reversal
• Ignoring that groups partition the list

5. Suppose the linked list nodes can be reused multiple times (i.e., the list is cyclic or nodes appear multiple times). Which modification to the reorder list algorithm is necessary to handle this scenario correctly?

hard

A. Use a hash set to track visited nodes and avoid infinite loops during reordering.

B. No modification needed; the recursive approach handles cycles naturally.

C. Convert the list to an array first to handle duplicates, then reorder using indices.

D. Break the list into halves without reversing the second half to prevent cycles.

Solution

1. Step 1: Understand node reuse implications

   Reusing nodes or cycles cause infinite loops if not detected during traversal.

2. Step 2: Modify algorithm to track visited nodes

   Using a hash set to track visited nodes prevents revisiting and infinite loops.

3. Step 3: Evaluate other options

   Recursive approach alone cannot detect cycles; array conversion adds overhead; skipping reversal breaks reorder logic.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Tracking visited nodes prevents infinite loops in cyclic lists [OK]

Hint: Cycle detection requires visited node tracking [OK]

Common Mistakes:

• Assuming no cycles exist
• Relying on recursion without cycle checks
• Ignoring node reuse effects