Design Linked List — Solution in Python, Java & C++
Design Linked List solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on simulation.
Design Linked List is a medium coding problem on simulation, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Simulation
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Implement your own linked list (singly or doubly linked, without the built-in list type). Positions are 0-indexed. Write the class MyLinkedList:
MyLinkedList()creates an empty list.int get(int index)returns the value of the node at positionindex, or-1ifindexis out of range.void addAtHead(int value)inserts a node withvaluebefore the first node; it becomes the new head.void addAtTail(int value)appends a node withvalueafter the last node.void addAtIndex(int index, int value)inserts a node withvalueso that it ends up at positionindex. Ifindexequals the length it is appended; ifindexis greater than the length nothing is inserted.void deleteAtIndex(int index)removes the node at positionindexif it exists.
The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every void method.
Example 1
Input: ["MyLinkedList","addAtHead","addAtTail","addAtIndex","get","deleteAtIndex","get"]
[[],[1],[3],[1,2],[1],[1],[1]]
Output: [null,null,null,null,2,null,3]
Explanation: The list goes [1] → [1,3] → [1,2,3], so position 1 holds 2. Deleting position 1 leaves [1,3], and position 1 now holds 3.
Example 2
Input: ["MyLinkedList","get","addAtIndex","addAtIndex","addAtTail","deleteAtIndex","get","get"]
[[],[0],[1,9],[0,4],[6],[5],[0],[1]]
Output: [null,-1,null,null,null,null,4,6]
Explanation: An empty list has no position 0. Inserting at index 1 of an empty list is out of range and ignored; index 0 works. After [4,6], deleting position 5 does nothing.
Constraints
0 <= index, value <= 1000At most 2000 calls are made to get, addAtHead, addAtTail, addAtIndex and deleteAtIndex
Hints for Design Linked List
Hint 1
Every operation needs to reach a position, so they all share one walk: from the head, follow
nextpointersindextimes.Hint 2
Inserting or deleting at position
indexchanges the node before it. A dummy (sentinel) node in front of the head means every position has a node before it, the head included.Hint 3
Keep the length in a counter, so out-of-range indexes are rejected before walking.
How to solve Design Linked List
A singly linked list with a dummy node before the head and a size counter. To act at position i, walk i steps from the dummy to reach the node just before it; inserting and deleting then rewire one next pointer.
Approach
- Keep
dummy(itsnextis the head) andsize. get(i): ifi >= sizereturn -1; otherwise walki + 1steps fromdummyand return that node's value.addAtIndex(i, v): ifi > sizedo nothing. Otherwise walkisteps fromdummyto nodep, create a node withnext = p.next, setp.nextto it, incrementsize.addAtHead(v)isaddAtIndex(0, v);addAtTail(v)isaddAtIndex(size, v).deleteAtIndex(i): ifi >= sizedo nothing. Otherwise walkisteps top, setp.next = p.next.next, decrementsize.
Why it works
After i steps from the dummy you stand on the node before position i (the dummy itself for i = 0), so splicing a node in after it puts the new node exactly at position i, and unlinking its successor removes exactly position i. The size check makes the walk never run off the end.
Complexity
- Time —
O(i) for an operation at position i (O(1) at the head); O(n) for addAtTail without a tail pointer - Space —
O(n)
Pitfalls
addAtIndexwithindex == sizeappends; onlyindex > sizeis ignored.- Without a dummy node, inserting or deleting at position 0 needs separate head-handling code — the usual source of bugs.
- Update the size on every successful insert and delete, and only then.
Reference solution
Python
class Node:
__slots__ = ("value", "next")
def __init__(self, value, nxt=None):
self.value = value
self.next = nxt
class MyLinkedList:
def __init__(self):
self.dummy = Node(0) # dummy.next is the head
self.size = 0
def _before(self, index):
p = self.dummy
for _ in range(index):
p = p.next
return p
def get(self, index: int) -> int:
if index >= self.size:
return -1
return self._before(index).next.value
def addAtHead(self, value: int) -> None:
self.addAtIndex(0, value)
def addAtTail(self, value: int) -> None:
self.addAtIndex(self.size, value)
def addAtIndex(self, index: int, value: int) -> None:
if index > self.size:
return
p = self._before(index)
p.next = Node(value, p.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index >= self.size:
return
p = self._before(index)
p.next = p.next.next
self.size -= 1Java
class MyLinkedList {
private static class Node {
int value;
Node next;
Node(int value, Node next) { this.value = value; this.next = next; }
}
private Node dummy = new Node(0, null); // dummy.next is the head
private int size = 0;
public MyLinkedList() {
}
private Node before(int index) {
Node p = dummy;
for (int i = 0; i < index; i++) p = p.next;
return p;
}
public int get(int index) {
if (index >= size) return -1;
return before(index).next.value;
}
public void addAtHead(int value) {
addAtIndex(0, value);
}
public void addAtTail(int value) {
addAtIndex(size, value);
}
public void addAtIndex(int index, int value) {
if (index > size) return;
Node p = before(index);
p.next = new Node(value, p.next);
size++;
}
public void deleteAtIndex(int index) {
if (index >= size) return;
Node p = before(index);
p.next = p.next.next;
size--;
}
}C++
class MyLinkedList {
struct Node {
int value;
Node* next;
};
Node* dummy = new Node{0, nullptr}; // dummy->next is the head
int size = 0;
Node* before(int index) {
Node* p = dummy;
for (int i = 0; i < index; i++) p = p->next;
return p;
}
public:
MyLinkedList() {}
~MyLinkedList() {
while (dummy) { Node* next = dummy->next; delete dummy; dummy = next; }
}
int get(int index) {
if (index >= size) return -1;
return before(index)->next->value;
}
void addAtHead(int value) {
addAtIndex(0, value);
}
void addAtTail(int value) {
addAtIndex(size, value);
}
void addAtIndex(int index, int value) {
if (index > size) return;
Node* p = before(index);
p->next = new Node{value, p->next};
size++;
}
void deleteAtIndex(int index) {
if (index >= size) return;
Node* p = before(index);
Node* dead = p->next;
p->next = dead->next;
delete dead;
size--;
}
};JavaScript
var MyLinkedList = function() {
this.dummy = { value: 0, next: null }; // dummy.next is the head
this.size = 0;
};
MyLinkedList.prototype.before = function(index) {
var p = this.dummy;
for (var i = 0; i < index; i++) p = p.next;
return p;
};
MyLinkedList.prototype.get = function(index) {
if (index >= this.size) return -1;
return this.before(index).next.value;
};
MyLinkedList.prototype.addAtHead = function(value) {
this.addAtIndex(0, value);
};
MyLinkedList.prototype.addAtTail = function(value) {
this.addAtIndex(this.size, value);
};
MyLinkedList.prototype.addAtIndex = function(index, value) {
if (index > this.size) return;
var p = this.before(index);
p.next = { value: value, next: p.next };
this.size++;
};
MyLinkedList.prototype.deleteAtIndex = function(index) {
if (index >= this.size) return;
var p = this.before(index);
p.next = p.next.next;
this.size--;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.