We all know the theory, that linked list are faster than vectors when it comes to insert and remove operation. Given the fact that I value proof more than anything, I decided to make a little benchmark in C++ . To objectively measure the running speeds I implemented the followings:
- Insert n elements by preserving ascending order. (For example: 5, 10, 13, 23)
- Delete all n elements, one at a time, from random positions. (For example remove elements at index 3, 0, 1, 0)
You can clone the code from: https://github.com/arpytoth/ListVsVector.git
Now, let’s run our benchmark and see the results:
I bet, you wasn’t expecting that the linked list will be so slow. We all know that the vector operations are Θ(n) while the equivalent linked list operations are Θ(1) but for some reason the linked list was insanely slow. It doesn’t matter what n you choose, the linked list will always be slower than the vector. This happens on insertions and deletions too.
The problem here is that most developers often forget that they are programming actual CPUs with limitations on their own. Indeed the insert and remove operations are faster on a linked list but the dominant operation here is the linear search (iteration through elements).
With vectors during insert/remove you shuffle a lot of elements back and forth but, CPU caches are really good at that. The vectors are random access construct but you can stream them because they are continuous memory locations. A list is not a random access structure but when you traverse it, you access the memory randomly from node to node, in an unpredictable way and your maximizing your CPU cache misses.
Cache misses are really bad because, even though your CPU is fast, the RAM memory access is pretty slow. To speed up the memory access, a modern CPU caches a lot of data into its internal cache. The trick is that it can only cache continuous or predictable memory zones, like vectors.
So, even though in theory should be faster, in practice the linked list structure is slower, unless you operate only on the worst case scenario such as a queue.