LeetCode Problem 707

Difficulty: 🟡 Medium
Topics: Linked List, Design

Solution

LeetCode 707 - Design Linked List

Problem Understanding

This problem asks us to implement our own linked list data structure from scratch without using any built in linked list library. The linked list must support several common operations such as retrieving a value at a specific index, inserting nodes at different positions, and deleting nodes.

The list is 0-indexed, which means the first node is at index 0, the second node is at index 1, and so on.

We need to implement the following operations:

• get(index) returns the value stored at the given index
• addAtHead(val) inserts a new node at the beginning
• addAtTail(val) inserts a new node at the end
• addAtIndex(index, val) inserts a node before the specified index
• deleteAtIndex(index) removes the node at the specified index

The important part of this problem is correctly handling pointer manipulation while maintaining the linked list structure.

The constraints are fairly small, with at most 2000 operations. This means performance requirements are not extremely strict, but we still want a clean and efficient implementation.

A linked list differs from an array because nodes are connected through references instead of contiguous memory locations. This makes insertion and deletion efficient once we reach the correct position, but random access becomes slower because we must traverse node by node.

Several edge cases are especially important:

• Accessing an invalid index should return -1
• Inserting at an index larger than the current size should do nothing
• Inserting at index equal to the current size should append to the end
• Deleting from an empty list should do nothing
• Operations involving the head node require special handling in many implementations

To simplify edge case handling, we will use a dummy head node.

Approaches

Brute Force Approach

A brute force approach would be to internally store all values in a dynamic array or Python list and manually simulate linked list operations.

For example:

• get(index) would directly access the array
• addAtHead(val) would insert at position 0
• addAtTail(val) would append
• addAtIndex(index, val) would shift elements to make room
• deleteAtIndex(index) would shift elements left after deletion

This works correctly because arrays can represent ordered sequences. However, insertion and deletion in the middle require shifting many elements, which is inefficient for large inputs.

More importantly, the problem explicitly asks us to design a linked list implementation, so using an array defeats the purpose of the exercise.

Optimal Approach

The optimal approach is to implement an actual singly linked list.

Each node stores:

• The node value
• A pointer to the next node

We also maintain:

• A dummy head node
• The current size of the linked list

The dummy head node is a common design technique that simplifies insertion and deletion logic because every real node always has a predecessor.

The main insight is that linked lists excel at insertion and deletion once we locate the correct position. Since we only need sequential traversal, a singly linked list is sufficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n) per insertion/deletion	O(n)	Uses array shifting operations
Optimal	O(n) per traversal operation	O(n)	Real singly linked list implementation

Algorithm Walkthrough

Data Structure Design

We define a Node structure containing:

• val
• next

We also maintain:

• dummy, a dummy head node
• size, the number of real nodes

Operations

1. Initialize the linked list

Create a dummy node whose next pointer initially points to None. Set the size to 0. 2. Get a value at an index

First validate the index. If the index is negative or greater than or equal to the size, return -1.

Otherwise, start traversal from dummy.next and move forward index times. Return the value of the reached node. 3. Add at head

Create a new node.

Set its next pointer to the current first node.

Update dummy.next to point to the new node.

Increase the size. 4. Add at tail

Traverse until reaching the final node.

Attach the new node at the end.

Increase the size. 5. Add at index

If the index is greater than the size, do nothing.

If the index is valid, traverse to the node immediately before the insertion position.

Insert the new node by updating pointers carefully:

• newNode.next = prev.next
• prev.next = newNode

Increase the size. 6. Delete at index

Validate the index.

Traverse to the node immediately before the target node.

Remove the target node by skipping it:

• prev.next = prev.next.next

Decrease the size.

Why it works

The linked list always maintains a valid chain of nodes because every insertion and deletion updates pointers consistently.

The dummy head guarantees that every node, including the real head, has a predecessor. This removes special cases for head operations and ensures pointer updates are uniform across all operations.

The size variable guarantees proper bounds checking, preventing invalid memory access and ensuring operations behave according to the problem specification.

Python Solution

class Node:
    def __init__(self, val: int = 0, next_node=None):
        self.val = val
        self.next = next_node

class MyLinkedList:

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

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

        current = self.dummy.next

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

        return current.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 < 0 or index > self.size:
            return

        prev = self.dummy

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

        new_node = Node(val)

        new_node.next = prev.next
        prev.next = new_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

# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

The implementation begins with a separate Node class that stores the node value and a pointer to the next node.

The MyLinkedList constructor initializes two important members:

• dummy, which is the dummy head node
• size, which tracks the number of real nodes

The get method first validates the index. If the index is invalid, it immediately returns -1. Otherwise, it traverses from the first real node until reaching the requested position.

The addAtHead and addAtTail methods reuse addAtIndex, which avoids duplicate insertion logic.

The addAtIndex method traverses to the predecessor node before insertion. This is critical because singly linked lists cannot move backward, so we need the previous node to reconnect pointers properly.

The deleteAtIndex method similarly traverses to the predecessor and bypasses the target node.

Using a dummy node greatly simplifies both insertion and deletion because the predecessor always exists.

Go Solution

package main

type Node struct {
	val  int
	next *Node
}

type MyLinkedList struct {
	dummy *Node
	size  int
}

func Constructor() MyLinkedList {
	return MyLinkedList{
		dummy: &Node{},
		size:  0,
	}
}

func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index >= this.size {
		return -1
	}

	current := this.dummy.next

	for i := 0; i < index; i++ {
		current = current.next
	}

	return current.val
}

func (this *MyLinkedList) AddAtHead(val int) {
	this.AddAtIndex(0, val)
}

func (this *MyLinkedList) AddAtTail(val int) {
	this.AddAtIndex(this.size, val)
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index < 0 || index > this.size {
		return
	}

	prev := this.dummy

	for i := 0; i < index; i++ {
		prev = prev.next
	}

	newNode := &Node{
		val: val,
	}

	newNode.next = prev.next
	prev.next = newNode

	this.size++
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index >= this.size {
		return
	}

	prev := this.dummy

	for i := 0; i < index; i++ {
		prev = prev.next
	}

	prev.next = prev.next.next

	this.size--
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * obj := Constructor()
 * param_1 := obj.Get(index)
 * obj.AddAtHead(val)
 * obj.AddAtTail(val)
 * obj.AddAtIndex(index,val)
 * obj.DeleteAtIndex(index)
 */

The Go implementation closely mirrors the Python solution, but there are a few language specific details.

Go uses explicit pointer types such as *Node for linked references. Memory allocation is handled using &Node{}.

Unlike Python, Go does not have None, so we use nil for missing pointers.

Methods are attached to the MyLinkedList struct using pointer receivers so modifications affect the original linked list instance.

Worked Examples

Example 1

Input:

["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]

Step by Step Trace

Operation	Linked List State	Explanation
Initialize	empty	Dummy node only
addAtHead(1)	1	Insert 1 at beginning
addAtTail(3)	1 -> 3	Append 3
addAtIndex(1, 2)	1 -> 2 -> 3	Insert 2 before index 1
get(1)	returns 2	Node at index 1 is 2
deleteAtIndex(1)	1 -> 3	Remove node containing 2
get(1)	returns 3	Node at index 1 is now 3

Internal Pointer View

After addAtIndex(1, 2):

dummy -> 1 -> 2 -> 3

After deleteAtIndex(1):

dummy -> 1 -------> 3

The node containing 2 is skipped.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Traversal may scan the entire list
Space	O(n)	One node per stored element

The most expensive operations are insertion, deletion, and retrieval because singly linked lists require sequential traversal from the head.

Although insertion itself is constant time once the location is found, locating the position requires up to O(n) traversal.

The space complexity is linear because every inserted value requires its own node object.

Test Cases

# Basic example from problem statement
linked_list = MyLinkedList()
linked_list.addAtHead(1)
linked_list.addAtTail(3)
linked_list.addAtIndex(1, 2)

assert linked_list.get(1) == 2  # middle insertion

linked_list.deleteAtIndex(1)

assert linked_list.get(1) == 3  # deletion check

# Empty list access
linked_list = MyLinkedList()

assert linked_list.get(0) == -1  # invalid access on empty list

# Add at head repeatedly
linked_list = MyLinkedList()

linked_list.addAtHead(1)
linked_list.addAtHead(2)
linked_list.addAtHead(3)

assert linked_list.get(0) == 3  # newest head
assert linked_list.get(1) == 2
assert linked_list.get(2) == 1

# Add at tail repeatedly
linked_list = MyLinkedList()

linked_list.addAtTail(1)
linked_list.addAtTail(2)
linked_list.addAtTail(3)

assert linked_list.get(2) == 3  # tail insertion

# Insert at exact size
linked_list = MyLinkedList()

linked_list.addAtTail(1)
linked_list.addAtIndex(1, 2)

assert linked_list.get(1) == 2  # append via addAtIndex

# Insert beyond size
linked_list = MyLinkedList()

linked_list.addAtTail(1)
linked_list.addAtIndex(5, 10)

assert linked_list.get(1) == -1  # insertion ignored

# Delete head node
linked_list = MyLinkedList()

linked_list.addAtTail(1)
linked_list.addAtTail(2)

linked_list.deleteAtIndex(0)

assert linked_list.get(0) == 2  # head deleted

# Delete tail node
linked_list = MyLinkedList()

linked_list.addAtTail(1)
linked_list.addAtTail(2)

linked_list.deleteAtIndex(1)

assert linked_list.get(1) == -1  # tail deleted

# Delete invalid index
linked_list = MyLinkedList()

linked_list.addAtTail(1)

linked_list.deleteAtIndex(5)

assert linked_list.get(0) == 1  # unchanged

# Mixed operations
linked_list = MyLinkedList()

linked_list.addAtHead(10)
linked_list.addAtTail(20)
linked_list.addAtIndex(1, 15)
linked_list.deleteAtIndex(0)

assert linked_list.get(0) == 15
assert linked_list.get(1) == 20

Test	Why
Basic example	Verifies all core operations
Empty list access	Confirms invalid index handling
Multiple head insertions	Ensures head updates correctly
Multiple tail insertions	Ensures traversal to tail works
Insert at exact size	Validates append behavior
Insert beyond size	Ensures invalid insertion is ignored
Delete head node	Tests special case near beginning
Delete tail node	Tests end removal
Delete invalid index	Ensures list remains unchanged
Mixed operations	Validates overall consistency

Edge Cases

Accessing an Invalid Index

One of the most common bugs in linked list implementations is failing to validate indices correctly. If get() is called with an index outside the valid range, traversal could continue into a None reference and cause runtime errors.

This implementation prevents that by checking:

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

This guarantees traversal only occurs for valid positions.

Inserting Into an Empty List

An empty list can be tricky because there are no real nodes yet. Without a dummy node, inserting at the head often requires special logic.

The dummy node removes this complexity. Even when the list is empty:

dummy -> None

Insertion simply reconnects pointers normally:

dummy -> newNode

No special handling is needed.

Deleting the Head Node

Deleting the first real node is another common source of pointer bugs. In traditional singly linked lists, removing the head often requires reassigning the head pointer.

Because this implementation uses a dummy node, the predecessor of the first real node always exists. Deletion works exactly the same as any other node removal:

prev.next = prev.next.next

This keeps the logic simple and consistent.