Comments by "" (@diadetediotedio6918) on "Why You Should AVOID Linked Lists" video.

@christopherpepin6059 No? He did not. He's assuming you already know the position of the item, the index, and if you know the time complexity is constant. With linked lists even indexes need to be traversed in order to get to the correct element, and this is not what make them slower than normal lists. What makes them slower is memory spreading and being prone to cache misses, in this sense a normal vector would perform better even if you need to iterate it entirely first.
3
["If list elements are linearly allocated, cache coherence is very high"] Do you perceive the stupidity of this, right? If the point is to keep the memory contiguous then linked lists <do not present any advantages over normal arrays in the first place>, they render to be useless. You use a linked list because of the constant time insertions/removals so you will still end up in the same problems as you have with normal heap-based linked lists.
1
It does not work that way, I don't know from where you got that impression that "every single list structure uses some form of linking". C# lists with structs are entirely contiguous for example, and Dictionaries are an entirely different beast made for a specific purpose, they are not even classified as lists in C#.
1
@Leonhart_93 O(1) in this case refers to "constant time", it does not matter if the operation is based on a lookup or on loading a file on the disk and then accessing a random piece of data, the thing that matters is that the access time remains the same for any given input, ceteris paribus But yeah
1
It still has the additional cost of keeping track of the generational indexes tho, but they are quite powerful
1
If you have an arena allocator just for this you would run into another set of problems, like the fact that deleting items would still scatter the memory around and create big holes of unused data in cache, which in itself is a problem.
1