Why You Should AVOID Linked Lists 

People don't seem to understand that O(1) is not FASTER than O(n), it just SCALES better; there's a breakpoint. Imagine a "hashcode as a service" rest call vs doing it in memory: it'd still scale better, but it'd take an awfully large 'n' to get there. I see people missing this in PRs, streaming/looping an array is often faster with small arrays than something like a `HashSet`. And in practice, its really unlikely either makes a tangible difference in most use cases.

Haskell programmers: Linked lists all the way and back.

There are some cases where linked lists are highly efficient. One real-world example is dynamically allocating sound channels. When you need a new channel, grab the head of the free list. When freeing a channel, link it onto the head of the free list. Both constant-time operations. And you have to traverse the active list every update, so you have your prev/next pointers to unlink if a channel has ended. And because it's all management of elements within a single array, you don't need pointers, or even to store the prev link. Just a single next index. Another is overhead RPG sprites. They need to be rendered in order of Y position, and you can do an insertion sort every frame to relink them in proper order. Normally an insertion sort is O(n2) because you have to traverse the list to find the insertion point, but because the list is still mostly sorted from last frame, you end up linking most entries to the head of the new list so it's O(n).

Store data in a dynamic array, add a unique ID to each entry and shuffle it every time you add an entry. Every time you need to access an entry, search for the index by randomizing the current index and check if the ID matches the ID of the entry you are looking for.

This is an absolutely classic talk that every software developer must see. I remember writing a lot of linked list code back in the days of DOS and it worked wonderfully... but computers changed a lot since 1990.

_Back in my day_ cache friendly code wasn't a thing; now these newfangled caches make the case for arrays stronger than ever. Having that said, solving the problem correctly before measuring performance and making the case for struct of arrays is super important or else you're just gonna have a lot of arrays that aren't doing you any good.

I saw this a while ago and it blew my mind. It just shows that when you move theory to practice things may not work how you expect since there's a lot of complexity such as caching, predictable usage patterns, compactness, number of pointer redirections, etc. that significantly impacts performance. It's very difficult to correctly optimize a piece of code without first measuring and understanding where the bottle necks unless you already have experience in tuning.

The linked lists gain a lot for some special purposes when the elements themselves have prev and next pointers and you never have to search. But even then not always - contiguous memory really makes a difference.

If you're doing only head or only tail removal/addition I'd go to a vector or a vector in reversed order. If you're doing both, I'd go to an array deque which is essentially just a vector treated as if wrapped in a circle. I try to avoid linked lists whenever possible.

C++ not censured, it thought it was family friendly channel

Just gonna say my thoughts as I watch: -Okay the thing about the linear search dominating makes sense at first blush but that's just bad usage of a linked list. Generally you will couple it with a hashtable from some key to the node. Any simple LRU cache would work like this. -The nodes don't have to be malloc'd randomly. You could malloc sizeof(Node)*1024 and then dole them out. -Linear search is especially bad for linked lists because with an array it can prefetch elements that it knows you are going to touch. Not so with a linked list because it's all through pointers so who knows what you're going to need next. Again, use a hashtable if you need lookups into your linked list. Linked lists are good at insertion and removal, not at random access. Nothing new there. -"Vectors are more compact than [linked] lists." No, see above about mallocing a pool of nodes. -"Always use a vector unless you can prove a map is faster." For a trivial case of searching for a given integer in a vector of integers, a map becomes faster after about 100 elements (from my testing a while ago. Also depends on the implementation of those data structures. I did my test in C# (List vs Dictionary so take that with a grain of salt). Linked lists are very powerful when you start using them how they are meant to be used. They are not merely "a worse vector." They afford different things.

This is a good take. I think it's good to educate people that if they need to search for a node to do something with it, then it will be expensive. I personally rarely use linked lists when I have to search for the node I want to do things to, but you don't always need to actually search for the node - when you don't need to search is when linked lists are (more likely to be) useful.

I love listening to Stroustrup talk. His pacing and tone are just fantastic when he's explaining _anything_ :)

Linked lists aren't good for containers, because of the linear search problem mentioned here. Linked lists are good when they're built into the data type itself. That way, if you have a reference to an object, you can just call something like appendAfter() efficiently, without searching for the insertion point

I like to use a combination of both. Make chunks of max 4K elements (or whatever size is suitable for your cache), store these chunks in a linked list. Insertion and deletion with a chunk is fast since you're shifting stuff already in the cache. Split a chunk if it gets near 4K elements into 2 chunks of 2K elements, or merge 2 chunks if they fall below 2K elements. Should be as fast as arrays, with the flexibility of linked lists.

one additional thing is the impact of linked list and structures with lots of pointers is heap fragmentation and compaction. At some point, your system may need to compact the memory to get better performance. A lot of programmers don't think about heap fragmentation and how much if affects performance.

It’s not even just cache misses and prefetching like he mentions, but it’s also a linear chain of data dependencies. When traversing a linked list, the out of order CPU can’t do anything for you because it doesn’t know where the next node is until it gets the result of the memory load of the next pointer for the current node. So the CPU is just stuck waiting around for stuff to do while memory loads. Basically, linked lists are the worst case data structure for allowing your CPU to do what it’s good at. Hybrid data structures (lists with fat nodes that contain compact arrays) can give many benefits of both, though.

If the items aren’t sorted, you can just swap the to-be-deleted item with the last item in the vector and then pop that. Super fast. No linked list will beat that :)

I think there is a small implied assumption when stating that insertion/removal is faster in a list, namely that you already have a pointer to the desired location and linear search is not an issue. Just like with an array, you don't usually search the element to be removed, you just index into the array by keeping track of the "interesting" indices, with a smart use of a linked list you usually keep track of pointers to the "interesting" nodes. In this circumstance, the list is better.

This was great. I remember watching Bjarne's presentation a few years ago and was blown away by how simple the problem was after he explained it but yet so damning for Linked-Lists. My favourite language is C++ and I miss it dearly (been stuck doing Kotlin for several years now).

TLDR and for grug: Make linked list inside array. Advantage of both linked list and array, less disadvantage. The magic of data structures is that you can combine them. If you allocate your linked lists with an arena allocator(pool allocator, bump allocator), then the point Stroustrup makes doesn't make sense. Linked lists aren't defined as having to use malloc (even if the do most of the time). Arrays(vectors) vs Linked lists doesn't make sense in all algorithms, as some necessitate one or the other. If you do what I suggest (arena allocator) there is cache locality, no memory fragmentation, the only draw back that remains is the memory overhead of the linked list structure.

A skip list is a clever and interesting method of speeding up lookups in sorted linked lists. It's possible, though, that cache misses still give it a disadvantage to vectors.

I'm glad that our professor emphasized the linear search bottleneck in the DS course. I still use linked list a lot, but the cases are almost always about some other abstract data structures like a stack or a hashtable (for each slot, not the whole mapping, of course). If something by design only uses head/tail removal or requires linear search anyway, linked list is the way to go. When sorting comes into the play, the first things that go through my mind would be an array, a heap or a RB tree. You'd better retake the whole data structure and algorithm curriculum if you come up with a linked list first.

Very good to pick up this topic. Honestly data being randomly all over the place makes these JS/TS languages even more slow than the slowdown that GC uses... Btw I have a data structure that uses a locally linked liist with all kinds of trickery to make it still continous in memory. However you skimmed over whatt he talks about having multiple bytes wasted for the forward and back pointers... In my case the data locality is not so shit - I totally try to make linked data close, yet I had to fight with the pointer overhead too! That is for example instead of using pointers I started using 32 bit indices when there is a jump - just because its smaller. Imagine this data structure templatized with x,y,z float triplet (like Vector3), which is small enough that 32 vs 64 bit size wasted for the pointer counts HUGE - not just in memory use, but in cache use. also people seem to think "not used memory is wasted memory" however memory in use also means cache collisions more often... winblows people never understand why its better to have minimalism, than the OS trying to keep everything in memory for "what if the next moment it is needed". Page table handling becomes harder, addresses for cache lines that mix with each grow, all kinds of subtle issues. TL;DR: pOOP style really hurts performance...

Almost always vector is the rule. Unless it's C#, because C# List is equivalent to C++'s vector. The only reasons to ever use a list for storage are if it's intrusive (like intrusively linking slabs inside an allocator) or if you have a collection that's constantly changing and your objects have a highly complex move.

I think what he is missing is vertical scaling. Make the stored type 10 or 50 bytes and the overhead of the pointers will go away and the copy issue of the array will get a lot worse. Would like to see the performance graphs with larger types.

If the size of the thing you are putting in each linked list node is comparable to or larger than 8 kB, linked lists start performing better again (though trees will do even better since for large nodes extra pointers per node are cheap). But the default page size in virtual memory is 8 kB, so fetching the next element during a linear scan will be a cache miss anyway even if you use a vector That 50-100x ratio is basically the ratio of the node size to the memory page size. Also, Rusts btreemap is _incredibly_ underrated if you plan on iterating through your keys or look up closely related objects often

In specific use cases, you can make using a vector even more efficient. For example, let's say you are first populating your vector with values that occur in some set of data, and then after that you are deleting from that vector any of those same values that occur in a second set of data. So after you populate the vector, then you sort it, and then when you go into the deletion procedure you do NOT move any items in the vector at all, but merely NULL those entries. No moving necessary. And then, if you want, you can create a second vector, traverse the first vector and populate the second vector with non-null values, and then deallocate the first vector, and just use the second vector.

You could also put a linked list into an array, where you store the next and the previous index in each element. And the removed elements, which are still inside the array also form a linked list in the same array. No custom allocation, pretty cache friendly, and almost all operations are O(1) until you resize. And sorting doesn't need to copy the elements itself, but only the indices.

If you do head or tail removal, you would leverage a dequeue or other FIFO like structure made for that, to still maximize cache hits, not a linked list. Pick the structure that minimize the services you need of it :) I would also say, off the record that it is bold to go and comment on a Bjarne Stroustrup presentation !

Maybe I missed it, but when doing the insertion on the linked list you have the pointer to the last thing you inserted. if the next random number to insert is bigger than the last you don't start at beginning of linked list, you start at last item you inserted. I haven't thought this out, but it seems quicker

These criticisms of linked lists are usually based on certain assumptions of bad surrounding programming practices which make linked lists perform badly. Insert IQ bell curve meme. The first assumption is that nodes will be individually dynamically allocated with e.g. malloc/free. In fact, allocating linked lists as a static array or on something like an arena allocator - potentially all at once, instead of individually per element - can eliminate not only tons of allocation overhead, but cache misses as well. If list elements are linearly allocated, cache coherence is very high, and you only have to worry about fragmentation as elements are shuffled around, contingent on your usage. The next big assumption is that pointer traversal is inherently slow. Not so. As above, cache misses are the main cause of slow pointer traversal on modern hardware. Following a pointer to a location in cache is very fast. There are a couple other related assumptions I'll point out - namely, the assumption linked lists are being used as generic containers, as non-intrusive linked lists, and that the element size is small. Generic containers are indeed not always an ideal use case for linked lists. Intrusive linked lists are also often more desirable. And the overhead is amortized somewhat when you are using larger elements, such as game entities, versus having a generic linked list of small elements like integers. If you keep all of this in mind and use linked lists tailored to your specific use case, with allocation patterns that aren't stupid, you will get dramatically better performance out of them. Even fragmentation, which slows them down significantly due to cache decoherence, usually indicates usage patterns that vectors/arrays are very poor at (lots of insertion and removal from the middle). Here is a good writeup by Ryan Fleury of the case for linked lists: open.substack.com/pub/ryanfleury/p/in-defense-of-linked-lists

What program are you using to do the diagrams at the beginning? And what text editor are you using at the end?

4:07, 6:48, that's bull, just keep existing allocations even if they're removed from the main list, like this: buff = all head = ... kept = NULL when a link is removed just move it to the "kept" linked list instead, whenever you need a new link you check to see if "kept" is NULL, if not take from there, otherwise you make an allocation. The links are instead offsets from the current link determined from a simple link->next = a - b which in turn is used for link = link + link->next, the "head" and "kept" will always be an offset from buff, this method gives the speed of buffer allocations + the speed of linked list management

Linked list is better when we need to insert or remove elements in the middle of lists and we also already have a reference to element next to it, which is kinda very specific. Removing head element, like chat said, is not really strong reason (but still good one) to use linked list, since vector with ring buffer (or something like deque that usually implemented using vector) is still better. Real use case is modified linked list that usually used by functional language to do "immutable" list with less memory footprint (less copied), which is understandable.

Where LLs are used, like in Linux kernel one does not do list traversal. Things have pointer right to the node they care about and add, remove/add it/other nodes right there.

As a general rule of thumb, if you have to look for the element in your list, linked list are usually beat by some kind of array construct, because the search is still the same assymtotic speed as the more expensive operations on array constructs, so it comes down to the exact cost inside that, and linked list can easily end up with a lot of overhead. Now, one can then try and come up with some specific cases where linked lists should be better, but in practise I do not recall an instance where a well set up array construct could not handle it more efficiently. In the end, the main use of linked lists are as a basic concept of nodes and graphs, which can then be used to construct more advanced datastructures, like trees, that do contain some more advantages. Also, it can often be useful to fist think of a problem in terms of a node datastructure, and then figure out a way to effectively turn it into an array construct of some kind, for instance you can handle a lot of cache-misses by simply implementing your linked list with indexes in a larger array instead of in general memory. In reality, most of structures like this are not used with the purpose of performance, but because they can be more readable, maintainable, and easier to work with, especially once you build several layers of such things together. In most cases I use a hashmap of some kind, it is not because I really need the special hashmap performance (hint: hashing can be expensive, and hashing cheats a bit to appear to have constant operations, by just starting with large enough constants that you would not reasonably escape to the part where it stops being constant), but because I want something to be stored based on just some hashable value, usually either because it is convinient for the problem or because it makes it more readable or quicker to write. In practise, you often get a fairly performant result by structuring the inner part of the logic in array constructs of some kind, and then you can build the other structure through nodes, maps and other convinient data-structures. This works, because a lot of the advantages of array constructs fall off once the content of said array are pointers, and directly and fully building larger problems with multiple levels combined into efficient array structures is a nightmare in maintainablity.

Just saying that I'm watching his course on frontend masters and its fenomenal! Such an awesome work Prime! I'm loving it!

yeah head insertion/deletion, or things that can be effectively reduced to head insertion/deletion. if the problem you're solving is amenable to having a "cursor" (or multiple "cursors") linked list would still be better because it avoids the search you'd need for true random access. has the side benefit of letting you do thread safe access with fewer locks too, although i think in most practical cases you don't actually need every thread to be able to randomly access any element in the list at any time. if your access pattern is random you'd probably want to divide your list up among the worker threads instead, or have some kind of batch update scheme.

A deque in python is also implemented using doubly linked list, hence searching for a node in the middle of the list will be O(n) where using a vector would be better unless you only work with popping the first and last elements.

Is it possible to explicit case an array to a linked list and then link the two? Given 1..69420 as an contiguous array, then remove one element, instead of creating a new array thats array1.length -1, then copy 0 to n-1 to array2 and then n+1..array.length-1 to array2 at element n, could you just recast the array1 as a linkedlist, replace elements n's value with the memory address to element n+1?

I don't like "Avoid " videos, every DS has its use, for something like unordered data or streams LL are the only option.

There appears to be two types of linked lists taught: one where a node is a separate object, and one where the node is a composite member. The latter I have only seen done with kernel programming in C, because constructs like CONTAINING_RECORD cannot be done in high-level languages such as Javascript. For example, if you have a process object (struct task_struct on linux or KPROCESS on windows), removing that process from the list does not require iterating all processes because you can directly access the list_entry member. Whereas for generic containers, the node is external and must be searched.

there's a good video by computerphile on this topic, called "arrays vs linked lists", in which they compare this on computers with and without cache

Wow I saw Mr Stroustrup during lunch at a conference years ago, he looked to be in his 40s. He was talking about his Tetris scores. Time sure flies 😮

The main reason for avoiding linked lists and preferring array-based structures is that the machine memory since dr. von Neumann and dr. Turing is an array, not a linked list.

You generally use (double) linked lists when you want fast deletion and fast "top" insertion and you have to iterate all elements anyway. In fact, i'm doing an entity system for a game and i had to do BOTH dynamic buffer (std::vector) and linked lists, and with relative pointers instead absolute pointers to avoid dangling pointers. Use the std::vector for memory buffer, a stack for reserving all the free entity and a linked list to iterate just the entities that is not freed.

I've done some work of trying to optimize algorithms, and this is my opinion at the moment: - The tighter you can pack your problem in memory the faster your algorithm will run. - The CPU is fast, memory is slow - It may be best to think of memory as linear-access rather than random-access. The number of passes through memory your algorithm needs determines a lot about performance. - there isn't much that can substitute for just testing different implementations of your problem. (Though the specifics of your system may influence the results a lot)

In C#, Java, and Kotlin I literately never had the a problem that would be solved with a linked list while in C I've seen people using it all the time. Is it a lack of generics/templates or are they actually good for something?

this is so cool. i'm self teaching rn and learned about the different cpu components yesterday. abusing the cache with a simple array over a more complex structure like a tree or list with nodes sounds super interesting. i'll start to code up a hybrid in c with different node sizes where each node is an array that fits in cache. gotta do some more research tho how the diffrent cache levels interact when loading a node like that on my intel cpu. on an amd something like this could also have insane multi core performance when the infinity fabric is abused with each core dealing with a different array(node) with, tho i did not study amd cpus yet and don't have one

I like these types of videos. Like pair learning. Didn't realize linked list was so slow compared to arrays, but it makes sense.

I don't get where the idea to use a linked list comes from for this example. Sometimes you already have a pointer to the insertion/deletion point, I feel like that's the only interesting use case to compare. Like "userptr" in some library, a dictionary matching UI element to a linked list node or something like that, no linear search involved.

well, do you HAVE to do a linear search every time ? i always thought that linked lists only are viable with some sort of indexing, of a tree, to get to the point faster i learned this, like, second semester of computer science

There is no guarantee an array is consecutive in memory. Not in virtual memory, not in physical memory and not on disk. If you look into the malloc functionality you will discover this. You will also encounter how they store long lists of things to manage the always moving, allocating, deallocating and even resizing of the allocated page list.

Lispchads I don't feel so good!

I call a linked list, a leaked list. One mistake and you leaked memory

To my understanding of the question, if you have 100k elements and need to remove the one at 702, you can index directly to that element with a vector and it just requires a memory copy to move the elements down and that memory copy is amazingly quick because the data is contiguous in the cache. With a list, it's never going to be contiguous and possibly in a different numa and you have to traverse the list from the start to the desired node to remove the element.

I would try making a parallel index of pointers, in an array, ordered. The objects would be stored in a linked list because of faster allocations. But for search, an ordered array of pointers without rearrange would be good, depending on the size of elements.

if you have a pointer, or an iterator/IENumerable depending on your language, it's fast to insert around it. It's only slower if you use it the same way as you use vectors, WHICH THEY ARE NOT MEANT TO. There's a reason there are both vectors and linked lists. I sped up a lot of my programs by using linked lists. I remember having a competitive task where I had to insert N numbers before Mth character. I took the iterator to the Mth character, and just inserted to the list from that iterator. IRL applications are queues, dequeues and stacks. If I know how much I need to insert into memory, it's the array/vector that's the best. But if I have teoretically unlimited insertions, vectors quickly start to have bottlenecks, and also the memory taken by it, since there is a massive memory padding in huge vectors. (it is worth noting the built in stack, queue and dequeue are all using vectors and not linked lists tho)

We were taught the same thing about using lists, but the condition on these algorithms was always that there was no space limit aswell as allocation and other things that are done in the background were not considered/ irgnored, to fully focus on the efficency of the actual algorithm you'd write

In Haskell, linked lists are used more than anything else, and it's common for a list to be produced by one function while it's being consumed by another, so the whole list is never in memory. For updating/inserting/deleting elements at random positions in a container, I'd use a sequence, since if you use an array, you have to copy the entire array every time you update one element.

What's the drawing tool you use to make those diagrams so swiftly?

I remember seeing this video around 10 years ago when I was in university, and having my mind blown. Very satisfying seeing the same look on Prime's face.

This is why you really want some kind of tree of arrays, with the nodes annotated with data that lets you look up by index rapidly. Ideally each of the nodes sits in a page, including the node annotations.

If you'd have shown me a picture of him and asked why I thought he was famous, I would have said he was that German cannibal.

7:39 I love how excited Prime became

A lot depends on the language, compiler version, operating system, architecture and usage patterns. Always benchmark and look at your metrics before jumping to conclusions. At first prefer the simplest, most readable and most idiomatic version of the code. Optimize when absolutely necessary.

Every language construct is a tool. Use the appropriate tool for the job. If it's a short list and you don't expect it to grow you can get away with an array. Push comes to shove you can always realloc if you need to grow the array, and using a logarithmic scale for memory allocation can help. The advantage of a linked list or deque is insertion and deletion times are fast, you don't need to worry about indexing (if you shuffle an array any indices you had previously are now invalid). Sorting can be more efficient in a linked list than in an array (and I would say if you need fast sorting, just go with a self balancing tree structure). Disadvantages are that it takes more memory, and searching is O(n) vs O(1). If you have less than a hundred items though O(n) and O(1) are pretty close in terms of magnitude. Memory ends up more fragmented, which can be an advantage on smaller systems with less contiguous memory available. At the end of the day they are just tools, and just like you don't use a hammer to turn a screw (you could always brute force it, but that never turns out good), you should use the appropriate tool for the job.

Cache coherency is important! How do the insertion and deletion operations on a vector affect it?

Cool topic and I admit that I didn't think about it like that, either... but I always arrange my data in arrays if I can. That includes the way I define objects. If "some thing" has to do the same function a lot of times, I allocate arrays for the data. The main reason why I do this is memory layout. By pre-allocating a fixed memory block and checking range all kinds of nasty dynamic bugs can be avoided because the system always knows how much memory it has left.

This also gets much faster when you’re talking about caching. Data locality is king and keeping your data compact like this enables stupid fast lookup because the memory will always be in CPU cache. This is literally the idea behind ECS (entity component system). Essentially create a compact list for each component of an entity rather than Malloc a bunch of objects with the components attached. Because the components are compacted and destructed in this way, you get more cache hits and improved performance for your simulation

At 5:36 i have started screaming "B+ Trees, goddamit!". It is an unrolled linked list with a tree as a search index assistant.

If you need to keep the order of insertion, a LL with a hashmap matching values to their node (or ancestor node, in a singly LL), works just fine. I know, not the most common use case ever, but, still...

The one place I see linked lists pretty commonly in the Real World is in allocators, for example if you're managing your own free list. Since you can't control what malloc actually *gives* you as far as a memory address, it can be helpful (and way faster) to keep track of the pointers that you *are* given and their size, and serve those up first when a new allocation is requested, before asking for more memory. This is mostly a video game code thing, and this saves cycles, so while it may seem like we're splitting hairs over fractions of a second....we are. We try to avoid *actual* allocation and deallocation at all costs.

Before the video starts: Because they are less efficient than having an array, even if it is a ListArray that doubles its array size when necessary. LinkedList means the items are all over the memory and therefore it's slower. Edit: And yes, the 'n' complexity for get, set, delete. Getting a value is basically always needed at least once... unless you traverse it step by step and do something as you go... well then it might be _not as bad_. Still worse than array even in that case.

I kinda thought the optimal would be somewhere in the middle. where you would map to vectors which are the size of a cache block. So you load vectors of like 10000 elements in to the cache then go to the heap periodically to fetch the next block.

I've seen the weirdest linked list interview challenges... putting numbers in a linked list digit by digit in reverse order and then "adding" the linked lists and turning the result back to a number. Never in my career did I encounter a use case for linked lists. Now I realize I've been doing math wrong the hole time...

a doubly linked list will be much faster if you're doing lots of head-insertions or concatenation. Honestly speaking, I can't remember the last time I've removed random elements from my data structure.

is this the guy responsible for making cpp

And in C++ std::vector you can preallocate space upon creation, so adding new elements will be very quick (up to certain point).

That was kinda the same argument for Unity engine to introduce ECS, they explained how OO code was slower, and using arrays was faster because objects were contiguous in memory, benefiting from CPU caches

When I was learning about linked lists using Java, I made them manually. Each element (data + pointers) was its own object. While debugging I dumped the pointers of the objects to the screen, and was horrified to discover that objects were scattered around the heap. The compiler knows how big each object is, why not pack them together--which would at least give you some cache hits. But that's not the way Java works. I've never tested C++ to see of the compiler randomizes the location of things in the heap. Perhaps I should. Anyway, I believe Stroustrup. Doing a linear search of a linked list is far slower than doing a linear search of a vector (or an array). With the list you not only get to fool around with pointers + data, rather than just data with the vector, but if the compiler randomizes the location of the elements you are guaranteed a cache miss for every access. Of course that'd be the compiler's fault.

I suppose if you have a strange situation where you already always have the relevant pointers to the elements of the list stored somewhere, then using them to do the insertions or deletions would be efficient. But what would be a problem that would be structured that way?

What tool are you using for sketching when you start explaining at 1:00 ?

video quality is so good that it looks like I have myopia

making you memory more cache friendly is the whole point of Data Oriented Programming, I feel like more people should know this exists.

You have to do a linear search on an array if you are looking for a specific thing within the array....the only difference is the reference look-in and the cache misses that cause a slowdown, but it's still considered O(n). The bigger point is when you have data that stores a pointer to within the linked list for fast referencing, and when that object is destroyed, it can quickly delete itself from the list without having to move all other elements at a O(1) speed to search. These are also more thread safe and can be handled in multitasking efforts unlike arrays where elements can change mid-search (a linked list that changes other elements within it won't affect the read because the list doesn't shift). Linked lists can also be sorted in-place without ever moving memory position. A bridge can be formed in order to move any active throughput points into a new set without effort, which makes sorting also thread-able. Objects can move between linked lists in-place and thereby anything that has a reference to it will not have to change its reference, retaining all other data across the move. So...basically....arrays are great for....quicksort stuff? I honestly don't know the point of an array unless it is literally a math vector or a place to store sync or roundrobin data....linked lists are better, at just about everything. I'm sure you can inch out a few ms of speed, but I prefer flexibility and expandability over perceived speed (which can be improved using several links in an octree fashion anyway)

I was hired as a 'systems administrator' and I was looking over the shoulder of the guy who was working on a custom MySQL table engine that was key to what the company did. I pointed out an indirection in a data structure the guy was using and told him that it would be a lot faster if he removed it. He did it, and I was right, and he was a little surprised and rather pleased. 🙂 I also dissected the file structure of a proprietary b-tree and wrote code in Python to traverse it and highlighted a way in which they were doing the comparisons wrong in their own code to manipulate this structure that would result in an inconsistent b-tree.. They fired me after I worked there for three months, and after they had begged me to switch from being a contractor to being an employee... it was all pretty obnoxious.

I'm curious about the diagram at 1:02 was he explaining something with it on stream?

When I first heard about big O and linked list I couldn't understand why everybody ignored the fact that you have to get there before removing or inserting something. Why is that process ignored?

I just took a class at NYU (DSA) and they went into all of this and wayyy deeper, but this was a nice refresher lol

What diagramming/drawing app is this?

Link List vs Vector is good example of why you can't just look at Big-Oh.

I love his remark about people thinking 1000 elements makes a large list. Performance experts tell you to measure everything for a reason.

Only time a linked list made sense to me was when I was storing really large state objects in a ring buffer (2000 simulation steps "forward") for visualising orbits. It was basically a huge FIFO queue and using a linked list meant I didn't have to reorder anything

Linked list is taught as an practical alternative to arrays to fledgling programmers, but raw linked list is actually only useful as specialized data structure.

It is a really good discussion, we tend to overlook how much more performant contiguous memory can be. However, if I did not miss it, shifting of the array indices is not mentioned here. I believe it is convenient to point out that for operations that add/remove an element towards the start, list can be more performant as there will be no index shifting. If same operation is done for an array, it takes O(n) to modify the indices of elements in the case where the first element is removed. It is not easy to tell at which point array starts to compensate for shifting operations by providing more performance via contiguous memory. However, for tasks where we are more interested in first or last elements of a list, it would be wiser to work with stacks or queues. Considering this, if we are generally comparing list and arrays for manipulating elements of mostly mid-indices, array seems to be the way. Even if it performs worse in some cases, it is more measurable and predictable as stated in the video.

But what about the case where you combine a LinkedList with a HashTable, so an item can be looked up by ID without traversal and removed. If the majority of your operations are removing (e.g. a trade orderbook 80%+ are order cancels). Is this then faster? I suspect even then a vector could be faster (especially as orders in a price level can be binary searched), but I've often wondered. I should benchmark some day.. RE Javascript, there is no definition of how arrays are stored. I suspect that the JIT would try to use a vector, but then fallback to a hashmap depending on if e.g. it is a sparse array or the items are not of the same type/size

Sometimes, it's okay to increase indirection if it makes the overall structure of your code more manageable, testable, and maintainable. If you're making a game or working in high-frequency trading, go ahead and be particular with how you allocate memory and pass data around, but if you're working with enterprise microservices handling thousands of API calls per second, a few cache misses is negligible compared to network latency, load balancing, and visibility of issues. Software is full of tradeoffs, and part of being an engineer is knowing what things to value in each situation.

This is why the dominant list implementation in java is using an array in memory so you at least have a nice vector of primitives or pointers to the objects