[jstimpfle]

Don't forget that there are valid uses of linked lists even in 2017. If there are more insertions / removals than scans, an array makes no sense.

Reallocating a big dynamic array is also a no-go in many time-constrained situations.

> You actually have to allocate the memory for the node, too.

The way this is done is by intrusive linking (the data must include list pointers). The data usually knows in which lists it is linked, so there is no point in having a version of the data without a list head.

[kazagistar]

Almost any insertion requires a scan.

[wtetzner]

Well, given that the pointers are contained in the nodes themselves, if a piece of code is already looking at a node when deciding if an insertion is needed, then no additional scan is required.

[jstimpfle]

Many do, but there are also insertions in unsorted lists or insertions after a given element...

[Retric]

Cache means inserts into arrays are often faster than linked lists. Remember RAM is really really big and slow.

[PeterisP]

Not if the list is allocated within a slab, as described in the article. Imagine list elements allocated continuously (as in an array) but the ordering is decided by the pointers within each node, instead of assuming a fixed order. All the elements still are in the same cache line.

[Retric]

Linked lists take more memory than arrays, so even in your example it's not as obvious as your making it out to be. Further, your ordering assumes no deletes.

[signa11]

>... inserts into arrays are often faster than linked lists.

don't forget, deletes, as well.

[Retric]

Yea, it's really seeks being horribly slow on out of cache linked lists being horribly slow, and then inserts and deletes being fast once you find the right node.