> The last time I used [a doubly linked list] was in the nineties. I know the Linux kernel uses them, but that design was also laid down in the nineties; if you were designing a kernel from scratch today, you would probably not do it that way.
Curious to know in the Linux context whether moves away from doubly linked lists have ever been tested?
Linux uses them because it has a lot of lists of objects that very rarely or never need to be iterated over, but where it needs to be fast to
- Insert a new item
- Delete a specific item (that you have a pointer to
- Move a specific item from list A to list B
- Get the next item to work on
And where pointers to an item need to be stable. Doubly-linked lists are very fast for all of that; their main downside is they are slow to iterate over due to cache incoherency but that doesn't matter if you very rarely or never iterate through the entire list. And since you need to have stable pointers to items in the list that don't change when you insert/remove items, most other data structures would need an extra level of indirection so you lose the cache coherency benefit anyways.
And they also value for the size of the set to not be bounded, and for those operations to occur without allocation.