A linked list chains nodes with value and next pointers. Insert/delete at known position is O(1) after finding the node; search is O(n). Unlike vectors, nodes are not contiguous.
Singly linked list
- Head pointer to first node
- Traversal follows next until nullptr
- No random access—must walk from head
vs vector
| Operation | vector | linked list |
|---|---|---|
| Index i | O(1) | O(n) |
| Insert at head | O(n) shift | O(1) |
| Cache locality | Good | Poor |
Simple node struct
#include
struct Node {
int val;
Node* next;
};
int main() {
Node a{1, nullptr}, b{2, nullptr}, c{3, nullptr};
a.next = &b; b.next = &c;
for (Node* cur = &a; cur; cur = cur->next)
std::cout << cur->val << " ";
std::cout << "\n";
return 0;
} Important interview questions and answers
- Q: When use linked list?
A: Frequent head inserts or merging sorted lists; otherwise vector often wins on modern CPUs. - Q: Cycle detection?
A: Floyd slow/fast pointers—interview classic on linked lists.
Self-check
- What fields does a singly linked node need?
- Why is index access O(n)?
Pitfall: Forgetting nullptr checks when traversing—draw pointers on paper first.
Interview prep
- Insert at head?
O(1) after you have the node pointer.
- Index access?
O(n) traversal—no random access.