Linus Torvalds' good taste argument for linked lists, explained(github.com)
github.com
Linus Torvalds' good taste argument for linked lists, explained
https://github.com/mkirchner/linked-list-good-taste
326 comments
I'm not sure why the article removed comments from the code and replaced variable names like "indirect" with "p". Here are the two code samples verbatim from Linus's presentation:
I understand the general point (and value) of reframing the problem or the solution in a way that removes special cases ... but in this case I would actually prefer the first solution over the second. The second solutions reminds me of the old-school perl culture, and JavaScript culture, where 'cleverness' (which always manifests itself as terseness as if lines of code were expensive), takes precedence over maintainability and understandability. Your code is going to be potentially maintained years in the future by developers of all levels - make it easy on them by practicing the principle of least surprise. In this case, this means using a traditional implementation of a linked list that most developers would be familiar with.
Maybe slightly off topic, but..
I don't think this is really about taste. It's about "common ground" between programmers. If you've seen and used the second pattern many times before, it becomes part of your vocabulary. You're then able to express yourself more succinctly. It is then obviously a better solution to you.
If you see another programmer use the same pattern, it is common ground between you, and you like it. As long as every or most programmers on the team share the same common ground, you are more effective for using it. If you don't share it, you're less effective.
Everyone here commenting that they like the first solution better probably doesn't share the necessary common ground with Linus.
The big question is: what common grounds should you expect when writing your code?
I don't think this is really about taste. It's about "common ground" between programmers. If you've seen and used the second pattern many times before, it becomes part of your vocabulary. You're then able to express yourself more succinctly. It is then obviously a better solution to you.
If you see another programmer use the same pattern, it is common ground between you, and you like it. As long as every or most programmers on the team share the same common ground, you are more effective for using it. If you don't share it, you're less effective.
Everyone here commenting that they like the first solution better probably doesn't share the necessary common ground with Linus.
The big question is: what common grounds should you expect when writing your code?
Like others here, I prefer the first.
The first one -- I read it, I know what it does, it seems intuitive to understand, and I expect it to be bug-free especially because the edge case is explicitly accounted for. If someone else has to modify it later, I'm not particularly worried they'll mess it up.
The second one -- it took me about 4x longer to understand what it does. It works too, but it doesn't match how my brain naturally thinks about it, so it leaves me with the uneasy feeling "what if there's a bug?" and I'd be more worried someone else would introduce a bug if they had to modify it later.
I don't want "elegance" or "good taste" in code. Unless it has a good reason to be hand-tuned for performance, I want code that is written the way you'd expect an average programmer to write it. Nothing clever, just a straightforward translation of requirements into code. Not "transforming" them into something more "elegant".
The first one -- I read it, I know what it does, it seems intuitive to understand, and I expect it to be bug-free especially because the edge case is explicitly accounted for. If someone else has to modify it later, I'm not particularly worried they'll mess it up.
The second one -- it took me about 4x longer to understand what it does. It works too, but it doesn't match how my brain naturally thinks about it, so it leaves me with the uneasy feeling "what if there's a bug?" and I'd be more worried someone else would introduce a bug if they had to modify it later.
I don't want "elegance" or "good taste" in code. Unless it has a good reason to be hand-tuned for performance, I want code that is written the way you'd expect an average programmer to write it. Nothing clever, just a straightforward translation of requirements into code. Not "transforming" them into something more "elegant".
I've been teaching CS101 for two decades. I've never shown (nor seen another instructor show) a two pointer implementation for list traversal, except perhaps as an example of bad practice (probably by someone who doesn't understand the syntactic sugar of the -> operator). "Every pointer to node is a list, including the trivial case of a null pointer being an empty list" is the way I was taught in CS101 in the early 80s, including a one-pointer implementation of this algorithm in Pascal.
I suspect this might a case similar to that of the "Waterfall Method", where we have this unexamined belief that in olden times or academia they just weren't capable of comprehending really obvious things. CompSci instructors, and most of their students, are quite capable of recognizing that two pointers aren't needed, if only because every algorithms textbook they've ever read discusses it.
I think that this might be like Bubble Sort: it's discussed in class as a way of illustrating a point. In students' fuzzy memories of school, they remember that bubble sort and 2-pointer traversal were taught, but they forget that they were taught only to show why selection sort and single pointer ("look ahead") traversal are better algorithms.
As a side note: I don't like the "elegant" version's use of double indirection. It's not necessary if you return a pointer instead of void, which is also nice because you can treat calls to your list functions as lists themselves and chain them together. It also allows you to avoid warts like `p = &(*p)->next;` at the modest cost of needing `p=remove(p,t)` instead of `remove(p,t)`.
Finally, the use of two structs is unnecessary. IntList is just a wrapper around a pointer to IntListNode. Why not just use a naked pointer to IntListNode like the gods intended?
I suspect this might a case similar to that of the "Waterfall Method", where we have this unexamined belief that in olden times or academia they just weren't capable of comprehending really obvious things. CompSci instructors, and most of their students, are quite capable of recognizing that two pointers aren't needed, if only because every algorithms textbook they've ever read discusses it.
I think that this might be like Bubble Sort: it's discussed in class as a way of illustrating a point. In students' fuzzy memories of school, they remember that bubble sort and 2-pointer traversal were taught, but they forget that they were taught only to show why selection sort and single pointer ("look ahead") traversal are better algorithms.
As a side note: I don't like the "elegant" version's use of double indirection. It's not necessary if you return a pointer instead of void, which is also nice because you can treat calls to your list functions as lists themselves and chain them together. It also allows you to avoid warts like `p = &(*p)->next;` at the modest cost of needing `p=remove(p,t)` instead of `remove(p,t)`.
Finally, the use of two structs is unnecessary. IntList is just a wrapper around a pointer to IntListNode. Why not just use a naked pointer to IntListNode like the gods intended?
Semi-relevant side note: Within some constraints its possible to remove an element in a singly linked list without walking the list. The purpose of walking the list is not to find the element (which you already have) but to find it's previous element so you can fix the "next" pointer on the previous element. What you can do instead is to copy the data from the next element onto the one to delete, making it a "copy" of the next one. And then delete the next one after fixing the pointers. Hard to say in english but here's the idea:
remove_list_entry(entry)
{
next = entry->next;
entry->data = next->data;
entry->next = next->next;
free(next);
}
You do need to handle the case of deleting the last element in the list. That can be done by keeping an EOL element at the end just for this purpose. The real caveat is that it breaks external references to list elements. If you are managing the list yourself however and can deal with these issues you can avoid list traversal (or save a pointer on every list element vs a doubly linked list). Just something to keep in your bag of tricks.To relate this topic back to Computer Science and Math, the linked list traversal problem can be related back to Proof by Induction -- There's a base case (a starting condition) and then the inductive steps: "...proves that if the statement holds for any given case n = k, then it must also hold for the next case n = k + 1"
We can prove using proof by induction that Linus's implementation works because of the base case "indirect = &head", and the inductive step which is the rest of the program.
It'd take a lot more work to mathematically prove that the branching program "works" due to the if statement -- you'd have to construct a proof of each branch and prove that the combination works.
I'm not a mathematician, but this was a major point in CS courses at university. Being able to prove an algorithm works can extend into automated program checking / auditing, etc.
It's not just "taste" -- there's a lot of practical theory to be applied.
https://en.wikipedia.org/wiki/Mathematical_induction
We can prove using proof by induction that Linus's implementation works because of the base case "indirect = &head", and the inductive step which is the rest of the program.
It'd take a lot more work to mathematically prove that the branching program "works" due to the if statement -- you'd have to construct a proof of each branch and prove that the combination works.
I'm not a mathematician, but this was a major point in CS courses at university. Being able to prove an algorithm works can extend into automated program checking / auditing, etc.
It's not just "taste" -- there's a lot of practical theory to be applied.
https://en.wikipedia.org/wiki/Mathematical_induction
Although I liked the 'elegant' code after reading it, in general I would try to shy away from 'elegant' solutions that are actually harder to understand. Unless you are working with high-performance programs, most of the time you don't care about one or two extra branches. It's usually more beneficial to write code that can be easily understood by a future-you or by another person in your team: less time invested in understanding code, more time dedicated to actually fixing issues that matter. If performance becomes an issue, you'll catch that in profiling easily (because everybody here is profiling before trying to improve the performance of a piece of code, right?).
I think what's missing in the mental model of the elegant solution is, that the IntList-pointer does not point to a complete list or an element of the list, but to a tail of some list (that might be the complete list). This explains why the head is not really a special case, as it points to the tail that is complete. And you can just exchange a tail.
So I think the image with the blue boxes is misleading and it should be
->[4->[12->[3->[6->[2->[]]]]]]
It is now obvious that you can always point -> to a different [...]
And as it turns out, that is basically the Cons/Nil view of a list from functional programming or lisp, if you're so inclined. And in those languages you would pattern match on the constructor once and do the tail-recursive call.
So I think the image with the blue boxes is misleading and it should be
->[4->[12->[3->[6->[2->[]]]]]]
It is now obvious that you can always point -> to a different [...]
And as it turns out, that is basically the Cons/Nil view of a list from functional programming or lisp, if you're so inclined. And in those languages you would pattern match on the constructor once and do the tail-recursive call.
These functions can be thought of as two steps:
1. Find the thing to update
2. Update it
Linus's version does just that.
But the first version is more complex because step 1 instead emits something that may or may not be the thing to update, and so step 2 has to reason about that. Additionally, it introduces a bookkeeping variable -- cur -- which becomes redundant before step 2 (by which point it's equal to target).
IMO Linus is right here. The form of his solution directly matches the problem and allows you to look at the code as two clean steps -- no reasoning about the output of the first step and no bookkeeping cruft variable that you have to ignore or remind yourself that it's the same as another variable after some point in the function. At least once you're used to working with double pointers I think that's a much easier function to read.
1. Find the thing to update
2. Update it
Linus's version does just that.
But the first version is more complex because step 1 instead emits something that may or may not be the thing to update, and so step 2 has to reason about that. Additionally, it introduces a bookkeeping variable -- cur -- which becomes redundant before step 2 (by which point it's equal to target).
IMO Linus is right here. The form of his solution directly matches the problem and allows you to look at the code as two clean steps -- no reasoning about the output of the first step and no bookkeeping cruft variable that you have to ignore or remind yourself that it's the same as another variable after some point in the function. At least once you're used to working with double pointers I think that's a much easier function to read.
Most people prefer the first over the second. But I think that Linus really should prefer the second over the first. Let me try to explain why.
There is a well-known saying attributed to David Wheeler, "All problems in computer science can be solved by another level of indirection." Except the problem of having too many layers of indirection. Also both quotes are often seeing with "abstraction" instead of "indirection".
There is a not well-known saying that you can attribute to me, "Any method of abstraction that you have internalized becomes conceptually free to you." (So for the sake of others, choose wisely which you will expect maintenance programmers to have internalized!)
The key to the elegant solution is understanding how to manipulate data through pointers.
That makes the elegant solution inappropriate to use in CS 101. It involves a method of indirection/abstraction that is emphatically NOT free to beginning programmers.
It also makes the elegant solution inappropriate for most people on HN. We do not directly deal with manipulating things through pointers very much. Therefore most of us have not internalized how to do that, and the technique is very much not free to us.
However Linus is a kernel developer. Anyone maintaining his code will also be a kernel developer. Kernel developers have to internalize how to handle manipulating data through pointers because their APIs require it. For example look at https://www.kernel.org/doc/html/v4.14/filesystems/index.html and see that pretty much every function gets a pointer to a data structure, and then manipulates that data structure through the pointer.
Therefore every kernel developer should internalize how to manipulate data through pointers. And the elegant solution therefore becomes not just less code, it becomes conceptually simpler! And yes, any time you can replace a block of code with less code that is conceptually simpler, this shows good taste.
BUT, and this is very important, it is only conceptually simpler if you've already internalized concepts around manipulating data through the indirection of a pointer. Which makes it conceptually simpler for kernel developers like Linus, but not for most programmers in other languages.
There is a well-known saying attributed to David Wheeler, "All problems in computer science can be solved by another level of indirection." Except the problem of having too many layers of indirection. Also both quotes are often seeing with "abstraction" instead of "indirection".
There is a not well-known saying that you can attribute to me, "Any method of abstraction that you have internalized becomes conceptually free to you." (So for the sake of others, choose wisely which you will expect maintenance programmers to have internalized!)
The key to the elegant solution is understanding how to manipulate data through pointers.
That makes the elegant solution inappropriate to use in CS 101. It involves a method of indirection/abstraction that is emphatically NOT free to beginning programmers.
It also makes the elegant solution inappropriate for most people on HN. We do not directly deal with manipulating things through pointers very much. Therefore most of us have not internalized how to do that, and the technique is very much not free to us.
However Linus is a kernel developer. Anyone maintaining his code will also be a kernel developer. Kernel developers have to internalize how to handle manipulating data through pointers because their APIs require it. For example look at https://www.kernel.org/doc/html/v4.14/filesystems/index.html and see that pretty much every function gets a pointer to a data structure, and then manipulates that data structure through the pointer.
Therefore every kernel developer should internalize how to manipulate data through pointers. And the elegant solution therefore becomes not just less code, it becomes conceptually simpler! And yes, any time you can replace a block of code with less code that is conceptually simpler, this shows good taste.
BUT, and this is very important, it is only conceptually simpler if you've already internalized concepts around manipulating data through the indirection of a pointer. Which makes it conceptually simpler for kernel developers like Linus, but not for most programmers in other languages.
The second version seems more elegant but will scare non-C people away with all those pointers ;-)
What I do not understand is why one should use an "IntList" struct in the first place? As the explanation of the second method suggests, a List is the same thing as a pointer to its first element, so why not do this?:
typedef struct IntListItem* IntList;
Also, could it be that both methods fail terribly (infinite loops?) when they are given wrong input such as elements not in the list at all?
What I do not understand is why one should use an "IntList" struct in the first place? As the explanation of the second method suggests, a List is the same thing as a pointer to its first element, so why not do this?:
typedef struct IntListItem* IntList;
Also, could it be that both methods fail terribly (infinite loops?) when they are given wrong input such as elements not in the list at all?
I used to use linux's list.h quite a bit, that is the "good taste" implementation, where the head is the same as the elements. My only problem with that implementation is the fact it is non-typed. Heads are generic, and the code using them has to use container_of() macros to recover the containing type.
I've since discovered bsd/queue.h [0], which is very similar in purpose, but is not "good taste" (which I don't mind at all) on the other hand it is type safe, has quite a few variants for single and double lists, and oh also, it's not GPL.
[0]: https://github.com/freebsd/freebsd/blob/master/sys/sys/queue...
I've since discovered bsd/queue.h [0], which is very similar in purpose, but is not "good taste" (which I don't mind at all) on the other hand it is type safe, has quite a few variants for single and double lists, and oh also, it's not GPL.
[0]: https://github.com/freebsd/freebsd/blob/master/sys/sys/queue...
The following is the code I wrote before reading the example pieces of code.
void remove(IntList* l, IntListItem* target) {
if (l->head == target) {
l->head = l->head->next;
return;
}
IntListItem* prev = l->head;
while (prev->next != target) prev = prev->next;
prev->next = prev->next->next;
}
Skimming the comments here, I was surprised not to see an equivalent piece of code mentioned. To me my code is more readable than both of the first and second examples presented in the article. Does that mean my taste is peculiar?The trick employed by the "good taste" solution is to ignore the type of the object containing the pointer, which is different for the head, and focus only on the type of the object pointed to, which is the same for all the pointers. This frame of reference shift makes the solution look tricky to people unaccustomed to working with pointers, or languages in which pointers are not explicitly represented. It is also not quite true, as the pointer in the last element in the list does not point to a list element.
I've seen the "better" version a few times before. I wrote something equivalent from first principles.
It is NOT better. It is much more difficult to understand. Software engineering is about making the code intelligible for the people who follow you. The simple two pointer with conditional is MUCH easier to read and understand.
It is NOT better. It is much more difficult to understand. Software engineering is about making the code intelligible for the people who follow you. The simple two pointer with conditional is MUCH easier to read and understand.
Author here.
To add context that seems lost on some: this is a cleaned-up version of my own notes from when I tried to understand the technical detail behind what Linus called "good taste" in the TED talk.
The main contributions of the writeup (if any) are the two conceptual insights that using an indirect pointer yields a homogeneous data structure and a convenient handle to the list item and its predecessor.
The article is not intended to show an example of clean code, there is no checking for NULLs, there are implicit expectations (the target needs to exist). It's just not the point.
I also strongly agree with the sentiment in the discussion that simple is often better than elegant. If it takes an entire article to figure out what's happening, that says something about how careful you should be with putting it in production code.
Anyways, thanks everyone on HN for a great discussion and for all the insights, comments and suggestions!
To add context that seems lost on some: this is a cleaned-up version of my own notes from when I tried to understand the technical detail behind what Linus called "good taste" in the TED talk.
The main contributions of the writeup (if any) are the two conceptual insights that using an indirect pointer yields a homogeneous data structure and a convenient handle to the list item and its predecessor.
The article is not intended to show an example of clean code, there is no checking for NULLs, there are implicit expectations (the target needs to exist). It's just not the point.
I also strongly agree with the sentiment in the discussion that simple is often better than elegant. If it takes an entire article to figure out what's happening, that says something about how careful you should be with putting it in production code.
Anyways, thanks everyone on HN for a great discussion and for all the insights, comments and suggestions!
I gave a lot of thought on that example when I first watched the video many many years ago. And I think it all comes down to experience and it has far less to do with good taste. To a junior developer the first solution is perfectly valid and easy to read for everyone. And it is true to a certain degree. But it takes some experience and sooner or later you start getting this feeling that doing something like this probably has a simpler and easier solution, for after all, this is a common thing. Once people wrap their head around that concept(the "surely I'm not the only one that's faced that" thought), they start finding it very easy to jump between languages and learn new ones with ease.
Can't forget the Linux kernel VFS interface of 20 years ago, designed by Linus. It was one of the worst abstraction I ever worked with. Linus is a genius, but not the kind of genius that is able to make things obvious and clean.
I used to ask during interviews to just describe what a linked list was and less than half the candidates for mid/senior positions could. I think it's a really revealing question. Same with hash tables.
The "avoid special cases" argument comes up a lot in math too. For example in combinatorics, some people define 0^0 = 1, so that lots of formulas with "if x == 0 then this else that" just collapse into "that". (Other people insist on inventing a different symbol for this "special exponentiation", but I think that's unnecessary myself.)
For the same reason, an empty sum is defined as 0 and an empty product as 1, so your base cases of some inductions don't require an extra "if".
For the same reason, an empty sum is defined as 0 and an empty product as 1, so your base cases of some inductions don't require an extra "if".
I have an odd structure that links objects into "boxes" where each object can be in more than one box and each box can contain multiple objects. I made a struct to link an object to a box via a pointer to both the object and the box. These links are each part of 2 lists, one from the object and one from the box. The main job is to find all the objects in a given box, which is done by following the list from the box. To delete an object involves following the list off the object and removing all the links - each of which is in a list from a box.
Each link needs two next pointers since it's part of 2 lists. It also needs a PREV pointer for the list from the box for easy deletion. I originally had an empty link object within the box object to be the previous node, but then realized a better way was to have the PREV pointer point to the previous NEXT pointer which means a box only has a pointer instead of a link. This pointer is why I decided to post.
Lastly my link object contained 5 pointers, so I XORed the object and box pointer to cut it down to 4. I always start traversal from one of those, so the XORed value can always be used to reach the other. This did not really impact performance much.
Lastly my link object contained 5 pointers, so I XORed the object and box pointer to cut it down to 4. I always start traversal from one of those, so the XORed value can always be used to reach the other. This did not really impact performance much.
This certainly falls under Rich Hickey's definition of "simple", which is one virtue. But:
> it is not immediately evident how the more elegant solution actually works
another virtue is ease of comprehension, and the more elegant solution lacks that in my (and seemingly Linus') opinion. Maybe if you're used to working with pointers to pointers you might have an intuituon for them, but I at least had a difficult time gaining an intuitive grasp on the second solution, which could potentially nullify the bug-resistance of having fewer branching cases. In short, calling the second one objectively better is overstating it I think.
It's worth noting that in a language with union types, you can have the best of both worlds (using Rust here because it's the one I'm most familiar with):
> it is not immediately evident how the more elegant solution actually works
another virtue is ease of comprehension, and the more elegant solution lacks that in my (and seemingly Linus') opinion. Maybe if you're used to working with pointers to pointers you might have an intuituon for them, but I at least had a difficult time gaining an intuitive grasp on the second solution, which could potentially nullify the bug-resistance of having fewer branching cases. In short, calling the second one objectively better is overstating it I think.
It's worth noting that in a language with union types, you can have the best of both worlds (using Rust here because it's the one I'm most familiar with):
enum LinkedList {
Null,
Node { value: i32, next: Box<LinkedList> }
}
In the same way that the pointer to a pointer homogenizes the head-case with the rest, a union type means that any given linked list "is just a node", and the head can therefore be treated the same way as any later nodeWhich one required writing an article about to explain?
In most cases clarity should win out over succinctness. (Sometimes succinct is more clear).
I absolutely prefer the first one in almost all cases, and would probably reject the second one on a code review.
Unless we're dealing with such a core, hyper-sensitive part of the system wherein the compiler would not find rough equivalence anyhow, and the material gains from supposedly 'fewer instructions' would be better.
i.e. a pragmatic performance optimization that was realized in the real world, due to the pervasive utilization of the code ... this would be acceptable.
But for the vast majority of what we do, this won't be the case.
Double-pointers are like flame throwers - they are very 'cool' to some, and technically, they do 'burn things faster', but are just excessively dangerous and almost assuredly not the right too. Unless, they actually are, wherein you get to be the dude who uses the flamethrower, but again, that's rare.
Reading this it seems more clear to me why git has such tremendous - and mostly unnecessary UX problems. There's a dimensionality of the craft being ignored.
I absolutely prefer the first one in almost all cases, and would probably reject the second one on a code review.
Unless we're dealing with such a core, hyper-sensitive part of the system wherein the compiler would not find rough equivalence anyhow, and the material gains from supposedly 'fewer instructions' would be better.
i.e. a pragmatic performance optimization that was realized in the real world, due to the pervasive utilization of the code ... this would be acceptable.
But for the vast majority of what we do, this won't be the case.
Double-pointers are like flame throwers - they are very 'cool' to some, and technically, they do 'burn things faster', but are just excessively dangerous and almost assuredly not the right too. Unless, they actually are, wherein you get to be the dude who uses the flamethrower, but again, that's rare.
Reading this it seems more clear to me why git has such tremendous - and mostly unnecessary UX problems. There's a dimensionality of the craft being ignored.
I knew I have seen this code somewhere explained years ago and suspected Slashdot. Search for "favorite hack":
https://meta.slashdot.org/story/12/10/11/0030249/linus-torva...
Here using actually "pp" ;)
https://meta.slashdot.org/story/12/10/11/0030249/linus-torva...
Here using actually "pp" ;)
This sounds like a classic case of "simplicity is in the eye of the beholder".
If you're someone who has experience with, or can easily grok concepts such as "pointer to a pointer", then the second snippet seems obviously simpler. After all, there are fewer branches to consider.
Unfortunately, as someone who stopped working with pointers a long time ago, my mind has to work in overdrive to understand any implementation that relies on a "pointer to a pointer". Hence why the first implementation is far easier for me to understand.
I'm sure we'll see many debates around which solution is simpler, but these debates will never reach a resolution. Depending on the skills and experiences you bring to the table, different people will objectively benefit from very different implementations.
https://software.rajivprab.com/2019/08/29/abstractions-are-i...
If you're someone who has experience with, or can easily grok concepts such as "pointer to a pointer", then the second snippet seems obviously simpler. After all, there are fewer branches to consider.
Unfortunately, as someone who stopped working with pointers a long time ago, my mind has to work in overdrive to understand any implementation that relies on a "pointer to a pointer". Hence why the first implementation is far easier for me to understand.
I'm sure we'll see many debates around which solution is simpler, but these debates will never reach a resolution. Depending on the skills and experiences you bring to the table, different people will objectively benefit from very different implementations.
https://software.rajivprab.com/2019/08/29/abstractions-are-i...
I've seen this presentation, and if I remember correctly, this example was more an attempt to convey what good taste can relate to, more than a definitive answer on whether the second is actually better than the first.
Many comments here are arguing that the first answer is actually better because it is clearer. I think it feels clearer to many of us not because it is actually simpler, but because it is the one we learnt at school / are used to see and therefore know by heart.
Linus is probably aware of this and may have meant to surprise the public with the second solution.
Why the second solution is better? Not because it does less branching and is more efficient. This misses the point. Not because there are fewer lines of codes and is terser. This also misses the point.
Fewer special cases means less ways to screw up, and also easier to follow. In the general case. Not only in this specific linked list example. And also clearer code.
It's just that in this specific case, we are used to the first solution that we are able to recognize at a glance (we "pattern-match" it).
Do you remember when you had to grasp this first solution the first time you encountered it or tried to write it? Many of us probably screwed it up and wasted time making it work. We might have forgotten the exact edge case Linus Torvalds was pointing out in this presentation. At least for me, I remember it was hard. I probably would have had easier time understanding the second solution by the way. The difficulty is a pointer indirection, but you better really understand pointers correctly when you are manipulating linked lists in C anyway.
Comments here also speak about leaving maintainable code for future developers on the project and avoid clever solutions to make their life easier, but it is the whole point of the second solution: let them not have to think about edge cases as much as possible.
Don't stop on this linked list example. We are all used to the first solution and Linus Torvalds probably picked this example because many people know linked lists. The message is: fewer edge cases is better. The goal is not to be "clever", in the negative sense.
Also see the original code with comments, which is way more readable: https://news.ycombinator.com/item?id=25327066
Many comments here are arguing that the first answer is actually better because it is clearer. I think it feels clearer to many of us not because it is actually simpler, but because it is the one we learnt at school / are used to see and therefore know by heart.
Linus is probably aware of this and may have meant to surprise the public with the second solution.
Why the second solution is better? Not because it does less branching and is more efficient. This misses the point. Not because there are fewer lines of codes and is terser. This also misses the point.
Fewer special cases means less ways to screw up, and also easier to follow. In the general case. Not only in this specific linked list example. And also clearer code.
It's just that in this specific case, we are used to the first solution that we are able to recognize at a glance (we "pattern-match" it).
Do you remember when you had to grasp this first solution the first time you encountered it or tried to write it? Many of us probably screwed it up and wasted time making it work. We might have forgotten the exact edge case Linus Torvalds was pointing out in this presentation. At least for me, I remember it was hard. I probably would have had easier time understanding the second solution by the way. The difficulty is a pointer indirection, but you better really understand pointers correctly when you are manipulating linked lists in C anyway.
Comments here also speak about leaving maintainable code for future developers on the project and avoid clever solutions to make their life easier, but it is the whole point of the second solution: let them not have to think about edge cases as much as possible.
Don't stop on this linked list example. We are all used to the first solution and Linus Torvalds probably picked this example because many people know linked lists. The message is: fewer edge cases is better. The goal is not to be "clever", in the negative sense.
Also see the original code with comments, which is way more readable: https://news.ycombinator.com/item?id=25327066
> [...] I don't want you to understand why it doesn't have the if statement. But I want you to understand that sometimes you can see a problem in a different way and rewrite it so that a special case goes away and becomes the normal case, and that's good code. [...] -- L. Torvalds
I think the idea of this extends much beyond a linked-list implementation, into software design and architecture.
Sometimes, you find more elegant solutions to something, that inherently do away with edge cases. I think this is the original intent, to show that you can find beauty, much as chessplayers do in chess. These solutions may be harder to understand completely, but you can actually encapsulate them in a function or use them as patterns!
A point is also made, there's often a rewrite involved. You usually don't need to find this stuff on first try.
I think the idea of this extends much beyond a linked-list implementation, into software design and architecture.
Sometimes, you find more elegant solutions to something, that inherently do away with edge cases. I think this is the original intent, to show that you can find beauty, much as chessplayers do in chess. These solutions may be harder to understand completely, but you can actually encapsulate them in a function or use them as patterns!
A point is also made, there's often a rewrite involved. You usually don't need to find this stuff on first try.
Back in the 80's, I learned Pascal, and learned about its dynamically allocated records, then I went on to learn C, and got used to its pointers and arrays.
Then I went back to Pascal, and designed a program in my head with some dynamically allocated linked list data structures, and another data structure that had a member that pointed to the head of the linked list.
Then I started typing in the Pascal code, and hit a wall, because Pascal has ^ which is like C's * operator to dereference a pointer, but doesn't have anything like C's & operator to make a pointer to an arbitrary field in memory, so you can't actually make a pointer to anything except the beginning of a record that you dynamically allocated!
That was when I gave up on Pascal.
Programming Pascal is like riding a bicycle with only one leg.
Then I went back to Pascal, and designed a program in my head with some dynamically allocated linked list data structures, and another data structure that had a member that pointed to the head of the linked list.
Then I started typing in the Pascal code, and hit a wall, because Pascal has ^ which is like C's * operator to dereference a pointer, but doesn't have anything like C's & operator to make a pointer to an arbitrary field in memory, so you can't actually make a pointer to anything except the beginning of a record that you dynamically allocated!
That was when I gave up on Pascal.
Programming Pascal is like riding a bicycle with only one leg.