Assignment 4: Implementing the list ADT

Assignment 4: Implementing the list ADT

The interface of a list

Let us try to deduce a pretty interface for a list.

First, we clearly need functions to create a new list, List_new(), and to delete an existing list, List_delete().

Second, everybody agrees that we need functions to insert an element in a list, List_insert(), and to erase an element from the list, List_erase().

Third, it does not hurt to have information about the amount of data present in a list. Basically, we need a function that returns the number of elements in a list, List_size(), and a function that checks whether a list is empty or not, List_is_empty().

Fourth, we need to traverse a list. Now we have a problem! What are the functions needed to traverse a list?

Traversing a list

Suppose that in the header file that defines the list interface (let us call it list.h) we have something like this:

struct List_node
   void                   *element;
   struct List_node       *previous;
   struct List_node       *next;

typedef struct List_tag
   int                     count;
   struct List_node       *begin;
   struct List_node       *end;
} *List_T;

Let us imagine that we have a program that uses the list ADT. The code for this program is in user.c, which includes list.h. Somewhere in user.c the variables list and p are defined like this:

List_T                  list;
struct List_node       *p;

Let us further assume that list->end is manipulated by the implementation of the list ADT in such a way that we know that if we reach list->end, it means that we have gone past the last node of the list. In this case, the code to traverse the list could be written like this:

for (p = list->begin; p != list->end; p = p->next)

It seems OK, but it is not. This kind of implementation unnecessarily exposes too many nasty details of implementation to the users of the ADT. The worst thing about this is that if we change the structure of List_tag or the structure of List_node, programs that use this ADT may stop working or not compile because they could have made assumptions about the implementation. That is too bad.

The second kind of implementation could hide completely the details of those structures by making List_T an opaque pointer in list.h, like this:

typedef struct List_tag *List_T;

In this case, the list ADT would need to have its own internal pointer to the node currently being visited, and the interface of the list ADT would need to have functions to manipulate this pointer. Then we would not need to have the pointer p in the preceding code which could be rewritten like this:


This is quite superior to the first option, but it is still not that good. What if instead of one pointer scanning the list we wanted two pointers to two possibly different nodes? Well, we could provide the second internal pointer and expand the interface, but what if we wanted three pointers? And what about ten? We cannot keep adding internal pointers and changing the interface because it would become cumbersome.

The third (and I promise the last for this assignment) option uses opaque pointers to a list and opaque pointers to list nodes. So in the list.h file we have something like this:

typedef struct List_tag *List_T;
typedef struct List_node *List_iterator_T;

This introduces the concept of an iterator which is an opaque pointer to a list node. We can have as many iterators as we want. However, we cannot operate on them as they were non-opaque pointers. In particular, we cannot dereference an iterator. As a consequence, we can neither directly access the element pointed to by an iterator, nor move directly the iterator back and forth. So the interface must provide functions to do these operations. Let us declare the variable p as an iterator like this:

List_iterator_T p;

In this case, the code to traverse the list would look like this:

for (p = List_begin(list); p != List_end(list); p = List_next(p))
   do_something(List_element(list, p));

The interface of a list revisited

Now we can come back to where we left off. In order to traverse a list, we need: a function that returns an iterator to the first node of the list, List_begin(); a function that returns an iterator that indicates the fact that we have gone past the last node of the list, List_end(); functions to move an iterator back and forth, List_previous() and List_next(); and a function that returns the element of the node pointed to by an iterator, List_element().

Lastly we would like to provide a function that moves a sequence of nodes from one list to a specified position in another list, an operation known as "splicing". In the process, the sequence of nodes is removed from the original list. The function List_splice() takes the list to insert nodes into, an iterator for this list that indicates where to insert, a second list from which nodes will be removed, and two iterators that specify the beginning and end of the sequence of nodes to remove from the second list.

Click here to see the list.h file which contains the precise declaration of the interface of the list ADT.

Click here to see a very simple test of this interface. Click here to see a more complete example.

What you have to do

You have to write the list.c file. ("Only this???" Yes, only this!!!)

Be sure that your implementation handles the boundary cases well. For example, insertions can happen in any place >= List_begin() and <= List_end(). However, accesses and erasures can only happen in places >= List_begin() and < List_end() (it is not valid to "dereference" the iterator returned by List_end(); it means that you can neither access the element of the node pointed to by List_end()), nor delete this node.

Also, check any possible run-time errors like an attempt to pass a NULL pointer when a valid list, iterator, or element is expected; getting a NULL pointer from malloc(); or an attempt to erase a node from an empty list.

How to submit the program

Submit the list.c file electronically with the command

/u/cs217/bin/submit 4 list.c

You may use other computing facilities to develop your program, but the submitted version must compile with lcc and execute correctly on the arizona machines.

How your program will be graded

We will compile and link your file with some user.c file that we will write to test if your implementation runs smoothly. Hint: test your program with the given examples; in the /u/cs217/4 directory you can find (among others) the following files that can make your life easier: list.o (compiled version of a working implementation that does not implement List_splice), test1 (the executable for the first example), test2 (the executable for the second example), and makefile (a sample makefile).

Due date

You have to submit your program by 11:59pm, Monday, March 8, 1999.

The ideas presented here were taken from the book C++ Programmer's Guide to the Standard Template Library .

Copyright (c) 1996 by Wagner Toledo Corrêa
Special thanks to Yefim Shuf