Design Linked List
Medium · Linked List · Explanation and code example
Doubly Linked List (Optimal)
How it works
This optimization improves traversal time by choosing the shorter path. For indices in the first half of the list, we traverse forward from the head. For indices in the second half, we traverse backward from the tail. The getPrev(index) helper returns the predecessor node using this bidirectional approach, cutting worst-case traversal roughly in half on average.
Steps
- Initialization: Create dummy head and tail nodes linked to each other. Set size to 0.
- getPrev(index): If
index <= size / 2, traverse forward from head forindexsteps. Otherwise, traverse backward from tail forsize - index + 1steps. Return the predecessor node. - get(index): If out of bounds, return -1. Call
getPrev(index)and return the value of its next node. - addAtHead(val): Call
addAtIndex(0, val). - addAtTail(val): Call
addAtIndex(size, val). - addAtIndex(index, val): If index is greater than size, return. Use
getPrev(index)to find the predecessor, create the new node, and wire it between the predecessor and its current next. Increment size. - deleteAtIndex(index): If out of bounds, return. Use
getPrev(index)to find the predecessor, then bypass the target node by linking predecessor directly to the node after the target. Decrement size.
Complexity
- Time complexity:
O(1)time for initialization.O(1)time foraddAtHead(),addAtTail().O(n)time forget(),addAtIndex(),deleteAtIndex().
- Space complexity:
O(n)
Things to watch for
Using Wrong Bound Check for addAtIndex vs deleteAtIndex
The addAtIndex allows inserting at position size (appending), but deleteAtIndex does not allow deleting at position size. Using the same condition for both causes bugs.
Forgetting to Update Size
Every insertion must increment size and every deletion must decrement it. Forgetting this causes subsequent operations to use stale bounds, leading to crashes or incorrect behavior.
Incorrect Pointer Order When Inserting
When inserting a node, you must set the new node's next pointer before updating the previous node's next. Reversing this order loses the reference to the rest of the list.
Python code example
class ListNode:
def __init__(self, val=0, next=None, prev=None):
self.val = val
self.next = next
self.prev = prev
class MyLinkedList:
def __init__(self):
self.head = ListNode(0)
self.tail = ListNode(0)
self.head.next = self.tail
self.tail.prev = self.head
self.size = 0
def getPrev(self, index: int) -> ListNode:
if index <= self.size // 2:
cur = self.head
for _ in range(index):
cur = cur.next
else:
cur = self.tail
for _ in range(self.size - index + 1):
cur = cur.prev
return cur
def get(self, index: int) -> int:
if index >= self.size:
return -1
return self.getPrev(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 > self.size:
return
node = ListNode(val)
prev = self.getPrev(index)
next = prev.next
prev.next = node
node.prev = prev
node.next = next
next.prev = node
self.size += 1
def deleteAtIndex(self, index: int) -> None:
if index >= self.size:
return
prev = self.getPrev(index)
cur = prev.next
next = cur.next
prev.next = next
next.prev = prev
self.size -= 1
C++ code example
class MyLinkedList {
struct ListNode {
int val;
ListNode* next;
ListNode* prev;
ListNode(int val = 0, ListNode* next = nullptr, ListNode* prev = nullptr) {
this->val = val;
this->next = next;
this->prev = prev;
}
};
public:
ListNode* head;
ListNode* tail;
int size;
MyLinkedList() {
head = new ListNode(0);
tail = new ListNode(0);
head->next = tail;
tail->prev = head;
size = 0;
}
ListNode* getPrev(int index) {
if (index <= size / 2) {
ListNode* cur = head;
for (int i = 0; i < index; i++) {
cur = cur->next;
}
return cur;
} else {
ListNode* cur = tail;
for (int i = 0; i < size - index + 1; i++) {
cur = cur->prev;
}
return cur;
}
}
int get(int index) {
if (index >= size) return -1;
return getPrev(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 > size) return;
ListNode* node = new ListNode(val);
ListNode* prev = getPrev(index);
ListNode* next = prev->next;
prev->next = node;
node->prev = prev;
node->next = next;
next->prev = node;
size++;
}
void deleteAtIndex(int index) {
if (index >= size) return;
ListNode* prev = getPrev(index);
ListNode* cur = prev->next;
ListNode* next = cur->next;
prev->next = next;
next->prev = prev;
delete cur;
size--;
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.