Design Linked List (Full Implementation)

▶

Steps

setup

Initialize dummy head, tail, and size

Create a dummy head node with value 0 and no next node. Set tail pointer to dummy and size counter to 0.

💡 Dummy head simplifies edge cases by providing a fixed start; tail pointer helps efficient tail insertions; size tracks list length for quick index validation.

Line:

self.dummy = Node(0)
self.tail = self.dummy
self.size = 0

💡 The linked list starts empty but ready for operations with dummy and tail pointers set.

insert

addAtHead(1): create new node with val=1

Create a new node with value 1, pointing its next to dummy.next (currently null).

💡 New node is prepared to be inserted right after dummy head, becoming the first real node.

Line:

newNode = Node(val, self.dummy.next)

💡 Node creation is the first step before linking it into the list.

insert

addAtHead(1): link new node after dummy

Set dummy.next to point to the new node, inserting it at the head of the list.

💡 Linking new node after dummy head makes it the first real node in the list.

Line:

self.dummy.next = newNode

💡 The list now starts with the new node after dummy head.

insert

addAtHead(1): update tail if list was empty

Since size was 0, update tail pointer to the new node, now the last node in the list.

💡 Tail must point to last node; when list was empty, new node is both head and tail.

Line:

if self.size == 0:
    self.tail = newNode

💡 Tail pointer correctly tracks the last node after insertion.

insert

addAtHead(1): increment size

Increase the size counter by 1 to reflect the new node added.

💡 Size tracks number of real nodes, used for index validation in other operations.

Line:

self.size += 1

💡 Size is now 1, indicating one element in the list.

insert

addAtTail(3): create new node with val=3

Create a new node with value 3 and next pointer null, ready to append at tail.

💡 New node will be linked after current tail to add at the end.

Line:

newNode = Node(val)

💡 Node creation prepares for tail insertion.

insert

addAtTail(3): link new node after tail

Set current tail's next pointer to new node, appending it at the end of the list.

💡 Linking new node after tail extends the list by one node at the end.

Line:

self.tail.next = newNode

💡 List now has two nodes after dummy: 1 -> 3.

insert

addAtTail(3): update tail pointer to new node

Move tail pointer to the new node, which is now the last node in the list.

💡 Tail pointer must always track the last node for efficient tail insertions.

Line:

self.tail = newNode

💡 Tail pointer updated to new last node.

insert

addAtTail(3): increment size

Increase size counter by 1 to reflect the new node added at tail.

💡 Size now reflects two nodes in the list.

Line:

self.size += 1

💡 Size is now 2, matching the number of nodes after dummy.

insert

addAtIndex(1, 2): check index validity

Verify index 1 is valid (0 <= 1 <= size 2), so insertion proceeds.

💡 Index validation prevents invalid insertions outside list bounds.

Line:

if index > self.size or index < 0:
    return

💡 Insertion at index 1 is allowed between nodes 1 and 3.

traverse

addAtIndex(1, 2): traverse to node before index

Start from dummy and move one step to node with val=1, which is before index 1.

💡 Traversal finds the node after which new node will be inserted.

Line:

prev = self.dummy
for _ in range(index):
    prev = prev.next

💡 Prev pointer now at node 1, ready for insertion after it.

insert

addAtIndex(1, 2): create new node with val=2

Create new node with value 2, pointing its next to prev.next (node with val=3).

💡 New node will be inserted between nodes 1 and 3.

Line:

newNode = Node(val, prev.next)

💡 New node prepared with correct next pointer for insertion.

insert

addAtIndex(1, 2): link new node after prev

Set prev.next to new node, inserting it between nodes 1 and 3.

💡 Linking new node updates the list to [1, 2, 3].

Line:

prev.next = newNode

💡 List now correctly includes new node at index 1.

insert

addAtIndex(1, 2): increment size

Increase size counter by 1 to reflect the new node added at index 1.

💡 Size now reflects three nodes in the list.

Line:

self.size += 1

💡 Size is now 3, matching the updated list length.

compare

get(1): validate index

Check if index 1 is valid (0 <= 1 < size 3), so proceed to get value.

💡 Index validation prevents invalid access.

Line:

if index < 0 or index >= self.size:
    return -1

💡 Index 1 corresponds to node with val=2.

traverse

get(1): traverse to node at index

Start from dummy.next (node 1), move one step to node 2 at index 1.

💡 Traversal finds the node whose value we want to return.

Line:

curr = self.dummy.next
for _ in range(index):
    curr = curr.next

💡 Curr pointer now at node with val=2.

compare

get(1): return value of current node

Return the value of the node at index 1, which is 2.

💡 Returning the node's value completes the get operation.

Line:

return curr.val

💡 Value 2 is the correct output for get(1).

delete

deleteAtIndex(1): validate index

Check if index 1 is valid (0 <= 1 < size 3), so proceed to delete.

💡 Index validation prevents invalid deletions.

Line:

if index < 0 or index >= self.size:
    return

💡 Deletion at index 1 is allowed.

traverse

deleteAtIndex(1): traverse to node before index

Start from dummy and move one step to node 1, which is before the node to delete.

💡 Traversal finds the node before the one to be deleted for relinking.

Line:

prev = self.dummy
for _ in range(index):
    prev = prev.next

💡 Prev pointer now at node 1, ready to unlink next node.

delete

deleteAtIndex(1): unlink node and update tail if needed

Set prev.next to node after to_delete (node 3), unlinking node 2. Since deleted node is not tail, tail remains unchanged.

💡 Unlinking removes node from list; tail update needed only if last node deleted.

Line:

to_delete = prev.next
prev.next = to_delete.next
if to_delete == self.tail:
    self.tail = prev

💡 List now is [1, 3] after deletion.

delete

deleteAtIndex(1): decrement size

Decrease size counter by 1 to reflect node removal.

💡 Size now reflects two nodes in the list.

Line:

self.size -= 1

💡 Size is now 2, matching the updated list length.

compare

get(1): validate index

Check if index 1 is valid (0 <= 1 < size 2), so proceed to get value.

💡 Index validation prevents invalid access.

Line:

if index < 0 or index >= self.size:
    return -1

💡 Index 1 corresponds to node with val=3.

traverse

get(1): traverse to node at index

Start from dummy.next (node 1), move one step to node 3 at index 1.

💡 Traversal finds the node whose value we want to return.

Line:

curr = self.dummy.next
for _ in range(index):
    curr = curr.next

💡 Curr pointer now at node with val=3.

compare

get(1): return value of current node

Return the value of the node at index 1, which is 3.

💡 Returning the node's value completes the get operation.

Line:

return curr.val

💡 Value 3 is the correct output for get(1) after deletion.

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

class MyLinkedList:
    def __init__(self):
        self.dummy = Node(0)  # STEP 1
        self.tail = self.dummy  # STEP 1
        self.size = 0  # STEP 1

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:  # STEP 15,22
            return -1
        curr = self.dummy.next  # STEP 16,23
        for _ in range(index):
            curr = curr.next  # STEP 16,23
        return curr.val  # STEP 17,24

    def addAtHead(self, val: int) -> None:
        newNode = Node(val, self.dummy.next)  # STEP 2
        self.dummy.next = newNode  # STEP 3
        if self.size == 0:  # STEP 4
            self.tail = newNode
        self.size += 1  # STEP 5

    def addAtTail(self, val: int) -> None:
        newNode = Node(val)  # STEP 6
        self.tail.next = newNode  # STEP 7
        self.tail = newNode  # STEP 8
        self.size += 1  # STEP 9

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

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

📊

Design Linked List (Full Implementation) - Watch the Algorithm Execute, Step by Step

Watching each pointer move and node change live helps you understand how linked list operations work internally, beyond just reading code.

setup

0

insert

0

→

1

connect

0

→

1

connect

0

→

1

advance

0

→

1

insert

0

→

1

→

3

connect

0

→

1

→

3

advance

0

→

1

→

3

advance

0

→

1

→

3

compare

0

→

1

→

3

advance

0

→

1

→

3

insert

0

→

1

→

3

→

2

connect

0

→

1

→

3

→

2

advance

0

→

1

→

3

→

2

compare

0

→

1

→

3

→

2

advance

0

→

1

→

3

→

2

compare

0

→

1

→

3

→

2

Result: 2

compare

0

→

1

→

3

→

2

Result: 2

advance

0

→

1

→

3

→

2

Result: 2

detach

0

→

1

→

3

Result: 2

shrink

0

→

1

→

3

Result: 2

compare

0

→

1

→

3

Result: 2

advance

0

→

1

→

3

Result: 2

compare

0

→

1

→

3

Result: 3

Key Takeaways

✓ Using a dummy head node simplifies edge cases for insertions and deletions at the head.

Without dummy, special code is needed for head operations; dummy unifies logic.

✓ Maintaining a tail pointer allows O(1) insertions at the tail without traversal.

Without tail pointer, adding at tail requires traversing entire list, which is inefficient.

✓ Tracking size enables immediate index validity checks, preventing unnecessary traversal.

Size check quickly rejects invalid indices, saving time and avoiding errors.

Practice

1. You need to implement a browser history feature that supports visiting new URLs, moving backward by a number of steps, and moving forward by a number of steps. Which data structure approach best supports efficient visit, back, and forward operations with minimal time complexity?

easy

A. Using a single list with an index pointer to track the current page, slicing the list on visits to discard forward history.

B. Using a queue to store all visited URLs and dequeuing when moving back or forward.

C. Using a doubly linked list where each node stores a URL and pointers to previous and next pages.

D. Using two stacks: one for back history and one for forward history, pushing and popping URLs as navigation occurs.

Solution

1. Step 1: Understand operation requirements

   Visit must discard forward history, back and forward must move efficiently without scanning the entire history.

2. Step 2: Evaluate data structures

   Two stacks allow O(1) amortized push/pop for visit, back, and forward, efficiently managing history and forward pages.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Two stacks handle forward/back navigation efficiently [OK]

Hint: Two stacks efficiently manage back and forward navigation [OK]

Common Mistakes:

• Using a single list with slicing causes O(n) visit time
• Doubly linked list is correct but more complex
• Queue does not support backward navigation efficiently

2. You are given a singly linked list and a value x. The task is to reorder the list so that all nodes with values less than x come before nodes with values greater than or equal to x, while preserving the original relative order within each partition. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Extract all node values into arrays, reorder them, then rebuild the list.

B. Use two pointers to build two separate linked lists for nodes less than and greater or equal to x, then concatenate them.

C. Sort the entire linked list using merge sort and then split at value x.

D. Traverse the list once, rearranging nodes in-place by adjusting pointers without extra lists.

Solution

1. Step 1: Understand the problem constraints

   The problem requires partitioning the list around value x while preserving relative order and achieving O(n) time and O(1) space.

2. Step 2: Evaluate approaches

   Approach A uses extra arrays, so space is O(n). Approach B uses extra lists, so space is O(n). Approach D sorts the list, which is O(n log n) time. Only approach C rearranges nodes in-place in one pass with constant space.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   In-place rearrangement achieves O(n) time and O(1) space [OK]

Hint: In-place pointer rearrangement is O(1) space [OK]

Common Mistakes:

• Assuming sorting is needed to partition
• Using extra arrays or lists increases space
• Believing two separate lists always use constant space

3. Identify the bug in the following code snippet implementing the optimal approach to copy a list with random pointers:

medium

A. Line assigning curr.next.random = curr.random.next misses null check for curr.random

B. In Step 3, copy_curr is never advanced, causing incorrect separation

C. In Step 1, new_node is linked incorrectly to curr.next

D. The function returns copy_head before fully separating the lists

Solution

1. Step 1: Analyze Step 3 separation loop

   copy_curr is initialized but never advanced inside the loop, so copied list links are not updated correctly.

2. Step 2: Identify fix

   Adding copy_curr = copy_curr.next inside the loop after updating copy_curr.next fixes the bug.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without advancing copy_curr, copied list remains partially linked [OK]

Hint: Check if both original and copy pointers advance in separation loop [OK]

Common Mistakes:

• Forgetting to advance copy_curr in separation
• Assuming random pointer null checks are missing (they are present)
• Mislinking new_node in Step 1 (correct here)

4. What is the space complexity of the recursive reorder list approach that uses a helper function with recursion to reorder the list in place?

medium

A. O(n) -- recursion stack uses space proportional to list length

B. O(1) -- only constant extra pointers used

C. O(log n) -- recursion depth is halved each call

D. O(n^2) -- due to repeated pointer updates in recursion

Solution

1. Step 1: Identify recursion depth

   The helper function recurses once per node, so recursion depth is n.

2. Step 2: Calculate space usage

   Each recursive call adds stack frame, so total space is O(n), not constant or logarithmic.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion stack proportional to list length [OK]

Hint: Recursion depth equals list length -> O(n) space [OK]

Common Mistakes:

• Assuming constant space due to in-place changes
• Confusing recursion depth with log n
• Overestimating to quadratic space

5. Suppose the partition problem is modified so that nodes can be reused multiple times (e.g., the list represents a multiset with unlimited copies). Which modification to the optimal in-place partition algorithm correctly handles this scenario without breaking the algorithm?

hard

A. Convert the list to arrays, partition values, then rebuild the list to handle duplicates safely.

B. Use the same in-place pointer rearrangement but skip nodes already processed to avoid infinite loops.

C. Modify the algorithm to clone nodes when moving them to the less-than-x partition to preserve original nodes.

D. Use two separate lists with dummy heads and append clones of nodes to handle reuse.

Solution

1. Step 1: Understand the reuse constraint

   Nodes can be reused multiple times, so in-place rearrangement that moves nodes breaks because nodes are unique objects.

2. Step 2: Evaluate modifications

   In-place rearrangement cannot handle duplicates without cloning. Cloning in-place is complex and error-prone. Using arrays to store values and rebuild the list handles duplicates safely and cleanly.

3. Step 3: Compare cloning approaches

   Cloning nodes in-place or in two lists adds complexity and risks pointer errors. Arrays simplify the problem.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Rebuilding from arrays safely handles duplicates and reuse [OK]

Hint: Rebuild list from arrays to handle node reuse safely [OK]

Common Mistakes:

• Trying to rearrange nodes in-place with reuse
• Cloning nodes without updating pointers correctly
• Assuming pointer moves work with reused nodes