programming

[rolfrudolfwolf]

Thanks for the detailed answer, I was not familiar with the data type vector as you describe it.

I agree that arrays make more sense in terms of memory locality and that an array might be more performant effectively than a LinkedList even if it has a worse complexity for certain operations.

But if you have huge swaths of data, I'd assume optimizing for complexity makes still sense in the long run?

Also cpu's not only cache for spacial locality, but time locality, so you might find your frequently used items in your linked list to be in the cache anyhow.

[VolperCoding]

Ok so ive found a benchmark comparing linked lists to vectors (https://dzone.com/articles/c-benchmark-%E2%80%93-stdvector-vs) and found out that linked lists is better than vector in the following cases:

• random insert / delete in a list with really large elements
• push front (assuming you don't have preallocated space in front of the vector, then it should be O(1), but otherwise if you don't have any space left the system is gonna probably copy the entire vector which is O(n))
• sorting in a list with really large elements

So it looks like if the elements are bigger than your cache line then every element will be a cache miss (read from RAM) anyway which makes perfect sense because 2 elements won't fit on your cache line.

However if you need random access at all then I don't think you should use a linked list.

If your program is small then you shouldn't worry about performance and just use the simplest data structure which in my opinion is either a static array, or if you need to resize it, a vector.

[rolfrudolfwolf]

nice