Design Linked List
Design Linked List is a medium design data structures problem solved with the linked lists pattern.
The best approach, dummy head + size counter, runs in O(index) per operation time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from singly linked list without a dummy up.
Problem
Implement your own linked list with get(index), addAtHead(val), addAtTail(val), addAtIndex(index, val) and deleteAtIndex(index), using 0-based indices.
Examples
Example 1
- Input
addAtHead(1); addAtTail(3); addAtIndex(1, 2); get(1); deleteAtIndex(1); get(1)- Output
2, 3- Why
- List goes 1 → 1,3 → 1,2,3 → 1,3.
Constraints
0 <= index, val <= 1000; at most 2000 calls.- Invalid indices: get returns -1; add/delete do nothing.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (1 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Singly linked list without a dummy | O(index) per operation | O(n) |
| Dummy head + size counter | O(index) per operation | O(n) |
1Singly linked list without a dummy
O(index) per operationO(n)Handle index 0 separately for add and delete, and walk to index - 1 otherwise. It works, but has more branches.
- Special-case index 0; otherwise walk to the predecessor.
class MyLinkedList {
private static class Node { int val; Node next; Node(int v, Node n) { val = v; next = n; } }
private Node head;
private int size;
public int get(int index) {
if (index < 0 || index >= size) return -1;
Node p = head;
for (int i = 0; i < index; i++) p = p.next;
return p.val;
}
public void addAtHead(int val) { addAtIndex(0, val); }
public void addAtTail(int val) { addAtIndex(size, val); }
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) return;
if (index == 0) head = new Node(val, head);
else {
Node p = head;
for (int i = 0; i < index - 1; i++) p = p.next;
p.next = new Node(val, p.next);
}
size++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
if (index == 0) head = head.next;
else {
Node p = head;
for (int i = 0; i < index - 1; i++) p = p.next;
p.next = p.next.next;
}
size--;
}
}class Node:
def __init__(self, v: int, n: Optional["Node"]):
self.val = v
self.next = n
class MyLinkedList:
def __init__(self):
self.head = None
self.size = 0
def get(self, index: int) -> int:
if index < 0 or index >= self.size:
return -1
p = self.head
for _ in range(index):
p = p.next
return p.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
if index == 0:
self.head = Node(val, self.head)
else:
p = self.head
for _ in range(index - 1):
p = p.next
p.next = Node(val, p.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
if index == 0:
self.head = self.head.next
else:
p = self.head
for _ in range(index - 1):
p = p.next
p.next = p.next.next
self.size -= 1class MyLinkedList {
struct Node { int val; Node* next; Node(int v, Node* n) : val(v), next(n) {} };
Node* head = nullptr;
int size = 0;
public:
int get(int index) {
if (index < 0 || index >= size) return -1;
Node* p = head;
for (int i = 0; i < index; i++) p = p->next;
return p->val;
}
void addAtHead(int val) { addAtIndex(0, val); }
void addAtTail(int val) { addAtIndex(size, val); }
void addAtIndex(int index, int val) {
if (index < 0 || index > size) return;
if (index == 0) head = new Node(val, head);
else {
Node* p = head;
for (int i = 0; i < index - 1; i++) p = p->next;
p->next = new Node(val, p->next);
}
size++;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
if (index == 0) {
Node* old = head;
head = head->next;
delete old;
} else {
Node* p = head;
for (int i = 0; i < index - 1; i++) p = p->next;
Node* old = p->next;
p->next = p->next->next;
delete old;
}
size--;
}
};class Node {
constructor(v, n) { this.val = v; this.next = n; }
}
class MyLinkedList {
constructor() {
this.head = null;
this.size = 0;
}
get(index) {
if (index < 0 || index >= this.size) return -1;
let p = this.head;
for (let i = 0; i < index; i++) p = p.next;
return p.val;
}
addAtHead(val) { this.addAtIndex(0, val); }
addAtTail(val) { this.addAtIndex(this.size, val); }
addAtIndex(index, val) {
if (index < 0 || index > this.size) return;
if (index === 0) this.head = new Node(val, this.head);
else {
let p = this.head;
for (let i = 0; i < index - 1; i++) p = p.next;
p.next = new Node(val, p.next);
}
this.size++;
}
deleteAtIndex(index) {
if (index < 0 || index >= this.size) return;
if (index === 0) this.head = this.head.next;
else {
let p = this.head;
for (let i = 0; i < index - 1; i++) p = p.next;
p.next = p.next.next;
}
this.size--;
}
}2Dummy head + size counter
O(index) per operationO(n)A permanent dummy node sits before index 0, so the predecessor of any index is reached by walking index steps from the dummy. One code path handles head, middle and tail.
- prev(index) = walk index steps from dummy.
- add: prev.next = new Node(val, prev.next). delete: prev.next = prev.next.next.
class MyLinkedList {
private static class Node { int val; Node next; Node(int v, Node n) { val = v; next = n; } }
private final Node dummy = new Node(0, null);
private int size;
private Node prev(int index) {
Node p = dummy;
for (int i = 0; i < index; i++) p = p.next;
return p;
}
public int get(int index) {
return index < 0 || index >= size ? -1 : prev(index).next.val;
}
public void addAtHead(int val) { addAtIndex(0, val); }
public void addAtTail(int val) { addAtIndex(size, val); }
public void addAtIndex(int index, int val) {
if (index < 0 || index > size) return;
Node p = prev(index);
p.next = new Node(val, p.next);
size++;
}
public void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
Node p = prev(index);
p.next = p.next.next;
size--;
}
}class Node:
def __init__(self, v: int, n: Optional["Node"]):
self.val = v
self.next = n
class MyLinkedList:
def __init__(self):
self.dummy = Node(0, None)
self.size = 0
def prev(self, index: int) -> Node:
p = self.dummy
for _ in range(index):
p = p.next
return p
def get(self, index: int) -> int:
return -1 if index < 0 or index >= self.size else self.prev(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 < 0 or index > self.size:
return
p = self.prev(index)
p.next = Node(val, p.next)
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index < 0 or index >= self.size:
return
p = self.prev(index)
p.next = p.next.next
self.size -= 1class MyLinkedList {
struct Node { int val; Node* next; Node(int v, Node* n) : val(v), next(n) {} };
Node* dummy = new Node(0, nullptr);
int size = 0;
Node* prev(int index) {
Node* p = dummy;
for (int i = 0; i < index; i++) p = p->next;
return p;
}
public:
int get(int index) {
return index < 0 || index >= size ? -1 : prev(index)->next->val;
}
void addAtHead(int val) { addAtIndex(0, val); }
void addAtTail(int val) { addAtIndex(size, val); }
void addAtIndex(int index, int val) {
if (index < 0 || index > size) return;
Node* p = prev(index);
p->next = new Node(val, p->next);
size++;
}
void deleteAtIndex(int index) {
if (index < 0 || index >= size) return;
Node* p = prev(index);
Node* old = p->next;
p->next = p->next->next;
delete old;
size--;
}
};class Node {
constructor(v, n) { this.val = v; this.next = n; }
}
class MyLinkedList {
constructor() {
this.dummy = new Node(0, null);
this.size = 0;
}
prev(index) {
let p = this.dummy;
for (let i = 0; i < index; i++) p = p.next;
return p;
}
get(index) {
return index < 0 || index >= this.size ? -1 : this.prev(index).next.val;
}
addAtHead(val) { this.addAtIndex(0, val); }
addAtTail(val) { this.addAtIndex(this.size, val); }
addAtIndex(index, val) {
if (index < 0 || index > this.size) return;
const p = this.prev(index);
p.next = new Node(val, p.next);
this.size++;
}
deleteAtIndex(index) {
if (index < 0 || index >= this.size) return;
const p = this.prev(index);
p.next = p.next.next;
this.size--;
}
}Edge cases to test
- addAtIndex(size, val) appends to the tail
- Deleting the head or the tail
- Index out of range
Hints
Hint 1
A dummy head removes every head special case, and a size counter makes index checks O(1).
FAQ
What is the best time complexity for Design Linked List?
Dummy head + size counter runs in O(index) per operation time and O(n) extra space.
Which pattern does Design Linked List use?
It is a design data structures problem that uses the linked lists pattern. Other problems with the same pattern: Design Front Middle Back Queue, LRU Cache, All O`one Data Structure.
Is there a brute force solution for Design Linked List?
Yes. Singly linked list without a dummy takes O(index) per operation time and O(n) space. Handle index 0 separately for add and delete, and walk to index - 1 otherwise.
Which edge cases should I test for Design Linked List?
addAtIndex(size, val) appends to the tail; Deleting the head or the tail; Index out of range.