Notes › DSA
Linked List
A linked list stores elements in nodes. Each node holds a value and a pointer to the next node. Unlike an array, the nodes are not next to each other in memory, so you cannot jump to the i-th element — you have to walk there.
head → [10 | •] → [20 | •] → [30 | •] → null
Types
| Type | Each node points to | Use |
|---|---|---|
| Singly | next | Simple lists, stacks |
| Doubly | next and prev | Browser history, LRU cache, deque |
| Circular | last node → head | Round-robin scheduling, music playlists |
Node and basic operations (C++)
struct Node {
int val;
Node* next;
Node(int v) : val(v), next(nullptr) {}
};
// insert at the front — O(1)
Node* pushFront(Node* head, int v) {
Node* n = new Node(v);
n->next = head;
return n; // new head
}
// insert after position k (0-based) — O(k)
void insertAfter(Node* head, int k, int v) {
Node* cur = head;
for (int i = 0; i < k && cur; i++) cur = cur->next;
if (!cur) return;
Node* n = new Node(v);
n->next = cur->next; // 1. new node points to the rest
cur->next = n; // 2. then link it in (order matters!)
}
// delete the first node with value v — O(n)
Node* removeValue(Node* head, int v) {
Node dummy(0);
dummy.next = head;
Node* prev = &dummy;
while (prev->next && prev->next->val != v) prev = prev->next;
if (prev->next) {
Node* del = prev->next;
prev->next = del->next;
delete del;
}
return dummy.next;
}
Dummy (sentinel) node trick: put a fake node before the head. Then deleting or inserting at the head needs no special case.
Complexity
| Operation | Array | Linked list |
|---|---|---|
| Access i-th element | O(1) | O(n) |
| Insert / delete at front | O(n) | O(1) |
| Insert / delete in the middle (pointer known) | O(n) | O(1) |
| Search | O(n) | O(n) |
| Extra memory | none | one pointer per node |
| Cache friendly | yes | no |
Must-know patterns
1. Reverse a list (iterative)
Three pointers: prev, curr, next. Save next before you change curr->next.
Node* reverse(Node* head) {
Node *prev = nullptr, *curr = head;
while (curr) {
Node* nxt = curr->next;
curr->next = prev;
prev = curr;
curr = nxt;
}
return prev; // new head
}
Watch it step by step in the linked list visualizer.
2. Fast and slow pointers
slow moves 1 step, fast moves 2 steps.
- Middle of the list: when
fastreaches the end,slowis in the middle. - Cycle detection (Floyd): if there is a cycle,
fasteventually meetsslow. - Start of the cycle: after they meet, move one pointer back to
head; move both 1 step at a time — they meet at the cycle start.
bool hasCycle(Node* head) {
Node *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}
3. Merge two sorted lists
Use a dummy node and attach the smaller head each time — O(n + m).
4. k-th node from the end
Move a first pointer k steps ahead, then move both until the first reaches the end.
5. Remove duplicates from a sorted list
If cur->val == cur->next->val, skip the next node; else move on.
Classic problems
| Problem | Idea |
|---|---|
| Reverse linked list | 3 pointers |
| Middle of linked list | fast/slow |
| Linked list cycle I & II | Floyd's algorithm |
| Merge two sorted lists | dummy node |
| Remove N-th node from end | gap of N between two pointers |
| Palindrome linked list | find middle, reverse second half, compare |
| Intersection of two lists | switch heads when a pointer reaches the end |
| Add two numbers | digit by digit with a carry |
| LRU cache | hash map + doubly linked list |
Practise them in the Linked List section of the DSA sheet.
Interview one-liners
- Why use a linked list? O(1) insert/delete when you already have the node, and it grows without resizing.
- Why not? No random access, extra memory per node, poor cache performance.
- Doubly vs singly: doubly can delete a node in O(1) given only that node, at the cost of one more pointer.
- Java/C++ library:
LinkedList(Java) andstd::list(C++) are doubly linked lists. - Always check
nullptrbefore using->next, and draw the pointers on paper before coding.