The Problem: There are lots of ways of creating a linked list. There are
only a few good ones.
The Hack: The Linux kernel's linked list implementation. (See the file
/usr/include/linux/list.h in any kernel source tree.)
There a large number of things we can learn from this simple module.
First since linked lists are a simple and common data structure it makes
sense to create a linked list module to handle them. After all things can get
confused if everyone implements his own linked list. Especially if all the
implementations are slightly different.
Lesson 1: Code Reuse.
The way the linked list is implemented is very efficient and flexible. You
can actually have items that are put on multiple lists.
Lesson 2: Flexible design.
The list functions are well documented. The header files contains
extensive comments using the Doxygen documentation convention (See Hack
65).
Lesson 3: Share your work. Document it so others can use it.
There's there's a mechanism in place to help persuade people to use this
implementation and to avoid writing their own. If you submit a kernel patch
containing a new linked list implementation you will be “politely”
5
told to use the
standard implementation. Also your code won't get in the kernel until you do.
Lesson 4: Enforcement of standard policy. Mostly through peer pressure.
So by looking at this implementation of a simple linked list we can learn
something. Which leaves us with our final lesson:
Lesson 5: A good hacker learns by reading code written by someone who
knows more about this type of programming that you do.