LeetCode 707: Design Linked List

Problem Restatement

We need to design a linked list from scratch.

The implementation may use either a singly linked list or a doubly linked list. This guide uses a singly linked list.

A singly linked list node stores two things:

The linked list is 0-indexed.

We need to implement the MyLinkedList class with these operations:

For addAtIndex(index, val):

Input and Output

The class shape is:

class MyLinkedList:

    def __init__(self):
        ...

    def get(self, index: int) -> int:
        ...

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

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

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

    def deleteAtIndex(self, index: int) -> None:
        ...

Examples

Example:

myLinkedList = MyLinkedList()
myLinkedList.addAtHead(1)
myLinkedList.addAtTail(3)
myLinkedList.addAtIndex(1, 2)
myLinkedList.get(1)
myLinkedList.deleteAtIndex(1)
myLinkedList.get(1)

Step by step:

First Thought: Track Only the Head

A basic singly linked list can be stored with only one pointer:

self.head

This works, but operations at index 0 need special handling.

For example, inserting at the head changes self.head.

Deleting at the head also changes self.head.

These special cases make the code easier to get wrong.

Key Insight

Use a dummy head node.

The dummy node does not store a real list value. It always sits before the first real node.

dummy -> first -> second -> third

With a dummy head, inserting at index 0 becomes the same as inserting after the dummy node.

Deleting index 0 becomes the same as deleting the node after the dummy node.

This removes special cases for the head.

Also keep a size counter:

self.size

The size counter lets us check invalid indices quickly.

Algorithm

Use a node class:

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

The linked list stores:

self.dummy
self.size

For get(index):

1. If index < 0 or index >= size, return -1.
2. Start at the first real node.
3. Move forward index times.
4. Return the node value.

For addAtHead(val):

1. Insert at index 0.

For addAtTail(val):

1. Insert at index size.

For addAtIndex(index, val):

1. If index > size, do nothing.
2. If index < 0, treat it like 0.
3. Move to the node before the insertion position.
4. Link the new node into the list.
5. Increase size.

For deleteAtIndex(index):

1. If index < 0 or index >= size, do nothing.
2. Move to the node before the target.
3. Skip the target node.
4. Decrease size.

Correctness

The list stores all real nodes after the dummy head. The dummy head is never returned by get and is never counted in size.

For get(index), the method first rejects every invalid index. For a valid index, starting from the first real node and moving forward index times reaches exactly the node at that 0-based position. Returning that node’s value is therefore correct.

For addAtIndex(index, val), if index > size, the requested position is beyond the end of the list, so doing nothing follows the required behavior. If index == size, the method moves to the current last node and inserts after it, so the new value is appended. If 0 <= index < size, the method moves to the node just before the current node at index, then rewires pointers so the new node points to the old node at index, and the previous node points to the new node. Thus the new value is inserted before the old node at index.

For addAtHead and addAtTail, both call addAtIndex with indices 0 and size, so they are correct by the same reasoning.

For deleteAtIndex(index), invalid indices are ignored. For a valid index, the method moves to the node before the target and changes its next pointer to skip the target. This removes exactly the node at index while preserving the order of all other nodes.

After every insertion, size increases by one. After every valid deletion, size decreases by one. Therefore size always matches the number of real nodes in the list.

Complexity

Let n be the current list length.

The list itself uses O(n) storage for its nodes.

Implementation

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

class MyLinkedList:

    def __init__(self):
        self.dummy = ListNode()
        self.size = 0

    def get(self, index: int) -> int:
        if index < 0 or index >= self.size:
            return -1

        cur = self.dummy.next

        for _ in range(index):
            cur = cur.next

        return cur.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

        if index < 0:
            index = 0

        prev = self.dummy

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

        node = ListNode(val)
        node.next = prev.next
        prev.next = node

        self.size += 1

    def deleteAtIndex(self, index: int) -> None:
        if index < 0 or index >= self.size:
            return

        prev = self.dummy

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

        prev.next = prev.next.next
        self.size -= 1

Code Explanation

The node class stores a value and a pointer to the next node:

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

The linked list starts with a dummy node and size 0:

self.dummy = ListNode()
self.size = 0

The get method rejects invalid indices:

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

Then it starts at the first real node:

cur = self.dummy.next

Moving forward index times reaches the requested node:

for _ in range(index):
    cur = cur.next

addAtHead and addAtTail reuse the general insertion method:

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

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

For insertion, an index greater than the size is invalid:

if index > self.size:
    return

A negative index is treated as insertion at the head:

if index < 0:
    index = 0

We move to the node before the insertion point:

prev = self.dummy

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

Then we link the new node into the list:

node = ListNode(val)
node.next = prev.next
prev.next = node

For deletion, invalid indices are ignored:

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

Then we move to the previous node and skip the target:

prev.next = prev.next.next

Testing

def to_list(linked_list):
    values = []
    cur = linked_list.dummy.next

    while cur:
        values.append(cur.val)
        cur = cur.next

    return values

def test_my_linked_list():
    linked = MyLinkedList()

    linked.addAtHead(1)
    assert to_list(linked) == [1]

    linked.addAtTail(3)
    assert to_list(linked) == [1, 3]

    linked.addAtIndex(1, 2)
    assert to_list(linked) == [1, 2, 3]

    assert linked.get(1) == 2

    linked.deleteAtIndex(1)
    assert to_list(linked) == [1, 3]

    assert linked.get(1) == 3

    linked.addAtIndex(10, 9)
    assert to_list(linked) == [1, 3]

    linked.deleteAtIndex(10)
    assert to_list(linked) == [1, 3]

    linked.addAtIndex(0, 5)
    assert to_list(linked) == [5, 1, 3]

    linked.deleteAtIndex(0)
    assert to_list(linked) == [1, 3]

    print("all tests passed")

test_my_linked_list()

Test coverage: