3 ms·
Let's take the case where we need to add to any element of the structure, with uniform probability. For an array, this means we'll have to move N elements if w
by tsimionescu 4y ago
Let's take the case where we need to add to any element of the structure, with uniform probability.
For an array, this means we'll have to move N elements if we need to add at the beginning, N/2 if exactly in the middle, or 0 if at the end. Either way, we'll need to re-size the array, which has some chance of requiring N copies anyway - say, half the time. So, on average, we'll perform 3N/4 moves per element added, requiring 1 cache miss every time.
For a (doubly-)linked list, this means we'll have to traverse 0 elements if we want to add right before Head, 0 if we want to add right after Tail, and worse case we'll need to traverse N/2 nodes if right in the middle - so, we'll have to do on average N/4 traversals per element added. Each of the nodes traversed will generally be a cache miss, so N/4 cache misses. So, the Linked List will indeed be require a third the number of operations on average, but many times more cache misses, so should be expected to lose. If you store the middle pointer as well, you'll again half the number of operations for the list, but that still won't cover the amount of time wasted on cache misses.
Of course, if the distribution is not uniform and is in fact skewed near a predictable element of the linked list, at some level of skewed-ness vs cache speed advantage, the Linked List will overtake the array.
Note that linked lists also have other advantages - for example, they can be used as in the Linux kernel to store the same object in multiple different lists without any copying and without extra pointer indirections (at a small cost of one extra pointer in the object per list it could be a member of). They are also easier to pack into a small address space that has to be dynamically allocated (since you don't require a large contiguous block).