🔗 Linked Lists in C++ — Singly, Doubly and Common Operations
Master linked lists in C++ — singly and doubly linked, insert, delete, reverse, detect cycle. Compare with arrays/vectors. Interview-ready examples + Q&A.
A linked list is a sequence of nodes where each node holds a value and a pointer to the next node. Unlike arrays, list elements aren't stored in contiguous memory.
📜 Node structure
struct Node {
int data;
Node* next;
Node(int d) : data(d), next(nullptr) {}
};🟢 Singly linked — one direction
Each node points to the next; the last points to nullptr.
🔁 Doubly linked — two directions
struct DNode {
int data;
DNode* next;
DNode* prev;
};⚖️ Array vs Linked List
| Operation | Array/Vector | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Insert at head | O(n) | O(1) |
| Insert at tail | O(1) amortized | O(1) if tail kept |
| Delete in middle | O(n) | O(1) if node ptr known |
| Cache friendliness | Excellent | Poor |
📚 In the STL
Use std::list (doubly linked) or std::forward_list (singly linked). In practice, std::vector is usually faster.
💻 Code Examples
Build and print a singly linked list
struct Node { int data; Node* next; Node(int d):data(d),next(nullptr){} };
Node* head = new Node(1);
head->next = new Node(2);
head->next->next = new Node(3);
for (Node* cur = head; cur; cur = cur->next)
std::cout << cur->data << ' ';Output:
1 2 3
Reverse a singly linked list — classic interview
Node* reverse(Node* head) {
Node* prev = nullptr;
Node* curr = head;
while (curr) {
Node* nextTmp = curr->next;
curr->next = prev;
prev = curr;
curr = nextTmp;
}
return prev; // new head
}Output:
Iterative reversal, O(n) time, O(1) extra space.
Detect cycle (Floyd's tortoise and hare)
bool hasCycle(Node* head) {
Node* slow = head;
Node* fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) return true;
}
return false;
}Output:
O(n) time, O(1) space — classic two-pointer trick.
⚠️ Common Mistakes
- Forgetting to delete nodes — memory leaks. Walk the list and `delete` each node.
- Losing the head pointer during a traversal — you can't get back.
- Off-by-one when inserting/deleting at head vs middle vs tail.
- Reaching for std::list when std::vector would be faster — cache locality wins almost always.
🎯 Interview Questions
Real questions asked at top product and service-based companies.
Q1.What is a linked list?Beginner
A linear data structure where each element (node) holds a value plus a pointer to the next node. Unlike arrays, the elements are NOT stored in contiguous memory.
Q2.What's the difference between an array and a linked list?Intermediate
Array: contiguous memory, O(1) index access, expensive insert/delete in the middle. Linked list: scattered memory, O(n) index access, O(1) insert/delete given the node pointer, poor cache locality.
Q3.How do you reverse a linked list?Intermediate
Iterate, reversing each node's `next` pointer. Keep three pointers: prev, curr, nextTmp. At the end, prev is the new head. O(n) time, O(1) extra space.
Q4.How do you detect a cycle in a linked list?Advanced
Floyd's algorithm — two pointers, slow moving by 1 and fast by 2. If they meet, there's a cycle. If fast reaches nullptr, there's no cycle. O(n) time, O(1) space.
Q5.When would you use std::list over std::vector?Advanced
Rarely. Maybe when you have very large objects and frequently insert/delete in the middle with stable references that can't invalidate. In most real code, std::vector wins on speed due to cache locality.
🧠 Quick Summary
- Linked list: sequence of nodes with pointer to next.
- Singly = one direction; doubly = both.
- Slow random access (O(n)) but fast inserts/deletes.
- Worse cache performance than arrays.
- Classic interview ops: traverse, reverse, detect cycle.
- STL: std::list (doubly), std::forward_list (singly).