Singly Linked Lists: Node Architecture, Traversal & In-Place Reversal0%
Singly Linked Lists: Node Architecture, Traversal & In-Place Reversal
Beginner12 min read•Updated: Jul 11, 2026
Singly Linked Lists: Node Architecture, Traversal & In-Place Reversal
A Singly Linked List is a fundamental linear data structure where elements (called Nodes) are not stored in contiguous memory cells. Instead, each node contains a data payload and a reference pointer (next) to the subsequent node in memory.
1. Real-World Analogy: The Scavenger Hunt
Think of a treasure hunt where each clue contains:
- 1A small prize or message (Data).
- 2A handwritten note with GPS coordinates to the next clue (Next Pointer).
- You cannot teleport directly to Clue #5; you must find Clue #1, follow its pointer to Clue #2, then #3, and so on.
- The final clue has no coordinates (NULL Pointer), indicating the hunt is over.
2. Linked List Memory Architecture
Click to ZoomComparison: Array vs Linked List
| Feature | Array | Singly Linked List |
|---|---|---|
| Memory Allocation | Contiguous chunk of RAM | Scattered nodes anywhere in Heap memory |
Index Access (get(i)) | $O(1)$ (Direct pointer math) | $O(n)$ (Must traverse from Head) |
| Insert/Delete at Beginning | $O(n)$ (Shifting elements) | $O(1)$ (Update Head pointer) |
| Memory Overhead | Low (Only data stored) | High (Each node stores data + 8-byte pointer) |
| Resizing Cost | $O(n)$ reallocation & copy | $O(1)$ dynamic heap allocation per node |
3. The Core Algorithm: In-Place Linked List Reversal ($O(n)$ Time, $O(1)$ Space)
Reversing a linked list is the quintessential technical interview question. You must redirect every node's next pointer to face backwards without allocating new nodes:
Output
Initial: [1] -> [2] -> [3] -> NULL
Pointers: prev = NULL, curr = [1]
Step 1: Save next_node = [2]
Redirect curr.next = prev (points to NULL)
Advance prev = curr ([1])
Advance curr = next_node ([2])
Final Result: NULL <- [1] <- [2] <- [3] (prev is new Head!)
4. Multi-Language Implementations: Node & Reversal
Python 3:
Python
class ListNode:
def __init__(self, val: int = 0, next: 'ListNode' = None):
self.val = val
self.next = next
def reverse_linked_list(head: ListNode) -> ListNode:
prev = None
curr = head
while curr is not None:
next_temp = curr.next # 1. Save reference to next node
curr.next = prev # 2. Reverse current node's pointer
prev = curr # 3. Advance prev pointer
curr = next_temp # 4. Advance curr pointer
return prev # prev is the new head of the reversed list!
Modern JavaScript / TypeScript:
TypeScript
export class ListNode {
val: number;
next: ListNode | null;
constructor(val: number = 0, next: ListNode | null = null) {
this.val = val;
this.next = next;
}
}
export function reverseLinkedList(head: ListNode | null): ListNode | null {
let prev: ListNode | null = null;
let curr: ListNode | null = head;
while (curr !== null) {
const nextTemp: ListNode | null = curr.next; // 1. Save next
curr.next = prev; // 2. Reverse pointer
prev = curr; // 3. Move prev
curr = nextTemp; // 4. Move curr
}
return prev;
}
5. Trace Table: Reversing List 1 -> 2 -> 3 -> NULL
| Iteration | curr.val | nextTemp.val | New curr.next | prev becomes | curr becomes |
|---|---|---|---|---|---|
| Init | 1 | - | - | NULL | 1 |
| 1 | 1 | 2 | NULL | 1 | 2 |
| 2 | 2 | 3 | 1 | 2 | 3 |
| 3 | 3 | NULL | 2 | 3 | NULL (Loop ends) |
Result: prev points to Node 3 -> 2 -> 1 -> NULL. Reversed in $O(n)$ time with $O(1)$ space!
Interactive Quiz
Multiple Choice Questions
Question 1
What does each node in a standard Singly Linked List contain?
Question 2
Why is random index access in a linked list (
get(i)) $O(n)$ while in an array it is $O(1)$?Question 3
What is the time complexity of inserting a new node at the very beginning (Head) of a Singly Linked List?
Question 4
What happens if you update
curr.next = prev during an in-place list reversal before saving curr.next in a temporary variable?Question 5
What value does the
next pointer of the tail node store in a standard non-circular linked list?Next Lesson
Doubly & Circular Linked Lists with Sentinel/Dummy Nodes
Continue learning with hands-on practice, examples, and exercises in the upcoming topic.
Related Lessons
Practice Quiz
Test your understanding of this lesson with 5 questions. Each question has one correct answer.