Skip to content
← All posts

Design Linked List: Build a Linked List From Scratch

5 min read
leetcodeproblemmediumlinked-listsdesign

Design Linked List is LeetCode problem 707. It asks you to implement a singly linked list class from scratch, supporting five operations: get, addAtHead, addAtTail, addAtIndex, and deleteAtIndex. This is not a tricky algorithm problem. It is a construction problem. You need clean pointer management, and the best way to get that is with a dummy head node.

The problem

Design a linked list that supports the following operations:

  • get(index) returns the value at the given index, or -1 if the index is invalid.
  • addAtHead(val) inserts a node with value val before the first element.
  • addAtTail(val) appends a node with value val as the last element.
  • addAtIndex(index, val) inserts a node before the index-th node. If index equals the length, append to the tail. If index is greater than the length, do nothing.
  • deleteAtIndex(index) deletes the index-th node if the index is valid.
singly linked list with dummy headD123nulldummyidx 0idx 1idx 2head
A dummy head node simplifies insertions and deletions. Real data starts at dummy.next (index 0).

Why a dummy head node?

The trickiest part of linked list implementation is handling the head. Without a dummy node, every operation needs special-case logic: "Is the list empty? Am I inserting at the head? Am I deleting the head?" That means if branches everywhere and bugs hiding in each one.

A dummy head node eliminates all of that. The dummy node is always present. It never stores real data. The first real node is always dummy.next. Every insertion and deletion becomes the same operation: find the node before the target position, then update pointers. No special cases.

Practice this pattern

The code

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

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

    def get(self, index):
        if index < 0 or index >= self.size:
            return -1
        curr = self.dummy.next
        for _ in range(index):
            curr = curr.next
        return curr.val

    def addAtHead(self, val):
        self.addAtIndex(0, val)

    def addAtTail(self, val):
        self.addAtIndex(self.size, val)

    def addAtIndex(self, index, val):
        if index < 0 or index > self.size:
            return
        prev = self.dummy
        for _ in range(index):
            prev = prev.next
        new_node = ListNode(val)
        new_node.next = prev.next
        prev.next = new_node
        self.size += 1

    def deleteAtIndex(self, index):
        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

Notice how addAtHead and addAtTail both delegate to addAtIndex. This is possible because the dummy head makes index 0 insertions behave identically to any other index. One method handles all three cases.

Tracking self.size lets you validate indices in O(1) before walking the list. Without it, you would need to walk to the end just to check if an index is valid.

Visual walkthrough

Let's trace through the LeetCode example sequence: addAtHead(1), addAtTail(3), addAtIndex(1, 2), get(1), deleteAtIndex(1).

addAtHead(1): Insert value 1 at the head (after dummy).

D1null

Set new_node.next = dummy.next, then dummy.next = new_node. Size becomes 1.

addAtTail(3): Insert value 3 at the tail.

D13null

Walk to the last node (1), then set last.next = new_node. Size becomes 2.

addAtIndex(1, 2): Insert value 2 at index 1.

D123null

Walk to node at index 0 (value 1). Splice new node between 1 and 3. Size becomes 3.

get(1): Retrieve the value at index 1.

D123null

Start at dummy.next, walk 1 step forward. Return node.val = 2.

deleteAtIndex(1): Remove the node at index 1.

D13null

Walk to the node before index 1 (value 1). Set prev.next = prev.next.next, skipping over 2. Size becomes 2.

Every operation follows the same pattern: start at the dummy node, walk forward to the position you need, then update one or two pointers. The dummy head means you never have to worry about null checks at the beginning of the list.

Drill this solution with spaced repetition

Complexity analysis

OperationTimeSpaceReasoning
get(index)O(n)O(1)Walk up to n nodes to reach the target index.
addAtHead(val)O(1)O(1)Insert directly after the dummy node.
addAtTail(val)O(n)O(1)Walk to the end of the list first.
addAtIndex(index, val)O(n)O(1)Walk to the node before the target index.
deleteAtIndex(index)O(n)O(1)Walk to the node before the target index.

You could optimize addAtTail to O(1) by maintaining a tail pointer, but LeetCode does not require it and it adds complexity.

The building blocks

This problem teaches two reusable pieces that appear across many linked list problems.

Dummy head technique

Create a sentinel node that sits before the real head. All operations start from the dummy, so you never special-case an empty list or a head insertion. You will use this same technique in merge two sorted lists, partition list, and remove elements from a linked list.

Walking to a position

To operate on index i, walk a pointer i steps from the dummy node. For insertions and deletions, you actually want the node before the target, so you walk i steps from the dummy (which lands on the node at index i - 1). This "find the predecessor" pattern is the backbone of singly linked list manipulation.

Edge cases to watch for

  • Get with invalid index. Negative index or index at or beyond size should return -1. The size check handles this.
  • Add at index 0 on an empty list. The dummy head makes this work automatically. prev is the dummy, prev.next is null, and the new node gets inserted.
  • Add at index equal to size. This appends to the tail. The loop walks prev to the last real node, and prev.next is null. The new node slots in cleanly.
  • Add at index greater than size. The bounds check catches this and returns early.
  • Delete the only node. prev is the dummy, prev.next is the node to delete, and prev.next.next is null. The dummy's next becomes null. The list is empty again.

From understanding to recall

Design problems like this one feel easy when you read the solution. The danger is assuming you will remember the details. Which pointer do you update first during insertion? How do you handle the bounds check for addAtIndex versus deleteAtIndex (one uses >, the other uses >=)? These small details are where bugs hide during interviews.

Spaced repetition locks in the muscle memory. You type the solution from scratch today, again in a few days, and again next week. After a few reps, the dummy head pattern and the pointer update order become automatic. You stop thinking about edge cases because the code structure handles them for you.

Try CodeBricks free

Related posts