Linked List
DSA · Beginner
Definition
A linked list is a linear data structure where each node stores a value and a pointer to the next node.
Linked lists teach pointer manipulation and power stacks, queues and LRU caches.
Diagram
Flowchart
Example: Reverse a linked list
def reverse(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev, head = head, nxt
return prevComplexity
Access O(n) · Insert/Delete at node O(1)
Key points
- Singly, doubly and circular variants
- No random access
- Fast/slow pointers detect cycles
Interview questions
How to detect a cycle?
Floyd's algorithm: move slow by 1 and fast by 2; they meet if a cycle exists.
How to find the middle node?
When fast reaches the end, slow is at the middle.
Why use a dummy node?
It removes special cases when the head itself changes.