707. Design Linked List - Explanation

1. Singly Linked List

Intuition

A singly linked list stores elements in nodes where each node points to the next one. We use a dummy head node to simplify edge cases like inserting at the beginning or deleting the first element. The dummy head always exists, so we never have to handle a null head pointer. We also track the size to quickly validate indices without traversing the entire list.

Algorithm

Initialization: Create a dummy head node and set size to 0.
get(index): If the index is out of bounds, return -1. Otherwise, start from the node after the dummy head and traverse index times, then return the value.
addAtHead(val): Create a new node, point it to the current first real node, and update the dummy head's next pointer to the new node. Increment size.
addAtTail(val): Traverse from the dummy head to the last node, then append the new node. Increment size.
addAtIndex(index, val): If index is greater than size, do nothing. Otherwise, traverse to the node just before the target position, insert the new node by adjusting pointers, and increment size.
deleteAtIndex(index): If index is out of bounds, do nothing. Otherwise, traverse to the node before the target, skip over the target node by updating the next pointer, and decrement size.

class ListNode:
    def __init__(self, val: int):
        self.val = val
        self.next = None

class MyLinkedList:
    def __init__(self):
        self.head = ListNode(0)
        self.size = 0

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

    def addAtHead(self, val: int) -> None:
        node = ListNode(val)
        node.next = self.head.next
        self.head.next = node
        self.size += 1

    def addAtTail(self, val: int) -> None:
        node = ListNode(val)
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = node
        self.size += 1

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        cur = self.head
        for _ in range(index):
            cur = cur.next
        node = ListNode(val)
        node.next = cur.next
        cur.next = node
        self.size += 1

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

Time & Space Complexity

Time complexity:
- $O(1)$ time for initialization.
- $O(1)$ time for $addAtHead()$ .
- $O(n)$ time for $get()$ , $addAtTail()$ , $addAtIndex()$ , $deleteAtIndex()$ .
Space complexity: $O(n)$

2. Singly Linked List (Optimal)

Intuition

This approach refactors the singly linked list by introducing a helper function getPrev(index) that returns the node immediately before the target index. Since insertion and deletion both require access to the predecessor node, centralizing this logic reduces code duplication. The addAtHead() and addAtTail() operations now simply call addAtIndex(), making the implementation cleaner and easier to maintain.

Algorithm

Initialization: Create a dummy head node and set size to 0.
getPrev(index): Starting from the dummy head, traverse index steps and return that node.
get(index): If out of bounds, return -1. Otherwise, call getPrev(index) and return the value of its next node.
addAtHead(val): Call addAtIndex(0, val).
addAtTail(val): Call addAtIndex(size, val).
addAtIndex(index, val): If index is greater than size, return. Get the predecessor using getPrev(index), create a new node pointing to the predecessor's next, and update the predecessor's next to the new node. Increment size.
deleteAtIndex(index): If out of bounds, return. Get the predecessor using getPrev(index) and skip over the target node. Decrement size.

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

class MyLinkedList:
    def __init__(self):
        self.head = ListNode(0)
        self.size = 0

    def getPrev(self, index: int) -> ListNode:
        cur = self.head
        for _ in range(index):
            cur = cur.next
        return cur

    def get(self, index: int) -> int:
        if index >= self.size:
            return -1
        return self.getPrev(index).next.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        prev = self.getPrev(index)
        node = ListNode(val, prev.next)
        prev.next = node
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index >= self.size:
            return
        prev = self.getPrev(index)
        prev.next = prev.next.next
        self.size -= 1

Time & Space Complexity

Time complexity:
- $O(1)$ time for initialization.
- $O(1)$ time for $addAtHead()$ .
- $O(n)$ time for $get()$ , $addAtTail()$ , $addAtIndex()$ , $deleteAtIndex()$ .
Space complexity: $O(n)$

3. Doubly Linked List

Intuition

A doubly linked list adds a prev pointer to each node, allowing traversal in both directions. We use two sentinel nodes: a dummy head and a dummy tail. These sentinels eliminate null checks when inserting or deleting at the boundaries. Any real node is always between the head and tail sentinels, so insertion and deletion operations become symmetric and straightforward.

Algorithm

Initialization: Create dummy head and tail nodes. Link head's next to tail and tail's prev to head.
get(index): Start from the first real node (head's next) and traverse until the index is reached or the tail is hit. Return the value if valid, otherwise return -1.
addAtHead(val): Create a new node. Set its next to head's current next and its prev to head. Update the neighboring pointers to include the new node.
addAtTail(val): Create a new node. Set its prev to tail's current prev and its next to tail. Update the neighboring pointers accordingly.
addAtIndex(index, val): Traverse to the node currently at that index. Insert the new node just before it by updating prev and next pointers on both sides.
deleteAtIndex(index): Traverse to the target node. Connect its prev and next neighbors directly, removing the target from the list.

class ListNode:
    def __init__(self, val):
        self.val = val
        self.prev = None
        self.next = None

class MyLinkedList:

    def __init__(self):
        self.head = ListNode(0)
        self.tail = ListNode(0)
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, index: int) -> int:
        cur = self.head.next
        while cur and index > 0:
            cur = cur.next
            index -= 1
        if cur and cur != self.tail and index == 0:
            return cur.val
        return -1

    def addAtHead(self, val: int) -> None:
        node, next, prev = ListNode(val), self.head.next, self.head
        prev.next = node
        next.prev = node
        node.next = next
        node.prev = prev

    def addAtTail(self, val: int) -> None:
        node, next, prev = ListNode(val), self.tail, self.tail.prev
        prev.next = node
        next.prev = node
        node.next = next
        node.prev = prev

    def addAtIndex(self, index: int, val: int) -> None:
        cur = self.head.next
        while cur and index > 0:
            cur = cur.next
            index -= 1
        if cur and index == 0:
            node, next, prev = ListNode(val), cur, cur.prev
            prev.next = node
            next.prev = node
            node.next = next
            node.prev = prev


    def deleteAtIndex(self, index: int) -> None:
        cur = self.head.next
        while cur and index > 0:
            cur = cur.next
            index -= 1
        if cur and cur != self.tail and index == 0:
            next, prev = cur.next, cur.prev
            next.prev = prev
            prev.next = next

Time & Space Complexity

Time complexity:
- $O(1)$ time for initialization.
- $O(1)$ time for $addAtHead()$ , $addAtTail()$ .
- $O(n)$ time for $get()$ , $addAtIndex()$ , $deleteAtIndex()$ .
Space complexity: $O(n)$

4. Doubly Linked List (Optimal)

Intuition

This optimization improves traversal time by choosing the shorter path. For indices in the first half of the list, we traverse forward from the head. For indices in the second half, we traverse backward from the tail. The getPrev(index) helper returns the predecessor node using this bidirectional approach, cutting worst-case traversal roughly in half on average.

Algorithm

Initialization: Create dummy head and tail nodes linked to each other. Set size to 0.
getPrev(index): If index <= size / 2, traverse forward from head for index steps. Otherwise, traverse backward from tail for size - index + 1 steps. Return the predecessor node.
get(index): If out of bounds, return -1. Call getPrev(index) and return the value of its next node.
addAtHead(val): Call addAtIndex(0, val).
addAtTail(val): Call addAtIndex(size, val).
addAtIndex(index, val): If index is greater than size, return. Use getPrev(index) to find the predecessor, create the new node, and wire it between the predecessor and its current next. Increment size.
deleteAtIndex(index): If out of bounds, return. Use getPrev(index) to find the predecessor, then bypass the target node by linking predecessor directly to the node after the target. Decrement size.

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

class MyLinkedList:
    def __init__(self):
        self.head = ListNode(0)
        self.tail = ListNode(0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def getPrev(self, index: int) -> ListNode:
        if index <= self.size // 2:
            cur = self.head
            for _ in range(index):
                cur = cur.next
        else:
            cur = self.tail
            for _ in range(self.size - index + 1):
                cur = cur.prev
        return cur

    def get(self, index: int) -> int:
        if index >= self.size:
            return -1
        return self.getPrev(index).next.val

    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index: int, val: int) -> None:
        if index > self.size:
            return
        node = ListNode(val)
        prev = self.getPrev(index)
        next = prev.next
        prev.next = node
        node.prev = prev
        node.next = next
        next.prev = node
        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index >= self.size:
            return
        prev = self.getPrev(index)
        cur = prev.next
        next = cur.next
        prev.next = next
        next.prev = prev
        self.size -= 1

Time & Space Complexity

Time complexity:
- $O(1)$ time for initialization.
- $O(1)$ time for $addAtHead()$ , $addAtTail()$ .
- $O(n)$ time for $get()$ , $addAtIndex()$ , $deleteAtIndex()$ .
Space complexity: $O(n)$

Common Pitfalls

Using Wrong Bound Check for addAtIndex vs deleteAtIndex

The addAtIndex allows inserting at position size (appending), but deleteAtIndex does not allow deleting at position size. Using the same condition for both causes bugs.

# addAtIndex: index == size is valid (append)
def addAtIndex(self, index: int, val: int) -> None:
    if index > self.size:  # Note: > not >=
        return

# deleteAtIndex: index == size is invalid
def deleteAtIndex(self, index: int) -> None:
    if index >= self.size:  # Note: >= not >
        return

Forgetting to Update Size

Every insertion must increment size and every deletion must decrement it. Forgetting this causes subsequent operations to use stale bounds, leading to crashes or incorrect behavior.

# Wrong: forgot to update size
def addAtHead(self, val: int) -> None:
    node = ListNode(val)
    node.next = self.head.next
    self.head.next = node
    # Missing: self.size += 1

# Correct
def addAtHead(self, val: int) -> None:
    node = ListNode(val)
    node.next = self.head.next
    self.head.next = node
    self.size += 1

Incorrect Pointer Order When Inserting

When inserting a node, you must set the new node's next pointer before updating the previous node's next. Reversing this order loses the reference to the rest of the list.

# Wrong: loses reference to rest of list
prev.next = node
node.next = prev.next  # node.next now points to itself!

# Correct: set new node's next first
node.next = prev.next
prev.next = node