Week 20 of 43
Core DSA
WEEK 20 LEARNING MODULE
Singly Linked Lists
Introduces pointer-based non-contiguous node data structures (`Node(val, next)`), head/tail insertion, node deletion, traversal, and the dummy node pattern.
4 Practice Problems3 Core ConceptsVerified Curriculum: high Confidence
What You'll Learn
- ✓Understand singly linked list node structure and pointer reference mechanics in memory.
- ✓Implement core operations: traversal, insertion at head/tail/position, and node deletion.
- ✓Master the Sentinel / Dummy Head Node pattern to handle edge cases cleanly.
- ✓Merge two sorted linked lists and reorder nodes (odd-even indices) using pointer manipulation.
Core Concepts
Linked List Node Structure
Non-contiguous dynamic structures consisting of a value and a reference pointer to the next node.
Dummy / Sentinel Node Pattern
O(1) spaceCreating an auxiliary dummy node before the head to avoid special null head handling during insertions and deletions.
Fast & Slow Pointers for Midpoint
O(n) time, O(1) spaceUsing slow (1 step) and fast (2 steps) pointers to locate list midpoint in a single pass.
Algorithms Covered
Linked List TraversalNode Deletion in $O(1)$ and $O(n)$Midpoint Finding (Fast & Slow Pointers)Merging Two Sorted ListsOdd-Even Node Segregation
Data Structures Applied
Singly Linked List
“If you fell down yesterday, stand up today.”
— H. G. Wells