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. 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 buggy recursive code to convert a binary number in a linked list to an integer. Which line contains the subtle bug that causes incorrect output for single-node lists?

medium

A. Line X: using addition instead of bitwise OR to accumulate bits

B. Line 7: base case check for None node

C. Line 3: __init__ method of ListNode

D. Line 9: recursive call with node.next and updated acc

Solution

1. Step 1: Identify the accumulation operation

   The code uses bitwise OR instead of addition to combine bits: acc = (acc << 1) | node.val.

2. Step 2: Understand impact on single-node lists

   Bitwise OR correctly sets bits without carry, ensuring accurate accumulation for all list lengths.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Bitwise OR correctly sets bits without carry, addition may overflow [OK]

Hint: Use bitwise OR, not addition, to accumulate bits [OK]

Common Mistakes:

• Using + instead of | causes wrong bit accumulation
• Misunderstanding bitwise operations vs arithmetic
• Assuming addition and OR are interchangeable for bits

3. The following code attempts to implement the two stacks browser history. Identify the line containing the subtle bug that causes forward navigation to return outdated pages after visiting a new URL.

class BrowserHistory:
    def __init__(self, homepage: str):
        self.back_stack = [homepage]
        self.forward_stack = []

    def visit(self, url: str) -> None:
        self.back_stack.append(url)
        # Missing forward_stack.clear() here

    def back(self, steps: int) -> str:
        while steps > 0 and len(self.back_stack) > 1:
            self.forward_stack.append(self.back_stack.pop())
            steps -= 1
        return self.back_stack[-1]

    def forward(self, steps: int) -> str:
        while steps > 0 and self.forward_stack:
            self.back_stack.append(self.forward_stack.pop())
            steps -= 1
        return self.back_stack[-1]

medium

A. Line where back_stack.append(url) is called in visit

B. Line where forward_stack.clear() should be called but is missing in visit

C. Line where back_stack.pop() is called in back method

D. Line where forward_stack.pop() is called in forward method

Solution

1. Step 1: Identify visit method behavior

   Visit appends new URL but does not clear forward_stack, so forward history remains outdated.

2. Step 2: Understand impact on forward navigation

   Without clearing forward_stack, forward() returns stale pages that should have been discarded.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Clearing forward_stack on visit is essential to maintain correct forward history [OK]

Hint: Visit must clear forward history to avoid stale pages [OK]

Common Mistakes:

• Forgetting to clear forward stack on visit
• Incorrectly popping from back stack
• Mismanaging stack boundaries

4. Identify the bug in the following code snippet for splitting a linked list into k parts:

medium

A. Line where curr is advanced without checking if curr is None, causing AttributeError.

B. Line where tails[i].next is set to curr without checking if curr is None.

C. Line where tails[i].next is set to None, which breaks the list prematurely.

D. Line where dummy_heads are created, which wastes extra space.

Solution

1. Step 1: Analyze pointer advancement

   Inside the inner loop, curr is advanced with curr = curr.next without checking if curr is None.

2. Step 2: Identify potential error

   If curr is None, accessing curr.next raises AttributeError. The check must happen before advancing curr.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing None check before curr = curr.next causes runtime error [OK]

Hint: Always check curr is not None before accessing curr.next [OK]

Common Mistakes:

• Forgetting None check before pointer advance
• Incorrectly cutting list by setting next to None too early
• Misusing dummy heads

5. Suppose the problem is modified so that nodes can be reused multiple times (i.e., after reversing a group, nodes can appear again in subsequent groups). Which of the following changes to the algorithm correctly handles this scenario?

hard

A. Modify the algorithm to create new nodes for each group reversal to avoid modifying original nodes in place.

B. This problem cannot be solved by reversal; instead, use a queue to simulate repeated node usage.

C. Use recursion with memoization to store reversed groups and reuse them without modifying the original list.

D. Use the same iterative reversal approach but reset pointers to allow reusing nodes in multiple groups.

Solution

1. Step 1: Understand node reuse implication

   Reusing nodes means original nodes must remain unchanged or duplicated to appear multiple times.

2. Step 2: Evaluate algorithm modifications

   In-place reversal modifies nodes destructively, so creating new nodes for each group is necessary to preserve original nodes.

3. Step 3: Assess other options

   Resetting pointers (A) breaks list integrity; recursion with memoization (C) is complex and not standard; queue simulation (B) does not solve reversal reuse.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Duplicating nodes preserves original list for reuse [OK]

Hint: Node reuse requires duplication, not in-place reversal [OK]

Common Mistakes:

• Trying to reuse nodes in place
• Ignoring list integrity
• Assuming recursion memoization solves reuse