EasyHigh Frequency20 min
Linked List Fundamentals
Singly, doubly, and circular linked lists — nodes, pointers, and traversal.
Linked lists give O(1) insert/delete at known node, O(n) access. Master traversal, dummy head, and the 3-pointer reversal.
What is a Linked List?
Node Structure
Linked List1 / 5
A linked list of 4 nodes
The head pointer points to the first node (10). Each node stores a value and a pointer to the next. The last node points to null.
Operation Complexities
Operation
Time
Note
Access by index
O(n)
Must traverse from head — no direct address formula
Search by value
O(n)
Linear scan from head until found or null
Insert at head
O(1)
Create node, point it to current head, update head
Insert at tail
O(n)
O(n) to reach tail; O(1) if tail pointer maintained
Insert at known node
O(1)
Rewire: newNode.next = prev.next; prev.next = newNode
Delete at head
O(1)
head = head.next
Delete by value
O(n)
O(n) to find the node, then O(1) to remove
Delete at known prev
O(1)
prev.next = prev.next.next
Operations — Step by Step
Traversal
O(n)Visit every node exactly onceStep-by-step1 / 5
curr = head (node 10)
Initialize curr to head. Process curr.val = 10.
More in Linked Lists
Fast & Slow Pointers (Floyd's)
Detect cycles, find midpoints, and solve linked list problems using two speed pointers.
Reverse Linked List
Iterative and recursive reversal patterns — the most fundamental linked list operation.
Merge Lists & K-way Merge
Merge sorted lists using dummy node technique and a min-heap for K lists.