Videos / DSA

Episode 14 of 22 · DSA, end to end

Linked lists: pointers as a data structure

Chapters

1. Carriages, coupled0:00
2. The struct, in full0:16
3. The address you cannot compute0:32
4. Shifting, versus rewiring0:51
5. The fine print on O(1)1:08
6. Sixteen bytes and a cache miss1:23
7. One way street1:40
8. The previous pointer1:54
9. No end to fall off2:12
10. Five branches for one idea2:28
11. The sentinel node2:46
12. The shape everyone ships3:04
13. Arrows, turned around3:21
14. Previous, current, next3:37
15. Save before you flip3:52
16. Three nodes, step by step4:08
17. The recursive version4:24
18. Loop or stack frames4:40
19. Two runners, one track4:58
20. Finding the middle5:14
21. Nth from the end5:31
22. The gap that shrinks5:47
23. Where the loop begins6:04
24. Two pointers, no allocation6:21
25. Two sorted piles6:38
26. The dummy head returns6:55
27. Why quicksort will not fit7:10
28. Split, recurse, merge7:26
29. No scratch buffer needed7:43
30. The honest benchmark8:00
31. Pulled out of the middle8:18
32. A map and a list8:32
33. The weakness became the design8:49
34. Graphs as arrays of chains9:06
35. The list inside the holes9:24
36. When to actually reach for one9:41
37. The whole thing9:58

Linked lists: pointers as a data structure. Picture a train. Each carriage carries cargo, and each carriage is coupled to exactly one carriage behind it. That is a linked list. A node holds a value and the address of the nex

Mark as watchedSaved in this browser only.