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?
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));
}
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.
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. The interface in list.h describes the checked runtime errors
your implementation should handle. Rather than using assertions to
check for these errors, you should use a conditional statement to check
for the error, and print a descriptive error message (write to stderr)
and exit if the error occurs.
You should create two executable versions of each test program, one
that links in your list.o, one that links in /u/cs217/Assignment4/list.o,
and compare the output produced by each program. You do not need
to turn in your test programs; however in grading your assignment your
list.c implementation will be evaluated in how it handles the checked runtime
errors.
/u/cs217/bin/submit 4 list.c readmeYou may use other computing facilities to develop your program, but the submitted version must compile with lcc and execute correctly on the arizona machines.
The ideas presented here were taken from the book C++
Programmer's Guide to the Standard Template Library .
Special thanks to Yefim Shuf