Inserting and removing elements
void listDestroy()
DLLIST *listAddToHead()
l_int32 listAddToTail()
l_int32 listInsertBefore()
l_int32 listInsertAfter()
void *listRemoveElement()
void *listRemoveFromHead()
void *listRemoveFromTail()
Other list operations
DLLIST *listFindElement()
DLLIST *listFindTail()
l_int32 listGetCount()
l_int32 listReverse()
DLLIST *listJoin()
Lists are much harder to handle than arrays. There is
more overhead for the programmer, both cognitive and
codewise, and more likelihood that an error can be made.
For that reason, lists should only be used when it is
inefficient to use arrays, such as when elements are
routinely inserted or deleted from inside arrays whose
average size is greater than about 10.
A list of data structures can be implemented in a number
of ways. The two most popular are:
(1) The list can be composed of a linked list of
pointer cells ("cons cells"), where the data structures
are hung off the cells. This is more difficult
to use because you have to keep track of both
your hanging data and the cell structures.
It requires 3 pointers for every data structure
that is put in a list. There is no problem
cloning (using reference counts) for structures that
are put in such a list. We implement lists by this
method here.
(2) The list pointers can be inserted directly into
the data structures. This is easy to implement
and easier to use, but it adds 2 ptrs of overhead
to every data structure in which the ptrs are embedded.
It also requires special care not to put the ptrs
in any data that is cloned with a reference count;
else your lists will break.
Writing C code that uses list pointers explicitly to make
and alter lists is difficult and prone to error.
Consequently, a generic list utility that handles lists
of arbitrary objects and doesn't force the programmer to
touch the "next" and "prev" pointers, is quite useful.
Such functions are provided here. However, the usual
situation requires traversing a list and applying some
function to one or more of the list elements. Macros
for traversing the list are, in general, necessary, to
achieve the goal of invisibly handling all "next" and "prev"
pointers in generic lists. We provide macros for
traversing a list in both forward and reverse directions.
Because of the typing in C, implementation of a general
list utility requires casting. If macros are used, the
casting can be done implicitly; otherwise, using functions,
some of the casts must be explicit. Fortunately, this
can be implemented with void* so the programmer using
the library will not have to make any casts! (Unless you
compile with g++, in which case the rules on implicit
conversion are more strict.)
For example, to add an arbitrary data structure foo to the
tail of a list, use
listAddToTail(&head, &tail, pfoo);
where head and tail are list cell ptrs and pfoo is
a pointer to the foo object.
And to remove an arbitrary data structure foo from a
list, when you know the list cell element it is hanging from,
use
pfoo = listRemoveElement(&head, elem)
where head and elem are list cell ptrs and pfoo is a pointer
to the foo object. No casts are required for foo in
either direction in ANSI C. (However, casts are
required for ANSI C++).
We use lists that are composed of doubly-linked
cells with data structures hanging off the cells.
We use doubly-linked cells to simplify insertion
and deletion, and to allow operations to proceed in either
direction along the list. With doubly-linked lists,
it is tempting to make them circular, by setting head->prev
to the tail of the list and tail->next to the head.
The circular list costs nothing extra in storage, and
allows operations to proceed from either end of the list
with equal speed. However, the circular link adds
cognitive overhead for the application programmer in
general, and it greatly complicates list traversal when
arbitrary list elements can be added or removed as you
move through. It can be done, but in the spirit of
simplicity, we avoid the temptation. The price to be paid
is the extra cost to find the tail of a list -- a full
traversal -- before the tail can be used. This is a
cheap price to pay to avoid major headaches and buggy code.
When you are only applying some function to each element
in a list, you can go either forwards or backwards.
To run through a list forwards, use:
for (elem = head; elem; elem = nextelem) {
nextelem = elem->next; (in case we destroy elem)
<do something with elem->data>
}
To run through a list backwards, find the tail and use:
for (elem = tail; elem; elem = prevelem) {
# prevelem = elem->prev; (in case we destroy elem)
<do something="" with="" elem->="">data>
}
Even though these patterns are very simple, they are so common
that we've provided macros for them in list.h. Using the
macros, this becomes:
<do something with elem->data>
<do something with elem->data>
Note again that with macros, the application programmer does
not need to refer explicitly to next and prev fields. Also,
in the reverse case, note that we do not explicitly
show the head of the list. However, the head of the list
is always in scope, and functions can be called within the
iterator that change the head.
Some special cases are simpler. For example, when
removing all items from the head of the list, you can use
while (head) {
<do something with obj>
}
Removing successive elements from the tail is equally simple:
while (tail) {
<do something with obj>
}
When removing an arbitrary element from a list, use
All the listRemove*() functions hand you the object,
destroy the list cell to which it was attached, and
reset the list pointers if necessary.
Several other list operations, that do not involve
inserting or removing objects, are also provided.
The function listFindElement() locates a list pointer
by matching the object hanging on it to a given
object. The function listFindTail() gets a handle
to the tail list ptr, allowing backwards traversals of
the list. listGetCount() gives the number of elements
in a list. Functions that reverse a list and concatenate
two lists are also provided.
These functions can be modified for efficiency in the
situation where there is a large amount of creation and
destruction of list cells. If millions of cells are
made and destroyed, but a relatively small number are
around at any time, the list cells can be stored for
later re-use in a stack (see the generic stack functions
in stack.c).
Definition in file list.c.