jaysudodeveloper/Good taste.md

Linus Torvalds in an interview (transcript and video available at the 14:17 marker) 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, 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 structure from Torvalds's slide. As a reminder, the member access through pointer (->) operator has precedence over both the dereference (*) and addres-of (&) operators. Also, the * and & opearators have right-to-left associativity.

int main(int argc, char const *argv[]) {
  // 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);
}

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;
  }
}

And this is a way to do it without having to worry about whether the list already has elements. It's more elegant.

// Tricky implementation of add_entry

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 at some point you need to evaluate the costs and benefits of each approach.