How to Remove an Item in a List (Good Taste and Bad Taste)?

Imagine a link-list data structure, given an entry, you are asked to remove the item from the list. In C/C++, you may write something like this (CAUTION: the following is NOT a production code as it assumes the entry is always existent in the list and Memory leaks. Gotta deallocate the removed leaves/nodes, Or shove them at the end to be reused, then only loop until member “end”. Saves allocations.):

void remove_list_entry(entry) {
  prev = NULL;
  walk = head;

  // walk the list to find the entry
  while (walk != entry) {
    prev = walk;
    walk = walk->next;
  }

  // remove the entry by updating the head or previous entry
   if (!prev) {
      head = entry->next;
   } else {
      prev->next = entry->next;
   }
}

The implementation is straightforward: first find the item by walking from the head towards the end of the list, then remove it. However, there is a special case that the entry is the head of the list where you need to point the new head to its next item.

Let’s see another implementation:

void remove_list_entry(entry) {
  // The 'indirect' pointer points to the *addres* of the thing we update
  indirect = &head;

  // walk the list, locate the thing that points to the entry we want to remove
  while ((*indirect) != entry) {
     indirect = &(*indirect)->next;
  }

  // and then just remove it
  *indirect = entry->next;
}

This version eliminates the special case, however, may not be obvious at a first glance. Does it really matter? The differences of performance in modern CPUs may not be noticeable unless you run a profiler and find them in the hot-spot. But as Linus Torvalds mentioned in his talk “The mind behind Linux”, the second implementation has a “Good Taste”.

–EOF (The Ultimate Computing & Technology Blog) —