3 ms·
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
by jstimpfle 10y ago
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.
- Retric 10y agoCache means inserts into arrays are often faster than linked lists. Remember RAM is really really big and slow.
- signa11 10y ago>... inserts into arrays are often faster than linked lists. don't forget, deletes, as well.
- Retric 10y agoYea, 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.
- PeterisP 10y agoNot 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 10y agoLinked 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.
- kazagistar 10y agoAlmost any insertion requires a scan.
- jstimpfle 10y agoMany do, but there are also insertions in unsorted lists or insertions after a given element...
- wtetzner 10y agoWell, 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.