<story><title>Toward a better list iterator for the Linux kernel</title><url>https://lwn.net/SubscriberLink/887097/7ca69c6bfa3584c0/</url></story><parent_chain><item><author>bee_rider</author><text>This is really part of the intro, but I wonder if someone knows anyway:&lt;p&gt;My very naive first guess at making a generic linked list would be, of course, a struct with a &amp;#x27;next,&amp;#x27; &amp;#x27;prev,&amp;#x27; and the void pointer to the payload (What can I say? At some point my brain was damaged by OO languages). I guess their method of instead defining a struct, embedding the linked list into it, and then using macros would probably interact more nicely with the type system.&lt;p&gt;Are there other benefits, though? I vaguely suspect their system might tend to prod users toward laying out their memory more nicely.</text></item></parent_chain><comment><author>Diggsey</author><text>Nobody&amp;#x27;s mentioned what is IMO the main benefit of an intrusive data-structure: items within the data-structure can belong to multiple containers.&lt;p&gt;This allows you to locate an item using more than one criteria: for example, you could store blocks of free memory in two intrusive lists, one sorted by size and one by location. This would allow you to first locate eg. the largest memory block, and then quickly locate blocks adjacent to that one in memory.&lt;p&gt;With non-intrusive data-structures this is not possible, because while you can go from an iterator -&amp;gt; the item pointed to by the iterator, there is no way to efficiently do the reverse. This is possible in an intrusive data-structure because the iterator and the item itself are the same thing.</text></comment>
<story><title>Toward a better list iterator for the Linux kernel</title><url>https://lwn.net/SubscriberLink/887097/7ca69c6bfa3584c0/</url></story><parent_chain><item><author>bee_rider</author><text>This is really part of the intro, but I wonder if someone knows anyway:&lt;p&gt;My very naive first guess at making a generic linked list would be, of course, a struct with a &amp;#x27;next,&amp;#x27; &amp;#x27;prev,&amp;#x27; and the void pointer to the payload (What can I say? At some point my brain was damaged by OO languages). I guess their method of instead defining a struct, embedding the linked list into it, and then using macros would probably interact more nicely with the type system.&lt;p&gt;Are there other benefits, though? I vaguely suspect their system might tend to prod users toward laying out their memory more nicely.</text></item></parent_chain><comment><author>loeg</author><text>&amp;gt; Are there other benefits, though?&lt;p&gt;Yes; you&amp;#x27;re avoiding an extra pointer indirection between list navigation and element access, which is usually going to be a cache miss.  Also if you have a pointer to an element of an intrusive list, you can cheaply navigate to the next element; this wouldn&amp;#x27;t work with your external list scheme (you&amp;#x27;d need to maintain a separate list pointer instead).</text></comment>