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?
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)
{
do_something(*p);
}
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:
List_move_first(list);
while(!List_reached_end(list))
{
do_something(List_current(list));
List_move_next(list);
}
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));
}
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.
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.
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.
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).
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 .