Linus Torvalds in an interview talked about the idea of good taste in code or what I like to call elegance. As one might expect from two slides meant to make a point during a talk, he omits a lot of details to keep it short and simple. This post digs into the specifics of his example (deleting an element from a list) and adds another example (inserting an element in a list) including working code.
This is an example of removing an element from a singly-linked list. It's one of the first data structures you learn about when you start learning about computer science and programming. The reason it doesn't show particularly good taste is because we have that condition at the end where we take a different action depending on whether the element we want to remove is at the beginning of the list or somewhere in the middle.
The following is better. More elegant. It doesn't matter which element we are trying to remove, we always take the same action and it works for both cases.
Some things to keep in mind:
- This example shows how we could do it when we're deleting the item from within the same function where our list was defined, meaning where our head pointer is defined. In a moment we'll look at the case where we use a separate function to manipulate the list. For now let's stick to the case where we're deleting it from within our main() function.
- It assumes we already have a pointer to the element we want to delete.
I'll use C because we don't need any C++ features to illustrate this point.
First we'll define our node type.
typedef struct node_t {
int value;
struct node_t *next;
} node;Now the fun part: The implementation of the good taste example keeping the same outline from Torvalds's slide. I'll skip the less elegant version because you can easily implement that once you know the better one. As a reminder, the member access through pointer (->) operator has precedence over both the dereference (*) and address-of (&) operators. Also, the * and & operators have right-to-left associativity.
int main() {
// Create an empty list
node *head = NULL;
/*
Add some entries.
When we start out with an empty list the function that adds an entry
(which we'll talk about later) needs to modify the head pointer itself
so instead of passing it a copy of the pointer we send a reference to it.
*/
add_entry(&head, 3);
add_entry(&head, 10);
add_entry(&head, 2);
add_entry(&head, 7);
// Get a pointer to the entry we want to delete,
// in this example the node containing a "3" in it.
node *entry = find_entry(head, 3);
// Create a pointer to the pointer that points to the head of the list
node **indirect = &head;
// As long as what is referenced by our double pointer doesn't point
// to the same place as our entry pointer
while((*indirect) != entry) {
// Advance our double pointer by making it point to the "next" pointer.
indirect = &(*indirect)->next;
}
/*
Now our double pointer points to a pointer that points to the same node as
the entry pointer (the one we're deleting) so we change the "previous" pointer,
which could be the head, to the node that comes after the entry, removing it.
*/
*indirect = entry->next;
// Free up the allocated memory
free(entry);
return 0;
}If we want to create a separate function to do the deletion, we'll need to change the pointer itself, not a copy of it. In C++ you can just declare the pointer parameter as a reference argument (&) and the compiler will take care of the details. In C we need to handle it ourselves so we add one more level of indirection for any parameters that need to be updated including pointers.
/*
The head pointer may need to be modified so we need a double pointer.
The entry pointer is also passed by reference as we'll free that memory.
*/
void remove_entry(node **head, node **entry) {
/*
The indirect pointer points to the pointer that we'll update
*/
node ***indirect = &head;
/*
Walk the list as long as we haven't found the pointer we're looking for
*/
while((**indirect) != *entry) {
*indirect = &(**indirect)->next;
}
/*
We remove it.
indirect, which now points to either null or to the pointer that points to
the entry we want to delete, is set to whatever comes after that entry.
*/
**indirect = (*entry)->next;
free(*entry);
}Now let's look at the add_entry function we used. As it turns out, this one is also a good example of something we can do in a pretty straightforward way but also in a very elegant, better way.
When adding an entry, we need to know if we're working with an empty list and therefore need to change the head pointer or if the list already contains elements, in which case we don't change the head but add the new node after the last one.
/*
When the list is empty adding an element requires modifying the head
pointer itself so the add function needs the address of the pointer,
that is, a pointer to a pointer.
*/
void add_entry(node **head, int new_value) {
node *current = *head;
node *new_node = malloc(sizeof(node));
new_node->value = new_value;
new_node->next = NULL;
if(*head == NULL) {
*head = new_node;
}
else {
while(current->next != NULL) {
current = current->next;
}
current->next = new_node;
}
}The following is a way to do it without having to worry about whether the list already has elements. It's more elegant. Let's start with the case where we're doing it from within our main() function.
int main() {
// We start with an empty list but it could also be an existing list
// with elements.
node *head = NULL;
// A reference to the last pointer. Starts out pointing to the head.
node **indirect = &head;
// We'll add a node with the value "4" in it
node *new_node = malloc(sizeof(node));
new_node->value = 4;
new_node->next = NULL;
// Walk the list until indirect points to the last pointer of the list
while(*indirect != NULL) {
indirect = &(*indirect)->next;
}
// indirect now points to the last pointer in the list whether it was
// empty or not so we just add the new node there.
*indirect = new_node;
return 0;
}And now let's see how we would do the same but in a separate function. This adds another level of indirection just as it did for the delete function.
/*
We'll have to update the head pointer when the list is empty
so we get a reference to it, not a copy.
*/
void add_entry(node **head, int new_value) {
// A reference to the last pointer. Starts out pointing to the head.
node ***indirect = &head;
node *new_node = malloc(sizeof(node));
new_node->value = new_value;
new_node->next = NULL;
while(**indirect != NULL) {
*indirect = &(**indirect)->next;
}
// indirect now points to the last pointer in the list
// whether it was empty or not
**indirect = new_node;
}One final note: There's nothing wrong with the less elegant versions. They work just as well and are easy to implement. Coming up with clean, elegant solutions to problems is harder and you need to evaluate the costs and benefits of each approach including both efficiency and maintainability.
Below you'll find the file taste.c with full working examples of these concepts.
In the "As a separate function" sections you are using too much pointers:
The "indirect" pointer doesn't need to be triple, you could simply write:
node **indirect = head;
(and then use less dereferencing everywhere)
Also you don't need to pass a pointer to the entry pointer, you can free it if you are just passing it normally.
By the way the indirect variable can be also ommitted by just simply writing:
void remove_entry(node **head, node *entry) {
while((*head) != entry) {
head= &(*head)->next;
}
*head= entry->next;
free(entry);
}