Log inSign up
mediumLeetCodeNot Started

Design Linked List

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

Design your implementation of the linked list. You can choose to use a singly or doubly linked list.

A node in a singly linked list should have two attributes: val and next. val is the value of the current node, and next is a pointer/reference to the next node.

If you want to use the doubly linked list, you will need one more attribute prev to indicate the previous node in the linked list. Assume all nodes in the linked list are 0-indexed.

Implement the MyLinkedList class: - MyLinkedList(): Initializes the MyLinkedList object. - int get(int index): Get the value of the indexth node in the linked list. If the index is invalid, return -1. - void addAtHead(int val): Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. - void addAtTail(int val): Append a node of value val as the last element of the linked list. - void addAtIndex(int index, int val): Add a node of value val before the indexth node in the linked list. If index equals the length of the linked list, the node will be appended to the end of the linked list. If index is greater than the length, the node will not be inserted. - void deleteAtIndex(int index): Delete the indexth node in the linked list, if the index is valid.

Example 1 · Standard Usage Example:

Input: ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]]
Output: [null, null, null, null, 2, null, 3]
Explanation: MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3 myLinkedList.get(1); // return 2 myLinkedList.deleteAtIndex(1); // now the linked list is 1->3 myLinkedList.get(1); // return 3

Constraints:

  • 0 <= index, val <= 1000
  • Please do not use the built-in LinkedList library.
  • At most 2000 calls will be made to get, addAtHead, addAtTail, addAtIndex, and deleteAtIndex.

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the Dual Sentinel Node pattern (dummyHead & dummyTail).
  • Implement 4-pointer insertion and deletion in Doubly Linked Lists.
  • Optimize sequential index lookups by selecting traversal direction based on size / 2.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Custom data structure design requiring O(1) head and tail operations.
  • Arbitrary index-based insertion and deletion without shifting elements.
  • Need robust handling of empty lists and single-element bounds.

Algorithmic Decision Tree:

  • Whenever designing custom linked structures: Always anchor with head and tail sentinel nodes.
  • Always track size to validate indices in O(1) before initiating node traversals.

Connected Patterns:

LRU Cache (Doubly Linked List + Hash Map)LFU CacheDesign Circular DequeFlatten a Multilevel Doubly Linked List

1. Brute Force — Dynamic Array Simulation

Intuition

Use a dynamic array/vector to fulfill the operations. While get is O(1), head and middle modifications incur heavy O(N) memory shifting penalties.

Algorithm

  1. Step 1: Maintain a dynamic list data.
  2. Step 2: get(index): If index in range return data[index], else -1.
  3. Step 3: addAtHead(val): Insert at index 0 (shifts all elements right).
  4. Step 4: addAtTail(val): Append to end.
  5. Step 5: addAtIndex(index, val): Insert at position index if valid.
  6. Step 6: deleteAtIndex(index): Remove at position index if valid.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4using namespace std;
5
6class MyLinkedList {
7 vector<int> data;
8public:
9 MyLinkedList() {}
10
11 int get(int index) {
12 if (index < 0 || index >= (int)data.size()) return -1;
13 return data[index];
14 }
15
16 void addAtHead(int val) {
17 data.insert(data.begin(), val);
18 }
19
20 void addAtTail(int val) {
21 data.push_back(val);
22 }
23
24 void addAtIndex(int index, int val) {
25 if (index < 0 || index > (int)data.size()) return;
26 data.insert(data.begin() + index, val);
27 }
28
29 void deleteAtIndex(int index) {
30 if (index < 0 || index >= (int)data.size()) return;
31 data.erase(data.begin() + index);
32 }
33};
34
35int main() {
36 MyLinkedList list;
37 list.addAtHead(1);
38 list.addAtTail(3);
39 list.addAtIndex(1, 2);
40 cout << "Array Sim get(1): " << list.get(1) << endl;
41 list.deleteAtIndex(1);
42 cout << "Array Sim get(1): " << list.get(1) << endl;
43 return 0;
44}

Time & Space Complexity

  • Time complexity: get: O(1), addAtHead/delete: O(N), addAtTail: O(1) — Array lookup by index is instantaneous O(1), but inserting or deleting at index 0 requires shifting all N elements in O(N) time.
  • Space complexity: O(N) — Stores elements in contiguous dynamic array buffer of size N.

Why Brute Force Doesn't Scale:

Array-based lists suffer O(N) cost when inserting at index 0 due to memory copying.

For 100,000 head insertions, Doubly Linked List completes in 4ms, while ArrayList takes ~12,000ms due to repeated array shifting.

2. Better — Singly Linked List with Sentinel Head

Intuition

Maintain a singly linked chain with a dummy head. Every operation iterates starting from dummy.next.

Algorithm

  1. Step 1: Create a single dummy head node head = new Node(0) and size = 0.
  2. Step 2: For get(index), validate index < size and traverse index + 1 steps.
  3. Step 3: For addAtHead(val), insert directly after dummy head.
  4. Step 4: For addAtTail(val), traverse to the end of the list and append.
  5. Step 5: For deleteAtIndex(index), traverse to the indexth node and skip the next node.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3using namespace std;
4
5class MyLinkedList {
6 struct Node {
7 int val;
8 Node* next;
9 Node(int v) : val(v), next(nullptr) {}
10 };
11 Node* dummy;
12 int size;
13public:
14 MyLinkedList() {
15 dummy = new Node(0);
16 size = 0;
17 }
18
19 int get(int index) {
20 if (index < 0 || index >= size) return -1;
21 Node* curr = dummy->next;
22 for (int i = 0; i < index; i++) curr = curr->next;
23 return curr->val;
24 }
25
26 void addAtHead(int val) {
27 addAtIndex(0, val);
28 }
29
30 void addAtTail(int val) {
31 addAtIndex(size, val);
32 }
33
34 void addAtIndex(int index, int val) {
35 if (index < 0 || index > size) return;
36 Node* prev = dummy;
37 for (int i = 0; i < index; i++) prev = prev->next;
38 Node* node = new Node(val);
39 node->next = prev->next;
40 prev->next = node;
41 size++;
42 }
43
44 void deleteAtIndex(int index) {
45 if (index < 0 || index >= size) return;
46 Node* prev = dummy;
47 for (int i = 0; i < index; i++) prev = prev->next;
48 Node* toDelete = prev->next;
49 prev->next = toDelete->next;
50 delete toDelete;
51 size--;
52 }
53};
54
55int main() {
56 MyLinkedList list;
57 list.addAtHead(1);
58 list.addAtTail(3);
59 list.addAtIndex(1, 2);
60 cout << "get(1): " << list.get(1) << endl; // 2
61 list.deleteAtIndex(1);
62 cout << "get(1): " << list.get(1) << endl; // 3
63 return 0;
64}

Time & Space Complexity

  • Time complexity: get: O(index), addAtHead: O(1), addAtTail: O(N), deleteAtIndex: O(index) — Traverses sequentially from the sentinel head node for get, addAtTail, and deleteAtIndex calls.
  • Space complexity: O(N) — Allocates one node per value stored.

3. Optimal — Doubly Linked List with Head & Tail Sentinels

Intuition

Connect dummy head and dummy tail nodes together. When accessing index k, if k < size / 2 traverse forward from head; otherwise traverse backward from tail. Insertions and deletions simply adjust 4 pointers.

Algorithm

  1. Step 1: Initialize head = new Node(0), tail = new Node(0), head.next = tail, tail.prev = head, and size = 0.
  2. Step 2: For index k, locate predecessor node: if k <= size / 2, start at head and step forward k times; else start at tail and step backward size - k + 1 times.
  3. Step 3: To insert node after prev: set node.prev = prev, node.next = prev.next, prev.next.prev = node, prev.next = node, and increment size.
  4. Step 4: To delete after prev: set toDelete = prev.next, prev.next = toDelete.next, toDelete.next.prev = prev, and decrement size.

Design Linked List Master Trace

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Sentinels connected
Visual state
Values and pointers at this exact step
linked list
size → 0
Node h
HEAD(0)
Node t
TAIL(0)
NULL
Check / comparison
head.next == tail
Decision / next transition
Empty list initialized
Why this step matters

Sentinels connected.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <algorithm>
3
4using namespace std;
5
6class MyLinkedList {
7 struct Node {
8 int val;
9 Node* prev;
10 Node* next;
11 Node(int v) : val(v), prev(nullptr), next(nullptr) {}
12 };
13
14 Node* head;
15 Node* tail;
16 int size;
17
18public:
19 MyLinkedList() {
20 head = new Node(0);
21 tail = new Node(0);
22 head->next = tail;
23 tail->prev = head;
24 size = 0;
25 }
26
27 int get(int index) {
28 if (index < 0 || index >= size) return -1;
29 Node* curr;
30 if (index < size / 2) {
31 curr = head->next;
32 for (int i = 0; i < index; i++) curr = curr->next;
33 } else {
34 curr = tail->prev;
35 for (int i = 0; i < size - 1 - index; i++) curr = curr->prev;
36 }
37 return curr->val;
38 }
39
40 void addAtHead(int val) {
41 addAtIndex(0, val);
42 }
43
44 void addAtTail(int val) {
45 addAtIndex(size, val);
46 }
47
48 void addAtIndex(int index, int val) {
49 if (index < 0 || index > size) return;
50
51 Node* pred;
52 Node* succ;
53 if (index < size / 2) {
54 pred = head;
55 for (int i = 0; i < index; i++) pred = pred->next;
56 succ = pred->next;
57 } else {
58 succ = tail;
59 for (int i = 0; i < size - index; i++) succ = succ->prev;
60 pred = succ->prev;
61 }
62
63 Node* toAdd = new Node(val);
64 toAdd->prev = pred;
65 toAdd->next = succ;
66 pred->next = toAdd;
67 succ->prev = toAdd;
68 size++;
69 }
70
71 void deleteAtIndex(int index) {
72 if (index < 0 || index >= size) return;
73
74 Node* pred;
75 Node* succ;
76 if (index < size / 2) {
77 pred = head;
78 for (int i = 0; i < index; i++) pred = pred->next;
79 Node* toDelete = pred->next;
80 succ = toDelete->next;
81 pred->next = succ;
82 succ->prev = pred;
83 delete toDelete;
84 } else {
85 succ = tail;
86 for (int i = 0; i < size - 1 - index; i++) succ = succ->prev;
87 Node* toDelete = succ->prev;
88 pred = toDelete->prev;
89 pred->next = succ;
90 succ->prev = pred;
91 delete toDelete;
92 }
93 size--;
94 }
95};
96
97int main() {
98 MyLinkedList myLinkedList;
99 myLinkedList.addAtHead(1);
100 myLinkedList.addAtTail(3);
101 myLinkedList.addAtIndex(1, 2); // linked list becomes 1->2->3
102 cout << "Optimal get(1): " << myLinkedList.get(1) << endl; // 2
103 myLinkedList.deleteAtIndex(1); // now the linked list is 1->3
104 cout << "Optimal get(1): " << myLinkedList.get(1) << endl; // 3
105 return 0;
106}

Time & Space Complexity

  • Time complexity: get: O(min(k, N-k)), addAtHead/Tail: O(1), addAtIndex/deleteAtIndex: O(min(k, N-k)) — Head and Tail insertions take O(1). Middle lookups take O(min(k, N-k)) by traversing from the closest sentinel.
  • Space complexity: O(N) — Stores N Doubly Linked Nodes with prev and next pointers.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Brute Force — Dynamic Array Simulationget: O(1), addAtHead/delete: O(N), addAtTail: O(1)O(N)Simulate operations using an underlying dynamic array (vector/ArrayList).Memory shifting on head insertions and deletions.
2.Better — Singly Linked List with Sentinel Headget: O(index), addAtHead: O(1), addAtTail: O(N), deleteAtIndex: O(index)O(N)Implement using singly linked nodes with a dummy head sentinel and size counter.Unidirectional traversal from head only.
3.Optimal — Doubly Linked List with Sentinel Head & TailOptimalget: O(min(k, N-k)), addAtHead/Tail: O(1), add/deleteAtIndex: O(min(k, N-k))O(N)Use a doubly linked list with both dummy head and dummy tail. Traverse from whichever end is closer to the target index.Optimal for linked list data structure design.

Common Pitfalls & Crucial Edge Cases

Off-by-One in `addAtIndex` vs `deleteAtIndex` Bounds

addAtIndex allows index == size, whereas deleteAtIndex requires index < size.

Broken Prev / Next Wiring Order

Assigning prev.next = toAdd before toAdd.next = prev.next in singly linked lists loses reference to the remainder of the list.

Forgetting to Update `size` Counter

Causes all subsequent index validations to fail.

Crucial Edge Cases to Validate:

  • Invalid Index (`index < 0` or `index >= size`) — Returns -1 for get, does nothing for deleteAtIndex.
  • `addAtIndex(size, val)` — Successfully appends to tail.
  • `addAtIndex(size + 1, val)` — Index is strictly greater than size, operation ignored.
  • Deleting Only Element — deleteAtIndex(0) when size = 1 properly restores head.next = tail and tail.prev = head.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Clarify upfront whether the interviewer wants a Singly or Doubly Linked List.
  2. Recommend the Doubly Linked List with dummy head and tail: 'This provides O(1) head/tail insertions and eliminates all null edge cases.'
  3. Mention the size / 2 traversal direction optimization: 'I will check if the index is in the first or second half to traverse from the closest sentinel.'

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the primary advantage of using two dummy sentinels (head and tail) in a Doubly Linked List?

2.How do we optimize get(index) in a Doubly Linked List?

3.What is the time complexity of addAtHead and addAtTail with sentinels?

Back to DSA Sheet