In the early releases of Linux, the cache locality argument wasn't as prominent an issue on the hardware of the day. So the computer science textbook argument of O(1) inserts and [if you have the node pointer already] removals was more compelling.
In the early releases of Linux, the cache locality argument wasn't as prominent an issue on the hardware of the day. So the computer science textbook argument of O(1) inserts and [if you have the node pointer already] removals was more compelling.
Or are pools used to avoid that?
Well not explicitly, but it uses a version of malloc that has a pool for every rounded object size.
But your question reminded me of another aspect of linked lists in the Linux kernel: unlike a lot of high level languages, there isn't an extra allocation for a node structure. The node structure is a member of the structure being linked.
Often the structure being linked might be something like a reference counted heap object, so the question of adding an extra member to store the next pointer is not a big difference.
That's good, but it seems like how-hanging fruit. Boost offers intrusive_prt for this. [0]
make_shared goes half way, and performs a single allocation to return a shared_ptr to a new object. It eventually made its way from Boost to the standard. [1][2]
See also [3] which contrasts the two. (As you can imagine, intrusive_prt is slightly more efficient.)
[0] https://www.boost.org/doc/libs/latest/libs/smart_ptr/doc/htm...
[1] https://www.boost.org/doc/libs/latest/libs/smart_ptr/doc/htm...
[2] https://en.cppreference.com/cpp/memory/shared_ptr/make_share...
He actually cited this use case, of a structure that has list or tree nodes inline with the data type, as a strength of the model.