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.