How to manipulate unsorted lists of objects

Prerequisites

Read about linked lists first.

Basic assumptions

We assume you are using a list as a set, i.e. there is no particular order between the items. This way of storing objects can be used whenever there is no natural order between the items. In other words, the domain of the objects inserted into the set does not have to support comparison. It does, however, have to support equality.

From the client's point of view, objects can be inserted into or deleted from the set, and an object can be tested as to whether it is in the set.

We still have a few implementation decisions to make. Here are some that are visible to the client:

Is it an error to try to insert an object that is already inserted, or is the operation just ignored?
Is it an error to try to delete an object that is not inserted, or is the operation just ignored?

And here is one that affects only the implementation:

Do we allow multiple occurrences of an object on the list?

The last question may seem to be more than one of implementation, but it really isn't. We can allow multiple objects and still present an interface that makes it look like a set. To do that, we simple define an object to be in the set if and only if there is at least one occurrence on the list. A consequence of such a decision is that the delete operation will have to remove all the occurrences. What could be the advantage of such an implementation? The answer is `efficiency'. If no error needs to be signaled when an object already in the set is inserted, we can just put it first on the list, a constant-time operation. If we either need to signal an error or do now allow for multiple objects, we must search the list first to check whether the object is already present, a linear-time operation.

Here, we shall assume that an error must be signaled whenever an attempt is made to insert an element already on the list, and whenever an attempt is made to delete an object which is not on the list. From these two decisions follow that there is no real point in allowing multiple objects on the list.

Initial assumptions

Let as assume that we have some function equal to test the equality of two elements. Notice that elements are generic pointers, so that the equal function must accept to such pointers and return a true value if and only if the two objects are to be considered equal.

The `member` function

Here is an attempt at the member function

  int
  member(list l, void *element)
  {
    list ll;
    for(ll = l; ll; ll = ll -> next)
     {
       if(equal(ll -> element, element))
         return 1;
     }
    return 0;
  }

Some people may object that we are using very short identifiers such as l and ll, whereas good software engineering practice favors longer, more explicit, names. See the section on naming conventions for a complete discussion about this topic.

Some other people may object that we are using a pointer expression such as ll rather than ll != NULL, which is more explicit. However, in the C language they are entirely equivalent for the purpose of a test like this one. The first version is shorter and all C programmers know both to use it and to understand it. It can thus be considered an idiom of the C language.

This first version of member is not quite acceptable. The problem is that we can't have the equal function be global, since the definition of equality depends on the domain of the elements. The only solution is to pass the equality as a parameter like this:

  int
  member(list l, void *element, int (*equal)(void *, void *))
  {
    list ll;
    for(ll = l; ll; ll = ll -> next)
     {
       if(equal(ll -> element, element))
         return 1;
     }
    return 0;
  }

We now have a reasonable version of member. We can improve on it a bit by noticing that l is a local variable just like ll, so that we can use it instead of ll like this:

  int
  member(list l, void *element, int (*equal)(void *, void *))
  {
    for(; l; l = l -> next)
     {
       if(equal(l -> element, element))
         return 1;
     }
    return 0;
  }

which is somewhat shorter and avoids the introduction of another variable. On the other hand, this version might be harder to understand in that it uses a parameter for something it was not intended, namely a loop variable. The previous version makes the distinction explicit. Which version is the best is a matter of taste.

The `insert` function

Let us now turn our attention to insert. Since we decided not to allow duplicate elements, we have to check whether the element to insert is already in the list. If it is, we generate an error. If not, we insert it. Two questions need to be answered:

In the case of an error, how do we report it?
Where do we insert the element?

The first question is answered in the section about errors and exceptions. Briefly, we consider that calling insert with an element already in the list to be a programming error. We therefore use assert to check for it.

The answer to the second question is "anywhere will do". To make our lives easy, we insert at the beginning of the list.

Before we look at some code, we have solve some minor problems. The insert function will take a list as an argument and possibly modify it. But since parameter passing is by value, modifications inside insert will not necessarily be visible to the caller. For instance, this function:

  void
  stupid(list l)
  {
    l = malloc(sizeof(struct cell));
    l -> next = NULL;
    l -> element = NULL;
  }

or using the cons function from the list module:

  void
  stupid(list l)
  {
    l = cons(NULL, NULL);
  }

has as its only effect to allocate a cell that then can never be referenced, which gives a memory leak (see need for garbage collection).

We must somehow communicate the updated list to the caller. There are two options, both acceptable. We can either pass a pointer to the list to be modified, or return the modified list as the value of the insert function.

Here is a version of insert using pointer passing:

  #include < assert.h>

  ...

  void
  insert(list *lp, void *element, int (*equal)(void *, void *))
  {
    assert(!member(*lp, element, equal));
    *lp = cons(element, *lp);
  }

We notice several things. First, we need the line:

  #include < assert.h>

in order to get access to the assert function (or rather the assert macro). Then, we notice that the insert function must also be passed the equal, so that it can check whether the element to insert is already on the list.

Also notice the change of names. We have used lp for the argument. It is an abbreviation for `list pointer'. We can't really use l since that would be deceiving the reader into thinking that it is a list. It isn't. It is a pointer to a list. Also, using lp frees up the name l for the local variable.

Make sure you understand every use of pointer dereferencing (i.e. * in this example.

Here is a version of insert using return value:

  #include < assert.h>

  ...

  list
  insert(list l, void *element, int (*equal)(void *, void *))
  {
    assert(!member(l, element, equal));
    return cons(element, l);
  }

Notice that the two versions must be used somewhat differently. Assuming that we want to insert an element e into a list l using the function equal, the first version would be called like this:

  insert(&l, e, equal);

whereas the second version would be called like this:

  l = insert(l, e, equal);

The `delete` function

For the delete function, we have similar choices regarding parameter passing as we had with the insert function, i.e. we can either pass a pointer to the list, or we can return a modified list.

But whereas with insert we could insert the element at the beginning of the list, with delete we have to find the element and remove it. Now, it may seem that we can just do what we did in member, that is:

  for(ll = l; ll; ll = ll -> next)
   {
     if(equal(ll -> element, element))
       /* we found it, delete it */
     ...
   }

But that does not really work. The problem is the following: When the statement:

  equal(ll -> element, element)

is true, then, ll is a pointer to the cell containing the element to be removed, i.e, the cell pointed to by ll must be removed from the list. But removing a cell from the list means modifying either the next field of the previous cell, or (in case the cell to remove is the first one) modifying the initial list. The traditional solution (which we do not recommend in C) is to use a trailing pointer. Here is a version of delete with such a trailing pointer:

  void
  delete(list *lp, void *element, int (*equal)(void *, void *))
  {
    list ll;
    list trail = NULL;
    assert(member(*lp, element, equal));
    for(ll = *lp; !equal(ll -> element, element); trail = ll, ll = ll -> next)
     ;
    if(!trail)
      *lp = cdr_and_free(*lp);
    else
      trail -> next = cdr_and_free(trail -> next);
  }

First a few remarks. Since we checked that element is in the list (in the call to assert), we don't have to check for the end of the list in the loop. We simply know that equal will ultimately return a true value. Also notice that we again allow ourselves to use a pointer value (here trail as a boolean value in a test. Also notice the use of the sequencing operator (the comma) in the last clause of the for loop. The variable trail is assigned the old value of ll before ll is advanced to the next cell. Further notice that the body of the for loop is empty, and that the semicolon that indicates that is on a line by itself. This is considered style. This version of delete has several problems. We already mentioned that we don't recommend the method of trailing pointers. The reason is that it introduces a special case that we then must test for. The special case is when trail is NULL, in which case the first element should be deleted. Notice that we treat the special case first, even though we have to negate the value of trail. As a matter of style, it is better to treat the special case first. Some people might think that doing so would be less efficient, since after all we have to negate the value of trail. This is wrong. Any reasonable compiler will generate the same code for the two cases.

The other main problem with this version of delete is that it scans the list twice, once in the call to the member function, and once to find and delete the element.

Let us first fix the problem with the trailing pointer. To avoid the special case, we can use a feature of the C programming language that lets us create a pointer not only to a block of memory returned by malloc but to any part of memory of the right type. Here is a version of delete using that feature:

  void
  delete(list *lp, void *element, int (*equal)(void *, void *))
  {
    list *llp;
    assert(member(*lp, element, equal));
    for(llp = lp; !equal((*llp) -> element, element); *llp = &((*llp) -> next))
     ;
    *llp = cdr_and_free(*llp);
  }

We immediately notice how the special case disappeared, and the resulting code is much shorter. Some people might object that this code is less readable (some would say unreadable) than the previous one. See using advanced features for a discussion concerning this topic.

Now, let us turn our attention to the second problem (traversing the list twice). We don't have to use the member to test whether the element is a member of the list or not. We can simply use the existing code, something like this:

  void
  delete(list *lp, void *element, int (*equal)(void *, void *))
  {
    list *llp;
    for(llp = lp;
        *llp && !equal((*llp) -> element, element); 
	*llp = &((*llp) -> next))
     ;
    assert(*llp);
    *llp = cdr_and_free(*llp);
  }

We notice several things. Most trivially, the clauses of the for loop are now so complicated that they will not (or just barely) fit on a line. We have therefore split the loop header into three lines, one for each clause. Second, we have re-introduced the test for the end of the list. We must do that since we eliminated the call to member. We simply no longer know whether the element is a member or not when we execute the loop. The result of a loop is now that *llp is NULL if and only if the element is not in the list. The call to assert makes sure the element is indeed on the list.

But now we have one loop in the delete function and one in the member function. In such a situation, the highly skilled programmer usually tries to factor the code, i.e. put the code in one single place. In this case, it doesn't look obvious to do so, since the loops don't look anything alike. Factoring this code requires some imagination. We are going to introduce another function that we will call find. The find function does the work of the loop in delete, i.e. it returns a position (of type list *, called (say) llp) such that if *llp is NULL, then the element is not on the list, and if *llp is not NULL, then the element is on the list. Here it is:

  list *
  find(list *lp, void *e, int (*equal)(void *, void *))
  {
    for(; *lp && !equal((*lp) -> element, e); lp = &((*lp) -> next))
     ;
    return lp;
  }

By re-using the argument lp we don't need a new variable llp. Together with using e as the name for the element to check for, it allows us to cut down the size of the code so that the loop heading again will fit on one line.

Now, we can easily define delete by using find like this:

  void
  delete(list *lp, void *element, int (*equal)(void *, void *))
  {
    list *llp = find(lp, element, equal);
    assert(*llp);
    *llp = cdr_and_free(*llp);
  }

If we are willing to re-use lp, we can make it one line shorter like this:

  void
  delete(list *lp, void *element, int (*equal)(void *, void *))
  {
    assert(*(lp = find(lp, element, equal));
    *llp = cdr_and_free(*llp);
  }

and if we have a garbage collector (see need for garbage collection), we can even eliminate the call to cdr_and_free like this:

  void
  delete(list *lp, void *element, int (*equal)(void *, void *))
  {
    assert(*(lp = find(lp, element, equal));
    *lp = (*lp) -> next;
  }

which should be compared to our initial 13-line version. Sure, we have introduced another function (find), but now we can use it to implement member. Recall our previously best version:

  int
  member(list l, void *element, int (*equal)(void *, void *))
  {
    for(; l; l = l -> next)
     {
       if(equal(l -> element, element))
         return 1;
     }
    return 0;
  }

which we can now simply replace by:

  int
  member(list l, void *element, int (*equal)(void *, void *))
  {
    return *(find(&l, element, equal));
  }

Similarly, we can modify insert to use find directly (although we don't have to), like this:

  insert(list *lp, void *element, int (*equal)(void *, void *))
  {
    lp = find(lp, element, equal);
    assert(!(*lp))
    *lp = cons(element, *lp);
  }

Notice that this version no longer inserts at the beginning, but at the end of the list. The list has to be scanned anyway in order to find out that the element is not a member. This scan stops at the end of the list, which is the point we use for insertion. This trick will be useful when we discuss manipulating sorted lists.

Turning it into a module

Now that we got our programming idioms done, let us look at how to turn these functions into a module. Recall that we divide a module into two distinct files, the header file (or the .h file) and the implementation file (or the .c file). Let us call our module ulset. Before we show the header file, let us make some observations about the equal function in the previous functions. That function determines how elements of the ulset are to be compared for equality. It is not reasonably to use different equal functions in different calls to these functions for the same ulset. But requiring the client to pass the equal function to each call makes it easier to violate this rule. We can prevent that, and at the same time make client code easier to understand, by passing the equal function to the constructor of ulset, i.e. the function that creates an empty ulset. With that in mind, we can now look at a typical header file:

  #ifndef ULSET_H
  #define ULSET_H

  /* We use unsorted linked lists to implement sets of elements,
     that can handle only equality */

  struct ulset;
  typedef struct ulset *ulset;

  /* create an empty ulset */
  extern ulset ulset_create(int (*equal)(void *, void *));

  /* return a true value iff the element is a member of the ulset */
  extern int ulset_member(ulset l, void *element);

  /* insert an element into an ulset.  The element must not already
     be a member of the ulset. */
  extern void ulset_insert(ulset l, void *element);

  /* delete an element from an ulset.  The element must be
     a member of the ulset. */
  extern void ulset_delete(ulset l, void *element);

  #endif

We have added comments describing briefly what the module does, and describing what each interface function does. The phrases must be and must not be mean that a program that does not respect what these phrases say, is a program with errors in it. This module is therefore free to do whatever it thinks reasonable (including nothing at all) when such a condition is violated. In our implementation, we will call assert and abort the execution of the program.

For the implementation file, we must use a header object as described in uniform reference semantics. The use of this header object will also fix the incompatibility between the interface of insert and delete on the one hand and ulset_insert and ulset_delete on the other hand. Here is the implementation file:

  #include "ulset.h"
  #include "list.h>
  #include < assert.h>
  #include < stdlib.h>

  struct ulset
  {
    int (*equal)(void *, void *);
    list elements;
  };

  ulset
  ulset_create(int (*equal(void *, void *)))
  {
    ulset l = malloc(sizeof(struct ulset));
    l -> elements = NULL;
    l -> equal = equal;
    return l;
  }

  static list *
  find(list *lp, void *e, int (*equal)(void *, void *))
  {
    for(; *lp && !equal((*lp) -> element, e); lp = &((*lp) -> next))
     ;
    return lp;
  }

  int
  ulset_member(ulset l, void *element)
  {
    list *lp = find(&(l -> elements), element, l -> equal);
    return *lp;
  }

  void
  ulset_insert(ulset l, void *element)
  {
    list *lp = find(&(l -> elements), element, l -> equal);
    assert(!(*lp))
    *lp = cons(element, *lp);
  }

  void
  ulset_delete(ulset l, void *element)
  {
    list *lp = find(&(l -> elements), element, l -> equal);
    assert(*lp);
    *lp = cdr_and_free(*lp);
  }

Notice that for reasons of symmetry, we introduced a variable lp at the beginning of each function of the interface, which is always initialized to the value of a call to find. For symmetry, we also renamed the local list variable in ulsetisert so that it is called temp just as in ulset_delete.

We prefix all interface functions (except the constructor) with ulset_. Such prefixing is neither necessary nor desired for internal functions such as find.