Linked lists train pointer discipline and are a gateway to more complex structures (LRU caches, skip lists, adjacency lists).
- Pointer manipulation: reversing, swapping pairs, merging sorted lists, and detecting cycles.
- Variants: singly, doubly, and circular lists with their tradeoffs and use cases.
- Slow-fast pointer tricks: cycle detection, middle node discovery, palindrome checks.
- Memory considerations: dummy head strategies, in-place modifications, and tail handling.
- Navigation history: browser back/forward stacks, music playlists, undo-redo systems.
- Cache design: implementing LRU/LFU caches that require O(1) insert/delete from arbitrary positions.
- Memory allocators: free lists for custom allocators and OS memory management.
singly_linkedlist.go: foundational node definitions and helpers.singly_linkedlist_problems.go: interview staples like reversal, middle element, and cycle detection.singly_linkedlist_test.go: tests covering edge cases and pointer correctness.doubly_linked_list.go: bidirectional list implementation for cache-style problems.questions/: targeted exercises including Floyd's cycle detection and list manipulations.reverse_list.go: focused implementation for iterative/recursive reversal patterns.
- Re-create the core functions without looking, then diff against the existing code.
- Implement copy-with-random-pointer and compare to typical interview expectations.
- Integrate with
hashing/to build an LRU cache; write benchmarks to validate O(1) operations. - Adapt solutions to handle gigantic lists (simulate streaming) to highlight memory patterns.
- Explore skip lists and compare to balanced BST performance.
- Implement a lock-free linked list using Go's atomics for concurrency practice.
- Pair this knowledge with
tree/BST rotations to understand structural transformations.