Comment by tmd83
5 years ago
But the memory usage isn't considering growth. If I grow by doubling the size (seems common) at n+1 element where n is the last allocation, one would allocate n2 + n (the original until the copy finishes) vs. n (pointer(s) + element size).
But yes the size advantage is very reduced for most use cases. What would you imagine the cases where LinkedList is still a valid data structure?
> If I grow by doubling the size (seems common)
True. Then it comes down to the size of your data vs the size of your pointers.
> What would you imagine the cases where LinkedList is still a valid data structure?
Compared to an array? When the array doesn't have the behavior that you need.
For instance, if you need to keep a stable reference to a particular element in a list, even while that list is being inserted into, then an array is not going to cut it. The linked list handles this case with ease.
That's not to say you can't write a wrapper for the array that does the right thing, probably for cheaper. But out of the box the linked list can do things that the array cannot and if you rely on them, then use the right tool for the job.