Why You Should AVOID Linked Lists
📚 Main topics
- The comparisonThe video examines when linked lists outperform vectors or arrays for inserting and removing elements, using a sequence of randomly positioned operations as the example. 0:00
- Finding an element costs timeAlthough changing links to remove a node is constant-time once you reach it, locating the node in a linked list requires traversal; that search can dominate the operation. 1:33
- Memory layout mattersVectors store elements contiguously, while linked-list nodes are scattered in memory and require extra pointers. 5:16
- Objects can add another layer of indirectionStoring references to objects in a container means following additional pointers to reach the actual data, making the layout less compact. 9:57
✨ Key takeaways
- Vectors are often faster in practiceShifting elements in a vector may sound expensive, but contiguous storage and cache-friendly access can make it faster than traversing a linked list. 4:13
- Linked lists hurt cache performanceTraversing scattered nodes involves unpredictable memory accesses and cache misses, while vectors support more predictable, compact access. 6:49
- Compactness can bring major gainsThe video argues that choosing compact, predictable data layouts can yield substantial performance improvements. 7:19
🧠 Lessons learned
- Consider the full operationConstant-time insertion or removal applies only after reaching the relevant linked-list node; the cost of finding it must also be counted. 4:44
- Prefer simple contiguous containers by defaultThe speaker recalls the advice to use a vector unless there is evidence that another structure is faster. 7:49
- Data representation affects performanceThe demonstration contrasts storing object references with storing values compactly in a typed array, illustrating how layout changes memory access. 11:58
🏁 Conclusion/next steps
- Choose based on measured needsLinked lists may be useful for special cases such as operations at the head, but for many workloads vectors benefit from compact storage and cache behavior. 6:18
- Think about memory access, not just algorithmic complexityWhen selecting a data structure, account for traversal, indirection, allocation, and cache performance—not only the cost of the final insertion or deletion. 7:19
Transcript excerpt
0:00 why should you avoid linked lists let's go okay here I'd like to to show an example that first was shown to Me by John Bentley of algorithms Fame make a sequence of random integers keeping them in order and so you you you're given the numbers 5142 and it builds up the sequence as you see it there and then you remove them again by giving a set of positions
0:31 of which one you you take out and so the exercise is for which end is it better to use a linked list than a vector okay or an array okay and so for those that don't understand who here doesn't understand the question that was just proposed right here type one in the chat if you don't understand the question that was proposed by the way if you don't love 14p you know type one in the chat okay so it's actually a pretty it's a pretty simple question right uh here let me see if we can exit out of here uh let's go to the Excalidraw this that
1:01 it's a very it's a very interesting question so you could imagine that there exists a world in which there is some large space like this in which you have a bunch of elements right one two three uh four or five all the way up to whatever right all the way up to I don't know 69 420. and then you have in another world something that looks like this where hold on let me get this thing and drop it all the way down to this and you have one and one well guess what one
🔒 The full, searchable transcript is available with Pro.
Related summaries
This Might Be the Best AI Release of 2026
Learning is Cool
I was right again
The Token Black Market
This is the only AI I want to use
