The go a bit further than the article on the advantages of intrusive data structures, taking linked lists as an example:
As the article mentions, intrusive data structures naturally lead to one fewer indirection. To do the same with a traditional list (where the list node owns the payload), a different node type is needed for each payload type. This is easy to do with the proper support for monomorphized generics, see C++'s std::list. It is awkward in C, where the implementation has to be macro-generated. C naturally pushes towards an indirection through void *, which makes intrusive lists more attractive.
One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections (where traditional collections would require e.g. one collection owning the payloads, and the other collections merely holding non-owning pointers to them).
Las but not least, the defining property of intrusive data structures is that they leave the responsibility of allocating the elements to the user. The elements can be allocated on the heap, on the stack, in a global array (like "initholes" in the article), in a special arena, etc. It is even reasonable to use non-uniform allocation strategies; for example, for a circular list, allocate an anchor node on the stack and the other nodes (those embedded in payloads) on the heap.
It is awkward in C, where the implementation has to be macro-generated.
You can avoid having the implementation be macro-generated by "hiding" the list pointers before a char payload[0]. See https://pastebin.com/DE69mbJD for an example.
The same technique is used by glibc's malloc to store metadata about the allocation right next to your data, and then recover it when you call realloc/free, without needing a separate metadata allocation.
The caveat is that the type of the pointer does not indicate provenance. For example, nothing stops you from calling list_next on an arbitrary pointer to data that is not on a list, and that would be UB. The same happens with realloc and free, where it's UB if you pass them a pointer that was not returned by the heap allocator.
Zero-sized arrays are not standard. Accessing an array out of bounds is UB. At the very least, you should use a flexible array member instead (char payload[];).
But even if you did that, strict aliasing implies that 'payload' can only be accessed as an array of character type. It is correct to memcpy between 'payload' and another object of arbitrary type T of the appropriate size (as list_push_ does in your example), but it is UB to access 'payload' in place as a T (as main does, by casting to struct point * and dereferencing). Oh, and 'payload' may not satisfy the alignment requirement of T.
There is no realistic strict-aliasing-abiding way around a distinct node type per payload type.
There is no OoB access of an array; the calculated pointer is pointing to the payload object that's residing in the malloc-returned storage right after the node struct.
I think the actual problem is the alignment; that malloc-returned storage simply can't have enough space to hold a "struct { struct node header; PAYLOAD_TYPE payload; }" (which is what the parent comment is trying to emulate) if the payload type has an alignment that's greater than the size of a pointer, and that pointer will be pointing at what would've been the padding in that struct.
Yes, there is. It does not matter that storage happens to be allocated beyond the end of said array. Strict aliasing implies that it is UB to reinterpret the array as anything else. And it is UB to access an array out of bounds.
Flexible array members specifically exist for these dynamically-allocated trailing arrays. They do not solve the strict aliasing problem, though.
if the payload type has an alignment that's greater than the size of a pointer
The amount of padding is implementation-defined. The only portable guarantee is that 'payload' is aligned for its element type, char. To over-align, use _Alignas, as in:
struct node {
struct node *next;
_Alignas(max_align_t) char payload[]; // Satisfies all fundamental alignment requirements
};
It does not matter that storage happens to be allocated beyond the end of said array.
It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned.
Strict aliasing
...is not violated; memcpy takes a void pointer as its destination, sets the effective type of the storage behind it, and the treats it as an array of unsigned chars.
It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned.
You can certainly store an object of arbitrary type, but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds.
memcpy takes a void pointer as its destination, sets the effective type of the storage behind it
And, in doing so, may very well overwrite the unspecified padding following 'payload' in the structure, thus instantly destroying the effective type of the structure object itself. Subsequent accesses to the structure or its members will be UB.
It seems to me that your argument hinges on two assumptions:
- there is no padding following 'payload' (this would have to be statically asserted),
- the pointer to 'payload' is indistinguishable from the pointer past the structure; in particular, provenance is not an issue.
but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds.
When you do "void *x = malloc(sizeof(struct node))", the returned storage doesn't have struct node object in it, it has an object of no effective type in it, with size "sizeof(struct node)". Taking the pointer to payload[] field is in no way different from doing "(char*) x + offsetof(struct node, payload)" — it takes a char pointer into the object storage, adds a number (less than the object's size) and so produces another char pointer that points somewhere inside into the object storage — and no, since there has been no actual referencing of the object's value, constructing such a pointer does not set the effective type of that object; and a char pointer is explicitly allowed to alias whatever storage. Then the memcpy sets the effective type, done. No UB anywhere.
Taking the pointer to payload[] field is in no way different from doing "(char*) x + offsetof(struct node, payload)"
It may differ, depending on the precise notion of provenance being applicable. If provenance only has allocation granularity, I suppose that there is no difference. I know that there were some discussions about provenance and subobjects. I do not know whether the question is resolved.
Where this gets complicated is that zero-sized arrays are non-standard. So even if we could build a convincing argument from standard notions of provenance, how would it transfer to a subobject that is excluded from the standard?
Last but not least, this is not only about creating the effective type through memcpy. The question is also whether this destroys the effective type of the structure. See my previous point about possible padding after 'payload'.
Please also consider that flexible array members are here for a reason. If I follow your argument, then they bring nothing that arrays of length 0 or 1 do not already cover.
If payload was ever dereferenced as a char array as well, I would buy the strict aliasing argument. But it’s not, it exists as a char pointer solely for pointer arithmetic.
AFAIK The purpose of strict aliasing rules is to let the compiler assume that dereferencing pointers of different types never refer to the same memory.
If ISO C treats this as UB, shouldn’t ISO C be fixed?
I’m not chasing theoretical portability and checking off a box saying my code is 100% pure ISO C. If that’s important to you, don’t do this (and also don’t use pretty much any allocator!)
Every sufficiently useful C codebase assumes specific implementations.
In practice you wouldn’t have the payload in the struct at all, just a fixed offset aligned with the maximum alignment, but this is more illustrative of what’s happening for an example.
IIRC GCC and Clang lets character types alias to any type. Otherwise glibc’s malloc also doesn’t abide to strict aliasing.
IIRC GCC and Clang lets character types alias to any type.
It is always legal to access the memory representation of any object as an array of characters. The other way around (interpreting an array of characters as a T, even though it does not have effective type T) is not.
Otherwise glibc’s malloc also doesn’t abide to strict aliasing.
It may not have to. From the point of view of C, malloc is special because it is part of the implementation. The compiler is free to handle UB as it sees fit. In particular, it can decide that aliasing has different semantics in malloc.c than outside it.
It is awkward in C, where the implementation has to be macro-generated
I assume this is why they are putting the list pointer and payload in separate structs and doing pointer math to access the payload, so that it’s easy to build a set of macros that act like a generic list class for building lists out of any payload, right?
One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections
Wait - how does this work? If I do address math on the pointer in order to find a payload, then isn’t the payload tied into exactly one next pointer, and thus exactly one list? For a minute I thought maybe this is why they put the pointer after the payload, but now I don’t see how to use a payload in more than one list, nor why they use subtract on the list pointer to find the payload instead of putting the list in front of the payload and adding (or using a type-cast pointer for direct access).
the defining property of intrusive data structures is that they leave the responsibility of allocating elements to the user.
Indeed! This is why you see them in OS’s, in memory managers, and in embedded systems. We used to use them all the time in console video games before dynamic memory and heap allocations were common (or even allowed). Use of STL wasn’t allowed. Often the memory needed would be pre-allocated, and lists would be created and managed at run time without allocation, just by wiring up the pointers. Similar to what a memory manager has to do.
This was in C++, but back when (and before) EASTL was popular. EASTL was EA’s version of the STL without built-in heap allocation for container classes. We usually built payload classes with the list next pointer placed directly in the payload, and essentially did the list management as a one-off separately for each payload, because it was typically only a few lines of code and there weren’t enough list types for it to be a problem. This is the kind of intrusive list I’ve seen the most of, hence the questions about the particular C flavor shown here.
Ah yes if all collections are explicitly listed in the list node type, that makes sense. I thought the suggestion was that you could somehow link any given payload entry into multiple independent lists each with their own list node type.
struct thread {
// Entry in the list of threads of the containing process
list_node process_entry;
// Entry in this thread's scheduling queue
list_node sched_entry;
// ...
};
Each struct thread is linked in two lists. When we need to get from a list_node * to the enclosing struct thread, we know from the context which list is being inspected, so we know which one of process_entry or sched_entry to consider for offsetting the pointer.
This is easy to do with the proper support for monomorphized generics, see C++'s std::list. It is awkward in C, where the implementation has to be macro-generated.
Fairly pleasant in Zig, through abuse of @fieldParentPointer and a pinch of comptime.
It was a little nicer in the `usingnamespace` days. So it goes.
The elements can be allocated on the heap, on the stack, in a global array (like "initholes" in the article), in a special arena, etc.
An "etc" worth mentioning specifically is a memory pool: they're useful for any same-sized struct which gets recycled a lot, but for linked lists there are further advantages. You don't have to cast the object to bytes and declare a link pointer, since it already has one: not really an advantage, casting is free, but: if you can arrange to give both sides of the list back, then recycling can be done on a per-list level by prepending the whole thing to the freelist.
I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version. The issue is more than there is no standardized version directly available except perhaps the old BSD ones and those are not ideal. I agree with the rest of your comment.
I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version.
I have some experience with this, and while this is one of these things that are feasible, I find them significantly inferior to templates in practice.
For one thing, footguns are everywhere in C macro-based metaprogramming. E.g. do not declare the payload as 'payload_type payload;' in the node structure, but choose 'typeof(payload_type) payload;' instead, as someone may pass an array type or function pointer type for 'payload_type'. Speaking of array types, how do you deal with the fact that you cannot pass them by value? I will choose C++ templates' semantic substitution over C macros' textual substitution.
Anyway, to me, the biggest limitation of macro-generation compared to templates is that there is no centralized monomorphization. If an application uses two libraries, each of which handles lists of int, each library will have to independently macro-generate its separate list implementation, and because C's type system is nominal, the generated types will be isomorphic but incompatible. Contrast this with C++ templates, where two independent libraries can happily share std::list<int> values.
You are right that it is not perfect, but it is fine for me and usability is not worse than for C++. I use the rule that only identifiers (typedef names) can be passed. Then the macro can synthesize a tag and list type is then compatible between different libraries.
The predeclarations are not needed anymore in C23 and I hope for the next version of C we can also get rid of the limitation that an identifier needs to be passed to the macro (by making the type system fully structural).
If an application uses two libraries, each of which handles lists of int, each library will have to independently macro-generate its separate list implementation, and because C's type system is nominal, the generated types will be isomorphic but incompatible.
Um, what? C89, 3.1.2.6: "Moreover, two structure, union, or enumeration types declared in separate translation units are compatible if they have the same number of members, the same member names, and compatible member types; for two structures, the members shall be in the same order".
There has been some minor changes over the years, but as long as the struct tags are the same, and the fields are in the same order and have compatible types, the two structs defined in separate compilation units are compatible.
Exactly. Now you have a naming problem. You need a naming convention that every user of the list library must follow, or else their types will be incompatible. And what about typedefs? If A is a typedef of B, or more generally A and B are typedef-related (their normal forms, obtained by following all typedefs, are the same), lists of A and B will be incompatible unless users agree on a common name. The only realistic choice is the normal form, but then this actively works against the abstraction provided by typedef.
And this is just for types. What about functions? While it is legal to do identical definitions of struct list_int, it is not for list_int_init() and list_int_add(). Or global variables: it is legal to do several identical extern declarations, but there can only be one definition; which compilation unit gets to do it?
Now you have a naming problem. You need a naming convention that every user of the list library must follow, or else their types will be incompatible.
Oh, that's simple: just have empty struct tags.
And what about typedefs?
The names introduced by the typedefs are irrelevant.
A and B are typedef-related (their normal forms, obtained by following all typedefs, are the same), lists of A and B will be incompatible unless users agree on a common name.
Huh?
typedef struct { int x; } A;
typedef struct { int x; } B;
typedef struct { header_list header; A payload; } list_of_A;
typedef struct { header_list header; B payload; } list_of_B;
The structs list_of_A and list_of_B are compatible.
Wait, seriously? They are unique, sure, but the 6.2.7.1 quite explicitly states they are compatible as long as they're in separate files:
Moreover, two structure,
union, or enumerated types declared in separate translation units are compatible if their
tags and members satisfy the following requirements: If one is declared with a tag, the
other shall be declared with the same tag. If both are completed anywhere within their
respective translation units, then the following additional requirements apply: there shall
be a one-to-one correspondence between their members such that each pair of
corresponding members are declared with compatible types; if one member of the pair is
declared with an alignment specifier, the other is declared with an equivalent alignment
specifier; and if one member of the pair is declared with a name, the other is declared
with the same name. For two structures, corresponding members shall be declared in the
same order. For two structures or unions, corresponding bit-fields shall have the same
widths. For two enumerations, corresponding members shall have the same values.
No, you are right, but it is not "in separate files" but "translation units". Two distinct list(int) from two different libraries need to be compatible when used together, which means you would include the header of those two libraries and then both end up in the same translation unit.
C23 relaxed requirements for types with tag, this works for structures with tag, but for type generic structures you then need to synthesize a tag that depends on the type, e.g. list_int, list_float, etc.. so that differently parametrized types do not collide. This works quite well in practice, but is not perfect.
I don't think that's the scenario the other commenter was talking about:
there is no centralized monomorphization. If an application uses two libraries, each of which handles lists of int, each library will have to independently macro-generate its separate list implementation, and because C's type system is nominal, the generated types will be isomorphic but incompatible.
So, lib_a.c includes header_only_list.h, and lib_b.c also includes the same header_only_list.h, but they can't they pass the list structures between each other because those structs would be incompatible even though they're textually identical ("the generated types will be isomorphic but incompatible"). To which I replied that no, they would not, no C program would be able to work if this were true.
Otherwise, the mentioning of monomorphization doesn't make any sense: of course two completely different implementations of lists will be incompatible.
But "the generated types will be isomorphic but incompatible" is right. It is ok if you have lib_a.c and lib_b.c because these are two separate translation units. But this only works if both of these libraries use the list type internally and pass the pointer to each other as a void pointer. The moment you have two headers lib_a.h lib_b.h both including header_only_list.h and defining an API using a generic type list(int) and where you then try to also include lib_b.h from lib_a.c it does not work.
The structs list_of_A and list_of_B are compatible.
No, they are not. From C23, 6.7.3.4 Tags: Each declaration of a structure, union, or enumerated type which does not include a tag declares a distinct type.
We mean compatible as defined by the C language standard. It is much more restrictive than having the same layout. In particular, you may not pass a pointer to a type where a pointer to an incompatible type is expected, even if the types have the same layout, which prevents the sort of sharing between two libraries that is being discussed.
Moreover, there is no guarantee that two distinct structure types with the same list of members have the same size or alignment (although in practice they do). The members must nevertheless be laid out in the same way (same offsets, and in the case of bit-fields, same layout inside storage units) due to an obscure constraint on common initial sequences. So the layouts of the structures may differ in the alignment requirement and the amount of trailing padding.
Furthermore, two structure, union, or enumerated types declared in separate translation units are
compatible in the following cases:
— both are declared without tags and they fulfill the preceding requirements;
the preceding requirements being
— there shall be a one-to-one correspondence between their members such that each pair of
corresponding members are declared with compatible types;
— if one member of the pair is declared with an alignment specifier, the other is declared with an
equivalent alignment specifier;
— and, if one member of the pair is declared with a name, the other is declared with the same
name.
For two structures, corresponding members shall be declared in the same order. For two unions
declared in the same translation unit, corresponding members shall be declared in the same order. For
two structures or unions, corresponding bit-fields shall have the same widths. For two enumerations,
corresponding members shall have the same values; if one has a fixed underlying type, then the
other shall have a compatible fixed underlying type. For determining type compatibility, anonymous
structures and unions are considered a regular member of the containing structure or union type,
and the type of an anonymous structure or union is considered compatible with the type of another
anonymous structure or union, respectively, if their members fulfill the preceding requirements.
Seems to me that those two structs satisfy all of those requirements, so they're compatible. Otherwise, struct declarations in the header files would've been completely useless from the very beginning.
One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections
My example here from the top of my head are intrusive heaps, which are provide a neat way of implementing A*. Here you combine a HashMap and a Heap (over a Vec) where the Heap has the data, and the HashMap maps SearchNodeId to Heap indices.
This allows O(1) lookups by search node Id into the Heap (as opposed to a linear scan) despite elements in the heap being constantly shuffled around as search nodes enter and leave the heap.
I'm sure that using HashMaps as a parallel index to other collections can be useful in other scenarios, but I don't know if combination of other data structures works this well, the synchronisation cost might not be worth it.
I was surprised to see the main benefit of intrusive linking mentioned as a bit of a side note: The ability to move data around between lists (and within a list) without copying. You also get O(1) removal from the middle of the list, assuming you have a pointer to the object somewhere else. As a result, when you have large state structs and you don't do a lot of list scans, intrusive linking makes things a lot faster than use of packed structures like vectors.
Data is generally read more often than written and data is read in locally spatial way.
That’s why having elements laid out next to one another is often more important than the algorithmic complexity of occasionally doing an O(n) or O(n log n) operation updating the layout.
It’s not always the case of course but it is the case more often than you’d think.
You can do this with non intrusive lists too. See c++’s merge/splice/etc. You can store the iterators in some other place as you do this, making it quite handy on occasion.
I'm pretty sure the author there means to compare the intrusive linked list to a non-intrusive linked list (such as C++ std::list), not to vectors etc. that aren't "linked" at all. As described e.g. in https://news.ycombinator.com/item?id=49549542 .
Hmm interesting, the doubly linked list presented here is missing the elegant 'overlapped list header' trick from AmigaOS (at least that's where I saw it first):
E.g. an AmigaOS list node looks conventional, it has two pointers, one to the next node (succ), and one to the previous node (pred):
In an empty list, lh_Head points to &lh_Tail, and lh_TailPred points to &lh_Head. The lh_Tail pointer is always null (this is the 'end marker').
In a populated list, lh_Head points to the embedded Node struct of the first list node, and lh_TailPred points to the embedded Node struct of the last list node. The ln_Succ pointer of the last node points to the address of the list header's lh_Tail pointer (...which is always null).
That way you only need an existing node pointer to walk forward and backward, or insert or remove a node. When walking the list by following the succ or pred pointers you know you've reached the end when encountering a null pointer.
Apparently the Linux-style lists in the article require to know the address of the list header to detect when the end is reached which isn't needed for the Amiga style list (at the cost of an additional 'sentinel null pointer' in the list header).
Pretty much all of AmigaOS was held together by such doubly linked lists.
(I hope I got that all right, it's been a long time)
When did you last encounter or use a linked list ? :)
Linked lists fell out of fashion once the cpu/memory latency gap opened up towards the end of the 1990s. For most use cases it's simply better to use a tightly packed array, even use cases where linked lists would intuitively make more sense.
Every day, all day. It is a myth that linked lists fell out of fashion.
Of course, "it depends". There are things that better live in tightly-packed arrays (large lists of free-standing objects), but there are things that are almost impossible without linked lists. In these cases, being "intrusive" has massive advantages.
I guess you can spend an entire coder career without having to use linked lists, and then you cannot imagine why anybody would ever use them (and make it a meme). The linked lists that do exist in your programs may be abstracted away from your visibility.
Therefore: sure, an article about linked lists will spawn numerous HN comments from such coders who don't know the shoulders they're standing on. It's linked lists all the way down... below the flat surface of high-level frameworks.
Anything where you use a state machine that has to remember the parent state is effectively an intrusive linked list (even if they rarely have more than two elements); similarly the most obvious implementation of undo/redo. In these uses it's less complex and more understandable than having an explicit container, and constant-factor performance is irrelevant since we're talking about spending a few clock cycles to retrieve information in response to a human-speed GUI interaction.
You might also note that TFA is much more recent than "the end of the 1990s" and describes one of the most important software systems out there, which to the best of my knowledge still uses these techniques in the same way.
Mutating a std::vector is much more difficult because you need a coarse lock and serialize every access with it - there's no other option. Linked lists, on the other hand, can be made thread-safe with a single coarse lock, or many finer-grained locks, or atomics, or fancier tricks like RCU.
All of that is difficult, sure, but what is less difficult than thread-safe linked lists?
Difficult to do thread-safely and lock-less-ly. An atomic compare-and-swap operation can be used to build lock-less, thread-safe singly-linked list. Doing that for doubly-linked lists is harder.
Another benefit the article doesn't mention: these intrusive lists seem a good soft defense against use-after-free bugs in C. The node struct knows about all containers to which it belongs, so writing the "destructor" is very local. With the pointer array equivalent, one can only identify the arrays that point to the object by understanding the surrounding codebase.
(Disclaimer: I am not speaking from experience here. My C background is mostly static allocation.)
Not more than regular collections (unless you mean working on different parts with different threads, then it's still possible but harder, just like with regular collections).
I googled it and got the response that Bjarne Stroustrup first used “intrusive” in his 1985 C++ book. He was adding a new distinction between the older intrusive kind and the new ‘non-intrusive’ kind, because some people had started using C++ to allocate the list nodes and the payload structs separately.
Now with std::list and college classes often teaching non-intrusive linked lists, and intrusive lists only being used in deep dark places like the OS kernel, maybe it’s easy to assume the ‘regular’ kind is non-intrusive.
What Stroustrup called ‘intrusive’ had been the default understanding of linked lists since around 1955, and what people used most often. A ‘regular’ linked list to most people back then was the intrusive kind, and the term ‘non-intrusive’ might have been an attempt to sell people on the benefits of abstracting and separating node types from payloads, but that maybe papers over the disadvantages a little.
The only kind of linked list I’ve ever used in my professional career is the intrusive kind. There are very few good reasons to ever use non-intrusive lists outside of the classroom. At least, not if you care about performance at all. They might be convenient & easy, but it’s usually the case that either an array or an intrusive list would be a better engineering choice.
benefits of abstracting and separating node types from payloads
If you mean being able to a generic `list<foo>` type (whether by C++ templates, macros, or good old void* casts), it's more than that.
The benefit of non-intrusive is being able to create/manipulate/pass around multiple collections pointing to same payloads, without disturbing the payloads or the other collections in any way¹. That makes it easier to return and manipulate collections functionally (both in the narrow immutable sense, but also in the wider "treat collections like _values_ sense)... The deepest benefit arising from that I suppose is code modularity: different code areas need not be aware of each other's existence.
That all obviously comes at some tradeoff to performance. By definition, not having a full picture of the pathways your data travels means you can't choose the fastest representation!
¹The cheat is GC. For multiple unconnected collections to point to same payload, you need ref counting, or mark&sweep or similar to control its lifetime. Technically, GC does disturb the objects it's tracking (though that's well abstracted from other code).
However, you're largely right that specifically linked lists are rarely a good choice for non-intrusive collections => Arrays usually beat them, and if not then hash sets.
(LISP & ML & Haskell do stick to lists for tail sharing — a choice which is arguably outdated by growing CPU / mem random access gap. I suppose Clojure's persistent vectors are an improvement.)
It really depends on the ecosystem you’re working in. For a good while, most developers have been working with managed runtimes, where “non-intrusive” linked lists are generally the default and “intrusive” linked lists correspondingly rare.
(Actually, in many cases arrays are the default (like ArrayList in Java), because lists tend to only get assembled once and then passed around without further modification.)
"Intrusive" may be a C++ speak, but I wouldn't say that one or the other type of lists is necessarily much older or more "normal". After all, a cons cell embeds data and not the other way around and lisp is one of the oldest programming languages in existence
Back in the day what is being called out here as an "intrusive" linked list was just a linked list, since you didn't have the luxury of having memory and CPU cycles to waste with extra allocations and indirection.
In the C++ world the STL introduced generic data types such as linked lists, which became the default, but "instrusive" linked lists still have their place in specialized list-heavy use cases where performance matters. In a previous job I wrote a widely adopted XML/JSON library using instrusive lists to link child elements, and the performance benefit was considerable, with my DOM API basically hiding this implementation detail from the user.
You have it backwards, an intrusive linked list is a linked list that is embedded in another data structure. The classic example is a linked list whose elements live on the stack.
The article is wrong too, or at least using the term over-specifically.
GP points out that what the article calls "intrusive linked list" is a regular linked list. Wikipedia for instance gives the canonical linked list example of a struct with one embedded integer and a next link and of course does not call it "intrusive linked list".
"Intrusive" got popular with C++ intrusive pointers, and that is where the article gets is misinformation from.
And of coursed the web jockeys downvote the correct objection since they have no clue about data structures, history, logic or basic reading skills.
"Intrusive" got popular with C++ intrusive pointers
It got popular with C++'s attempts at type safety. In particular, std::list lets you accomplish the machinery without macros, and allowing for polymorphism (heterogeneous lists of derived instances) without weird type casts and overallocation tricks, but at the cost of another level of indirection.
I came to this relatively late (2013-ish, windows kernel development, scouring OSDev, etc) so I thought that was always the right name for them. Prior experience was mostly... higher-level langs.
I concur. I recall being a student and when implementing LL for the first time, you did it this way (mix your data and ptr to next node). It is baby's first linked list.
Comments
The go a bit further than the article on the advantages of intrusive data structures, taking linked lists as an example:
As the article mentions, intrusive data structures naturally lead to one fewer indirection. To do the same with a traditional list (where the list node owns the payload), a different node type is needed for each payload type. This is easy to do with the proper support for monomorphized generics, see C++'s std::list. It is awkward in C, where the implementation has to be macro-generated. C naturally pushes towards an indirection through void *, which makes intrusive lists more attractive.
One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections (where traditional collections would require e.g. one collection owning the payloads, and the other collections merely holding non-owning pointers to them).
Las but not least, the defining property of intrusive data structures is that they leave the responsibility of allocating the elements to the user. The elements can be allocated on the heap, on the stack, in a global array (like "initholes" in the article), in a special arena, etc. It is even reasonable to use non-uniform allocation strategies; for example, for a circular list, allocate an anchor node on the stack and the other nodes (those embedded in payloads) on the heap.
You can avoid having the implementation be macro-generated by "hiding" the list pointers before a char payload[0]. See https://pastebin.com/DE69mbJD for an example.
The same technique is used by glibc's malloc to store metadata about the allocation right next to your data, and then recover it when you call realloc/free, without needing a separate metadata allocation.
The caveat is that the type of the pointer does not indicate provenance. For example, nothing stops you from calling list_next on an arbitrary pointer to data that is not on a list, and that would be UB. The same happens with realloc and free, where it's UB if you pass them a pointer that was not returned by the heap allocator.
Zero-sized arrays are not standard. Accessing an array out of bounds is UB. At the very least, you should use a flexible array member instead (char payload[];).
But even if you did that, strict aliasing implies that 'payload' can only be accessed as an array of character type. It is correct to memcpy between 'payload' and another object of arbitrary type T of the appropriate size (as list_push_ does in your example), but it is UB to access 'payload' in place as a T (as main does, by casting to struct point * and dereferencing). Oh, and 'payload' may not satisfy the alignment requirement of T.
There is no realistic strict-aliasing-abiding way around a distinct node type per payload type.
There is no OoB access of an array; the calculated pointer is pointing to the payload object that's residing in the malloc-returned storage right after the node struct.
I think the actual problem is the alignment; that malloc-returned storage simply can't have enough space to hold a "struct { struct node header; PAYLOAD_TYPE payload; }" (which is what the parent comment is trying to emulate) if the payload type has an alignment that's greater than the size of a pointer, and that pointer will be pointing at what would've been the padding in that struct.
Yes, there is. It does not matter that storage happens to be allocated beyond the end of said array. Strict aliasing implies that it is UB to reinterpret the array as anything else. And it is UB to access an array out of bounds.
Flexible array members specifically exist for these dynamically-allocated trailing arrays. They do not solve the strict aliasing problem, though.
The amount of padding is implementation-defined. The only portable guarantee is that 'payload' is aligned for its element type, char. To over-align, use _Alignas, as in:
It does matter, for malloc-returned storage. You can put whatever objects you want into that storage as long as it fits and the pointer is properly aligned.
...is not violated; memcpy takes a void pointer as its destination, sets the effective type of the storage behind it, and the treats it as an array of unsigned chars.
You can certainly store an object of arbitrary type, but here it is done through a pointer to an object with pointer arithmetic going beyond the allowed bounds.
And, in doing so, may very well overwrite the unspecified padding following 'payload' in the structure, thus instantly destroying the effective type of the structure object itself. Subsequent accesses to the structure or its members will be UB.
It seems to me that your argument hinges on two assumptions:
That is a very interesting discussion.When you do "void *x = malloc(sizeof(struct node))", the returned storage doesn't have struct node object in it, it has an object of no effective type in it, with size "sizeof(struct node)". Taking the pointer to payload[] field is in no way different from doing "(char*) x + offsetof(struct node, payload)" — it takes a char pointer into the object storage, adds a number (less than the object's size) and so produces another char pointer that points somewhere inside into the object storage — and no, since there has been no actual referencing of the object's value, constructing such a pointer does not set the effective type of that object; and a char pointer is explicitly allowed to alias whatever storage. Then the memcpy sets the effective type, done. No UB anywhere.
It may differ, depending on the precise notion of provenance being applicable. If provenance only has allocation granularity, I suppose that there is no difference. I know that there were some discussions about provenance and subobjects. I do not know whether the question is resolved.
Where this gets complicated is that zero-sized arrays are non-standard. So even if we could build a convincing argument from standard notions of provenance, how would it transfer to a subobject that is excluded from the standard?
Last but not least, this is not only about creating the effective type through memcpy. The question is also whether this destroys the effective type of the structure. See my previous point about possible padding after 'payload'.
Please also consider that flexible array members are here for a reason. If I follow your argument, then they bring nothing that arrays of length 0 or 1 do not already cover.
If payload was ever dereferenced as a char array as well, I would buy the strict aliasing argument. But it’s not, it exists as a char pointer solely for pointer arithmetic.
AFAIK The purpose of strict aliasing rules is to let the compiler assume that dereferencing pointers of different types never refer to the same memory.
If ISO C treats this as UB, shouldn’t ISO C be fixed?
No, you should fix your code to be compliant with ISO C. The optimizer isn’t going to wait for you to convince WG14.
I’m not chasing theoretical portability and checking off a box saying my code is 100% pure ISO C. If that’s important to you, don’t do this (and also don’t use pretty much any allocator!)
Every sufficiently useful C codebase assumes specific implementations.
In practice you wouldn’t have the payload in the struct at all, just a fixed offset aligned with the maximum alignment, but this is more illustrative of what’s happening for an example.
IIRC GCC and Clang lets character types alias to any type. Otherwise glibc’s malloc also doesn’t abide to strict aliasing.
It is always legal to access the memory representation of any object as an array of characters. The other way around (interpreting an array of characters as a T, even though it does not have effective type T) is not.
It may not have to. From the point of view of C, malloc is special because it is part of the implementation. The compiler is free to handle UB as it sees fit. In particular, it can decide that aliasing has different semantics in malloc.c than outside it.
I'm curious, what would be the point of having a zero-sized array if you can't access it?
I assume this is why they are putting the list pointer and payload in separate structs and doing pointer math to access the payload, so that it’s easy to build a set of macros that act like a generic list class for building lists out of any payload, right?
Wait - how does this work? If I do address math on the pointer in order to find a payload, then isn’t the payload tied into exactly one next pointer, and thus exactly one list? For a minute I thought maybe this is why they put the pointer after the payload, but now I don’t see how to use a payload in more than one list, nor why they use subtract on the list pointer to find the payload instead of putting the list in front of the payload and adding (or using a type-cast pointer for direct access).
Indeed! This is why you see them in OS’s, in memory managers, and in embedded systems. We used to use them all the time in console video games before dynamic memory and heap allocations were common (or even allowed). Use of STL wasn’t allowed. Often the memory needed would be pre-allocated, and lists would be created and managed at run time without allocation, just by wiring up the pointers. Similar to what a memory manager has to do.
This was in C++, but back when (and before) EASTL was popular. EASTL was EA’s version of the STL without built-in heap allocation for container classes. We usually built payload classes with the list next pointer placed directly in the payload, and essentially did the list management as a one-off separately for each payload, because it was typically only a few lines of code and there weren’t enough list types for it to be a problem. This is the kind of intrusive list I’ve seen the most of, hence the questions about the particular C flavor shown here.
The container_of macro takes the type and member - so for a different member it can subtract a different offset.
Going more basic, you could imagine creating something like:
The normal, 10ths, and 100ths lists are distinct collections, this is the basic idea. The macros just help generalise it and make it more usable.Ah yes if all collections are explicitly listed in the list node type, that makes sense. I thought the suggestion was that you could somehow link any given payload entry into multiple independent lists each with their own list node type.
Like this:
Each struct thread is linked in two lists. When we need to get from a list_node * to the enclosing struct thread, we know from the context which list is being inspected, so we know which one of process_entry or sched_entry to consider for offsetting the pointer.Fairly pleasant in Zig, through abuse of @fieldParentPointer and a pinch of comptime.
https://github.com/mnemnion/zelda
It was a little nicer in the `usingnamespace` days. So it goes.
An "etc" worth mentioning specifically is a memory pool: they're useful for any same-sized struct which gets recycled a lot, but for linked lists there are further advantages. You don't have to cast the object to bytes and declare a link pointer, since it already has one: not really an advantage, casting is free, but: if you can arrange to give both sides of the list back, then recycling can be done on a per-list level by prepending the whole thing to the freelist.
I do not think a type-safe macro-generated list in C is any more awkward to implement or inferior to a C++ template version. The issue is more than there is no standardized version directly available except perhaps the old BSD ones and those are not ideal. I agree with the rest of your comment.
I have some experience with this, and while this is one of these things that are feasible, I find them significantly inferior to templates in practice.
For one thing, footguns are everywhere in C macro-based metaprogramming. E.g. do not declare the payload as 'payload_type payload;' in the node structure, but choose 'typeof(payload_type) payload;' instead, as someone may pass an array type or function pointer type for 'payload_type'. Speaking of array types, how do you deal with the fact that you cannot pass them by value? I will choose C++ templates' semantic substitution over C macros' textual substitution.
Anyway, to me, the biggest limitation of macro-generation compared to templates is that there is no centralized monomorphization. If an application uses two libraries, each of which handles lists of int, each library will have to independently macro-generate its separate list implementation, and because C's type system is nominal, the generated types will be isomorphic but incompatible. Contrast this with C++ templates, where two independent libraries can happily share std::list<int> values.
You are right that it is not perfect, but it is fine for me and usability is not worse than for C++. I use the rule that only identifiers (typedef names) can be passed. Then the macro can synthesize a tag and list type is then compatible between different libraries.
It could look like this: https://codeberg.org/uecker/noplate/src/branch/main/tests/li...
The predeclarations are not needed anymore in C23 and I hope for the next version of C we can also get rid of the limitation that an identifier needs to be passed to the macro (by making the type system fully structural).
Um, what? C89, 3.1.2.6: "Moreover, two structure, union, or enumeration types declared in separate translation units are compatible if they have the same number of members, the same member names, and compatible member types; for two structures, the members shall be in the same order".
There has been some minor changes over the years, but as long as the struct tags are the same, and the fields are in the same order and have compatible types, the two structs defined in separate compilation units are compatible.
Exactly. Now you have a naming problem. You need a naming convention that every user of the list library must follow, or else their types will be incompatible. And what about typedefs? If A is a typedef of B, or more generally A and B are typedef-related (their normal forms, obtained by following all typedefs, are the same), lists of A and B will be incompatible unless users agree on a common name. The only realistic choice is the normal form, but then this actively works against the abstraction provided by typedef.
And this is just for types. What about functions? While it is legal to do identical definitions of struct list_int, it is not for list_int_init() and list_int_add(). Or global variables: it is legal to do several identical extern declarations, but there can only be one definition; which compilation unit gets to do it?
Oh, that's simple: just have empty struct tags.
The names introduced by the typedefs are irrelevant.
Huh?
The structs list_of_A and list_of_B are compatible.No, any tagless type is unique, so neither A and B nor list_of_A and list_of_B are compatible.
This is what I like to fix in C2y outside of typedefs (and it would really help if you file wishlist bugs with compilers if you agree).
Wait, seriously? They are unique, sure, but the 6.2.7.1 quite explicitly states they are compatible as long as they're in separate files:
Did C23 tighten the requirements?No, you are right, but it is not "in separate files" but "translation units". Two distinct list(int) from two different libraries need to be compatible when used together, which means you would include the header of those two libraries and then both end up in the same translation unit.
C23 relaxed requirements for types with tag, this works for structures with tag, but for type generic structures you then need to synthesize a tag that depends on the type, e.g. list_int, list_float, etc.. so that differently parametrized types do not collide. This works quite well in practice, but is not perfect.
I don't think that's the scenario the other commenter was talking about:
So, lib_a.c includes header_only_list.h, and lib_b.c also includes the same header_only_list.h, but they can't they pass the list structures between each other because those structs would be incompatible even though they're textually identical ("the generated types will be isomorphic but incompatible"). To which I replied that no, they would not, no C program would be able to work if this were true.
Otherwise, the mentioning of monomorphization doesn't make any sense: of course two completely different implementations of lists will be incompatible.
But "the generated types will be isomorphic but incompatible" is right. It is ok if you have lib_a.c and lib_b.c because these are two separate translation units. But this only works if both of these libraries use the list type internally and pass the pointer to each other as a void pointer. The moment you have two headers lib_a.h lib_b.h both including header_only_list.h and defining an API using a generic type list(int) and where you then try to also include lib_b.h from lib_a.c it does not work.
No, they are not. From C23, 6.7.3.4 Tags: Each declaration of a structure, union, or enumerated type which does not include a tag declares a distinct type.
It depends what is meant by "compatible." Is the memory layout the same? Yes. Can I memcpy between them? Yes...
We mean compatible as defined by the C language standard. It is much more restrictive than having the same layout. In particular, you may not pass a pointer to a type where a pointer to an incompatible type is expected, even if the types have the same layout, which prevents the sort of sharing between two libraries that is being discussed.
Moreover, there is no guarantee that two distinct structure types with the same list of members have the same size or alignment (although in practice they do). The members must nevertheless be laid out in the same way (same offsets, and in the case of bit-fields, same layout inside storage units) due to an obscure constraint on common initial sequences. So the layouts of the structures may differ in the alignment requirement and the amount of trailing padding.
Now if I include both library headers in code that attempts to plug them together, the types will be incompatible.
Although not a proof in itself, GCC and Clang seem to agree: https://godbolt.org/z/1ocr5Go5b.
Yes, I figured that's what you meant... I wasn't sure about the other guy.
My example here from the top of my head are intrusive heaps, which are provide a neat way of implementing A*. Here you combine a HashMap and a Heap (over a Vec) where the Heap has the data, and the HashMap maps SearchNodeId to Heap indices. This allows O(1) lookups by search node Id into the Heap (as opposed to a linear scan) despite elements in the heap being constantly shuffled around as search nodes enter and leave the heap.
I'm sure that using HashMaps as a parallel index to other collections can be useful in other scenarios, but I don't know if combination of other data structures works this well, the synchronisation cost might not be worth it.
The C macro systems never last. Just write it! It’s no harder than a for loop.
I was surprised to see the main benefit of intrusive linking mentioned as a bit of a side note: The ability to move data around between lists (and within a list) without copying. You also get O(1) removal from the middle of the list, assuming you have a pointer to the object somewhere else. As a result, when you have large state structs and you don't do a lot of list scans, intrusive linking makes things a lot faster than use of packed structures like vectors.
Data is generally read more often than written and data is read in locally spatial way.
That’s why having elements laid out next to one another is often more important than the algorithmic complexity of occasionally doing an O(n) or O(n log n) operation updating the layout.
It’s not always the case of course but it is the case more often than you’d think.
The main benefit is that adding/removing items to/from a list requires no heap operations. All control elements are basically preallocated.
You can do this with non intrusive lists too. See c++’s merge/splice/etc. You can store the iterators in some other place as you do this, making it quite handy on occasion.
I'm pretty sure the author there means to compare the intrusive linked list to a non-intrusive linked list (such as C++ std::list), not to vectors etc. that aren't "linked" at all. As described e.g. in https://news.ycombinator.com/item?id=49549542 .
Hmm interesting, the doubly linked list presented here is missing the elegant 'overlapped list header' trick from AmigaOS (at least that's where I saw it first):
E.g. an AmigaOS list node looks conventional, it has two pointers, one to the next node (succ), and one to the previous node (pred):
Most AmigaOS structs embed such a Node struct at the start....but the list header has three pointers which basically form two overlapped Node structs:
In an empty list, lh_Head points to &lh_Tail, and lh_TailPred points to &lh_Head. The lh_Tail pointer is always null (this is the 'end marker').In a populated list, lh_Head points to the embedded Node struct of the first list node, and lh_TailPred points to the embedded Node struct of the last list node. The ln_Succ pointer of the last node points to the address of the list header's lh_Tail pointer (...which is always null).
That way you only need an existing node pointer to walk forward and backward, or insert or remove a node. When walking the list by following the succ or pred pointers you know you've reached the end when encountering a null pointer.
Apparently the Linux-style lists in the article require to know the address of the list header to detect when the end is reached which isn't needed for the Amiga style list (at the cost of an additional 'sentinel null pointer' in the list header).
Pretty much all of AmigaOS was held together by such doubly linked lists.
(I hope I got that all right, it's been a long time)
This looks correct, here is a reference: https://wiki.amigaos.net/wiki/Exec_Lists_and_Queues#List_Hea....
Is this sort of thing no longer part of a standard computer science or software engineering undergrad curriculum?
When did you last encounter or use a linked list ? :)
Linked lists fell out of fashion once the cpu/memory latency gap opened up towards the end of the 1990s. For most use cases it's simply better to use a tightly packed array, even use cases where linked lists would intuitively make more sense.
Every day, all day. It is a myth that linked lists fell out of fashion.
Of course, "it depends". There are things that better live in tightly-packed arrays (large lists of free-standing objects), but there are things that are almost impossible without linked lists. In these cases, being "intrusive" has massive advantages.
I guess you can spend an entire coder career without having to use linked lists, and then you cannot imagine why anybody would ever use them (and make it a meme). The linked lists that do exist in your programs may be abstracted away from your visibility.
Therefore: sure, an article about linked lists will spawn numerous HN comments from such coders who don't know the shoulders they're standing on. It's linked lists all the way down... below the flat surface of high-level frameworks.
Anything where you use a state machine that has to remember the parent state is effectively an intrusive linked list (even if they rarely have more than two elements); similarly the most obvious implementation of undo/redo. In these uses it's less complex and more understandable than having an explicit container, and constant-factor performance is irrelevant since we're talking about spending a few clock cycles to retrieve information in response to a human-speed GUI interaction.
You might also note that TFA is much more recent than "the end of the 1990s" and describes one of the most important software systems out there, which to the best of my knowledge still uses these techniques in the same way.
Doubly-linked lists -all data structures that have back pointers- are really difficult to mutate thread-safely.
Difficult compared to what?
Mutating a std::vector is much more difficult because you need a coarse lock and serialize every access with it - there's no other option. Linked lists, on the other hand, can be made thread-safe with a single coarse lock, or many finer-grained locks, or atomics, or fancier tricks like RCU.
All of that is difficult, sure, but what is less difficult than thread-safe linked lists?
Difficult to do thread-safely and lock-less-ly. An atomic compare-and-swap operation can be used to build lock-less, thread-safe singly-linked list. Doing that for doubly-linked lists is harder.
Waiter, waiter! More optimization articles without benchmarks, please!
Another benefit the article doesn't mention: these intrusive lists seem a good soft defense against use-after-free bugs in C. The node struct knows about all containers to which it belongs, so writing the "destructor" is very local. With the pointer array equivalent, one can only identify the arrays that point to the object by understanding the surrounding codebase.
(Disclaimer: I am not speaking from experience here. My C background is mostly static allocation.)
Now try to do them in safe Rust.
Easy. https://docs.rs/intrusive-collections.
The issue is that back-links in data structures are inherently difficult to handle a thread-safe way in mutators.
Not more than regular collections (unless you mean working on different parts with different threads, then it's still possible but harder, just like with regular collections).
Importing a library does not count. (Besides, perhaps you can tell but I don't even know if the library uses safe Rust internally.)
Internally? No. Externally? Yes. That is the point.
I'm no rust expert but isn't this sort of thing exactly what traits handle well?
Not directly relevant.
Are the Rust devs not expanding the surface area of safe Rust over time? Just curious.
Sort of but also no. Intrusive lists are not likely to ever be possible in safe code, almost by definition.
I think this article rewrites history and it is unfortunately already cited by the clankers.
"Intrusive" is C++ speak. The regular linked lists always had embedded data or a mix of embedded data and pointers to outside data in a C struct.
I googled it and got the response that Bjarne Stroustrup first used “intrusive” in his 1985 C++ book. He was adding a new distinction between the older intrusive kind and the new ‘non-intrusive’ kind, because some people had started using C++ to allocate the list nodes and the payload structs separately.
Now with std::list and college classes often teaching non-intrusive linked lists, and intrusive lists only being used in deep dark places like the OS kernel, maybe it’s easy to assume the ‘regular’ kind is non-intrusive.
What Stroustrup called ‘intrusive’ had been the default understanding of linked lists since around 1955, and what people used most often. A ‘regular’ linked list to most people back then was the intrusive kind, and the term ‘non-intrusive’ might have been an attempt to sell people on the benefits of abstracting and separating node types from payloads, but that maybe papers over the disadvantages a little.
The only kind of linked list I’ve ever used in my professional career is the intrusive kind. There are very few good reasons to ever use non-intrusive lists outside of the classroom. At least, not if you care about performance at all. They might be convenient & easy, but it’s usually the case that either an array or an intrusive list would be a better engineering choice.
If you mean being able to a generic `list<foo>` type (whether by C++ templates, macros, or good old void* casts), it's more than that. The benefit of non-intrusive is being able to create/manipulate/pass around multiple collections pointing to same payloads, without disturbing the payloads or the other collections in any way¹. That makes it easier to return and manipulate collections functionally (both in the narrow immutable sense, but also in the wider "treat collections like _values_ sense)... The deepest benefit arising from that I suppose is code modularity: different code areas need not be aware of each other's existence.
That all obviously comes at some tradeoff to performance. By definition, not having a full picture of the pathways your data travels means you can't choose the fastest representation!
¹The cheat is GC. For multiple unconnected collections to point to same payload, you need ref counting, or mark&sweep or similar to control its lifetime. Technically, GC does disturb the objects it's tracking (though that's well abstracted from other code).
However, you're largely right that specifically linked lists are rarely a good choice for non-intrusive collections => Arrays usually beat them, and if not then hash sets. (LISP & ML & Haskell do stick to lists for tail sharing — a choice which is arguably outdated by growing CPU / mem random access gap. I suppose Clojure's persistent vectors are an improvement.)
It really depends on the ecosystem you’re working in. For a good while, most developers have been working with managed runtimes, where “non-intrusive” linked lists are generally the default and “intrusive” linked lists correspondingly rare.
(Actually, in many cases arrays are the default (like ArrayList in Java), because lists tend to only get assembled once and then passed around without further modification.)
"Intrusive" may be a C++ speak, but I wouldn't say that one or the other type of lists is necessarily much older or more "normal". After all, a cons cell embeds data and not the other way around and lisp is one of the oldest programming languages in existence
Back in the day what is being called out here as an "intrusive" linked list was just a linked list, since you didn't have the luxury of having memory and CPU cycles to waste with extra allocations and indirection.
In the C++ world the STL introduced generic data types such as linked lists, which became the default, but "instrusive" linked lists still have their place in specialized list-heavy use cases where performance matters. In a previous job I wrote a widely adopted XML/JSON library using instrusive lists to link child elements, and the performance benefit was considerable, with my DOM API basically hiding this implementation detail from the user.
You have it backwards, an intrusive linked list is a linked list that is embedded in another data structure. The classic example is a linked list whose elements live on the stack.
The article is wrong too, or at least using the term over-specifically.
It's not really tied to C++isms at all.
Regular linked lists were implicitly 'intrusive' long before C++ existed and introduced 'extrusive' lists in the stdlib.
GP points out that what the article calls "intrusive linked list" is a regular linked list. Wikipedia for instance gives the canonical linked list example of a struct with one embedded integer and a next link and of course does not call it "intrusive linked list".
"Intrusive" got popular with C++ intrusive pointers, and that is where the article gets is misinformation from.
And of coursed the web jockeys downvote the correct objection since they have no clue about data structures, history, logic or basic reading skills.
It got popular with C++'s attempts at type safety. In particular, std::list lets you accomplish the machinery without macros, and allowing for polymorphism (heterogeneous lists of derived instances) without weird type casts and overallocation tricks, but at the cost of another level of indirection.
This was my reaction exactly. I was surprised by the diagram of a "normal" linked list.
I came to this relatively late (2013-ish, windows kernel development, scouring OSDev, etc) so I thought that was always the right name for them. Prior experience was mostly... higher-level langs.
I concur. I recall being a student and when implementing LL for the first time, you did it this way (mix your data and ptr to next node). It is baby's first linked list.