Interview Preplinked-list-advancedmediumAmazonGoogleMicrosoft

Design Linked List (Full Implementation)

Choose your preparation mode4 modes available

Try It Solution Trace

Start learning this pattern below

Jump into concepts and practice - no test required

Recommended

Test this pattern10 questions across easy, medium, and hard to know if this pattern is strong

📋

Problem

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.

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.

Edge cases: get from empty list → returns -1addAtIndex with index greater than length → no insertiondeleteAtIndex with invalid index → no deletion

</>

IDE

class MyLinkedList:

class MyLinkedList:
    def __init__(self):
        # Initialize your data structure here.
        pass
    def get(self, index: int) -> int:
        pass
    def addAtHead(self, val: int) -> None:
        pass
    def addAtTail(self, val: int) -> None:
        pass
    def addAtIndex(self, index: int, val: int) -> None:
        pass
    def deleteAtIndex(self, index: int) -> None:
        pass

class MyLinkedList {
    public MyLinkedList() {
        // Initialize your data structure here.
    }
    public int get(int index) {
        return -1;
    }
    public void addAtHead(int val) {
    }
    public void addAtTail(int val) {
    }
    public void addAtIndex(int index, int val) {
    }
    public void deleteAtIndex(int index) {
    }
}

#include <iostream>
using namespace std;
class MyLinkedList {
public:
    MyLinkedList() {
        // Initialize your data structure here.
    }
    int get(int index) {
        return -1;
    }
    void addAtHead(int val) {
    }
    void addAtTail(int val) {
    }
    void addAtIndex(int index, int val) {
    }
    void deleteAtIndex(int index) {
    }
};

class MyLinkedList {
    constructor() {
        // Initialize your data structure here.
    }
    get(index) {
        return -1;
    }
    addAtHead(val) {
    }
    addAtTail(val) {
    }
    addAtIndex(index, val) {
    }
    deleteAtIndex(index) {
    }
}

0/9

Common Bugs to Avoid

Wrong: get returns -1 even for valid indicesIncorrect index validation or traversal logic stopping early.✅ Ensure traversal continues until index-th node is reached and check for None only after traversal.

Wrong: addAtIndex inserts node even when index > lengthMissing or incorrect boundary check for index in addAtIndex.✅ Add condition: if index > length, do not insert node.

Wrong: deleteAtIndex deletes node at invalid indexNo validation of index before deletion.✅ Check if index < length before deleting node.

Wrong: addAtTail causes TLE on large inputsTraversing entire list to add at tail causing O(n^2) complexity.✅ Maintain a tail pointer to add at tail in O(1) time.

Wrong: get returns wrong values after deleteAtIndexPointer updates after deletion are incorrect causing list corruption.✅ Update next pointers correctly and maintain list integrity after deletion.

✓

Test Cases

t1_01basic

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

Expected[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.

t1_02basic

Input["addAtHead(5)","addAtHead(10)","addAtTail(15)","get(0)","get(2)","deleteAtIndex(1)","get(1)"]

Expected[null,null,null,10,15,null,15]

Start with empty list. addAtHead(5) -> [5], addAtHead(10) -> [10,5], addAtTail(15) -> [10,5,15]. get(0) returns 10, get(2) returns 15. deleteAtIndex(1) removes 5, list becomes [10,15]. get(1) returns 15.

Practice

(1/5)

1. You are given a singly linked list where each node contains an additional pointer that can point to any node in the list or null. The task is to create a deep copy of this list, preserving both the next and random pointer structure. Which approach guarantees an optimal solution with O(n) time and O(1) extra space?

easy

A. Interleave copied nodes within the original list, assign random pointers using the interleaved structure, then separate the lists.

B. Use a hash map to store original-to-copy node mappings and create the copy in two passes.

C. Use a recursive function with memoization to copy nodes and their random pointers.

D. Traverse the list multiple times, copying nodes and random pointers separately without extra data structures.

Design Linked List (Full Implementation)

Start learning this pattern below

Practice

Solution

Step 1: Understand the problem constraints

Step 2: Identify the optimal approach

Final Answer:

Quick Check:

Solution

Step 1: Understand the problem constraints

Step 2: Evaluate approaches

Final Answer:

Quick Check:

Solution

Step 1: Identify the accumulation operation

Step 2: Understand impact on single-node lists

Final Answer:

Quick Check:

Solution

Step 1: Identify missing boundary check

Step 2: Consequence of missing check

Final Answer:

Quick Check:

Solution

Step 1: Understand node reuse implications

Step 2: Modify algorithm to track visited nodes

Step 3: Evaluate other options

Final Answer:

Quick Check: