[jekub]

There is a lot of reason why you can prefer a linked-list over an array, even with the hardware changing they are still a lot more efficient in some cases :

  * In multi-threaded context insertion and deletion can be done lock-free which is not the case for arrays ;

  * For intrusive list, insertion and deletion can't fail due to memory allocation ;

  * If you do only insertion at the tail and removal at the head these operation need only a pointer change which is more efficient than an array ;

  * Merging two list is only one pointer operation ;

  * Intrusive list have better memory allocation properties ;

  * ...

If you look at the usage of linked-list in the kernel you will see that they are used for reasons.

The problem is that, on new hardware, linked list should be used in less cases that in the past and some people have generalized this to linked-list should never be used. This is false, if you care about performances you should keep thinking and testing what is the best data-structure in different cases. If you don't care about performances, you should use an abstraction who implement what you need and don't car about the underlying data-structure.

[josefx]

> In multi-threaded context insertion and deletion can be done lock-free which is not the case for arrays

I just love when multithreaded code frees the element I currently iterate over in a different thread.

> For intrusive list, insertion and deletion can't fail due to memory allocation ;

As long as you store your elements on the stack or use static values you mean? Heap allocation happens at some point, you just move the location where it happens.

> If you do only insertion at the tail and removal at the head these operation need only a pointer change which is more efficient than an array

Use a circular buffer. Until the array is full you can just modify the start/end pointers.