Data structures · 5 lessons
Linked ListNodes joined by pointers
A linked list gives up contiguous memory in exchange for O(1) insertion and deletion at a known position. You will not reach for one often, but the pointer intuition, the fast/slow trick, and its role behind LRU caches and trees make it worth the detour.
Why learn Linked List
Where it shows upBack and forward in a browser
Each page remembering the one before and the one after is a doubly linked list. So are playlists and an editor's undo/redo.
→ Lesson: Doubly Linked ListLRU caches
Move what was just used to the front, drop what has gone stale off the back. Paired with a hash table that is O(1). OS page replacement and CDN caches both work this way.
→ Lesson: Fast & Slow PointersDetecting a cycle
Two runners on a track, one twice as fast — if there is a loop they must meet. The same trick finds the middle of a list, and needs no extra memory.
→ Lesson: Fast & Slow PointersLessons
5 lessons#AlgorithmComplexityDifficultyStatus
01Singly Linked List Singly linked listsNodes, pointers, head and sentinel nodesUsed for: Building pointer intuition; implementing queues and stacksInsert O(1), search O(n)Space O(n)available02Doubly Linked List Doubly linked listsWalk both ways, delete any known node in O(1)Used for: LRU caches, browsing history, undo/redoO(1) deleteSpace O(n)available03Reverse Linked List Reversing a listThe three-pointer iterative form and the recursive oneUsed for: Core pointer practice; very common in interviewsO(n)Space O(1)available04Fast & Slow Pointers Fast and slow pointersFind the middle, detect a cycle (Floyd), find where the cycle startsUsed for: Detecting circular references, splitting a list in halfO(n)Space O(1)available05Merge Lists Merging listsMerge two sorted lists; use a heap when there are K of themUsed for: The heart of merge sort; merging several sorted streamsO(n+m)Space O(1)available