What are appropriate applications for a linked (doubly as well) list?

Question

I have a question about fundamentals in data structures.
I understand that array's access time is faster than a linked list. O(1)- array vs O(N) -linked list
But a linked list beats an array in removing an element since there is no shifting needing O(N)- array vs O(1) -linked list
So my understanding is that if the majority of operations on the data is delete then using a linked list is preferable.
But if the use case is:

• delete elements but not too frequently
• access ALL elements

Is there a clear winner? In a general case I understand that the downside of using the list is that I access each node which could be on a separate page while an array has better locality.
But is this a theoretical or an actual concern that I should have?
And is the mixed-type i.e. create a linked list from an array (using extra fields) good idea?
Also does my question depend on the language? I assume that shifting elements in array has the same cost in all languages (at least asymptotically)

Answer 1

Singly-linked lists are very useful and can be better performance-wise relative to arrays if you are doing a lot of insertions/deletions, as opposed to pure referencing.

I haven't seen a good use for doubly-linked lists for decades. I suppose there are some.

In terms of performance, never make decisions without understanding relative performance of your particular situation. It's fairly common to see people asking about things that, comparatively speaking, are like getting a haircut to lose weight.

Before writing an app, I first ask if it should be compute-bound or IO-bound. If IO-bound I try to make sure it actually is, by avoiding inefficiencies in IO, and keeping the processing straightforward. If it should be compute-bound then I look at what its inner loop is likely to be, and try to make that swift.

Regardless, no matter how much I try, there will be (sometimes big) opportunities to make it go faster, and to find them I use this technique. Whatever you do, don't just try to think it out or go back to your class notes. Your problem is different from anyone else's, and so is the solution.

Answer 2

The problem with a list is not just the fragmentation, but mostly the data dependency. If you access every Nth element in array you don't have locality, but the accesses may still go to memory in parallel since you know the address. In a list it depends on the data being retrieved, and therefore traversing a list effectively serializes your memory accesses, causing it to be much slower in practice. This of course is orthogonal to asymptotic complexities, and would harm you regardless of the size.