How is a vector good for inserting elements in the middle? That is O(N). Where is the O(lg n) cost coming from?
>> your default be a vector and not a linked list
The default should be to understand the problem.
How is a vector good for inserting elements in the middle? That is O(N). Where is the O(lg n) cost coming from?
>> your default be a vector and not a linked list
The default should be to understand the problem.
If you want lock-free atomic data structures there are lots of variations (like AVL trees) that can be used as the underlying storage and just like mentioned above it tends to work well for most use cases and access patterns.
If N is fairly small and/or you allocate most of your linked list around the same time it may not matter which is why measuring your actual program with real-world data and access patterns is so important. eg if in production logging or other malloc traffic ends up making your linked list nodes spread out in memory perf is not going to match what you tested at your desk.
Often an algorithm can operate on an entire cache line's worth of data before main memory can chase down a single pointer. Modern CPUs hide that with prediction but even if the address prediction is 100% accurate if the result is a pointer loading chain you run out of pre-fetch slots pretty fast.
To give concrete numbers if DRAM is not busy refreshing and there is no bus contention or inter-core contention then we might get 60-100ns access times all told. If we have a 3Ghz CPU then that's 300 cycles waiting around doing nothing... for each pointer that needs to be dereferenced. For a vector after the first 300 cycle hit the rest would be free - following nodes are in the cache line and address prediction will pre-fetch subsequent cache lines as well, allowing pre-fetching to stream data ahead of when it is needed.
Both an array and a linked list are O(n) for adding in the middle. In an array, you finding the middle element is O(1), then moving the rest of the array is O(n) [you have to move n/2 elements]. In a linked list, finding the middle element is O(n) [you have to traverse n/2 elements], but adding it is O(1).
So, asymptotically there is no difference. In practice though, the linked list traversal will cause O(n) cache misses to reach the middle element (since we are traversing random memory), while the array move will only incur O(1) cache misses (since we are accessing memory in order) - so, the array will actually win in practice.
Edit: Note that I also don't know where the GP got the O(lg n).
I suppose if the LL like structure is mostly read only with rare inserts, not that big and holds simple data types or structs and often needs to be read sequentially then an array/vector/list would be better than a regular LL but then it is obvious that an array is better anyway.
It's poor guidance to tell people that the vector is the "go to" when you need a LL. Sad actually that this poor guidance has been upvoted by so many people such that it is the top comment, all in the name of some FUD about cache misses.
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).