| Table of Contents | ChiLib Library Documentation |
List<T> is a template to construct a linked list of elements of type T. T can be any type--numerical, pointer or class.
The default constructor constructs an empty list. The empty operation empties an existing list. The length operation returns the number of elements currently stored in the list.
Lists are copied by value. To keep the code simple and understandable, copy on write is not used. Therefore copies get expensive, and you should pass lists (and objects containing lists) by constant reference, not by value, to functions that do not change them.
void insert_head(T t);
void insert_tail(T t);
T remove_head();
T remove_tail();
T head() const;
T tail() const;
This class allows editing at both the head and the tail of the list. The insert_head operation makes a new link containing t that becomes the head of the list. The insert_tail operation makes a new link containing t that becomes the tail of the list. The head and tail operations report the contents of the head and the tail, whereas remove_head and remove_tail return and remove the head or tail.
This portion of the interface implements a deque (a double-ended queue).
What distinguishes a list from a deque is the ability to inspect and modify arbitrary elements inside it. For this purpose, each list object contains a cursor--a pointer to a current element.
void insert(T t); // insert before current position
T remove(); // remove current position
T current() const; // contents of current element
T& current(); // reference to current element
These operations insert and remove elements at the cursor position. To see the interaction between the cursor and the inserted or removed element, think of the cursor on a terminal. Insertion inserts before the cursor, and removal deletes the element under the cursor and moves the cursor to the next element. It is legal to insert when the cursor is at the end of the list. A list with n elements has n + 1 cursor positions: before each element and after the last one.
void reset();
void next(); // advance cursor to next position
Bool at_end() const;
These operations move the cursor and test whether it is already at the end of the list. Advancing past the end has no effect.
The typical traversal loop has the form
for (l.reset(); !l.at_end(); l.next())
do something with l.current();
Using the cursor to traverse a list has one disadvantage: it modifies the list. In particular, a function receiving a constant reference to a list cannot modify the cursor. The solution is to attach an external iterator, an object that can traverse a list without modifying it.
ListIterator<T> is a template for iterators through List<T> lists. (It would make more sense if each list class had a nested class List<T>::Iterator, but that broke several template implementations.)
ListIterator(const List<T>&);
void next(); // advance cursor to next position
void reset();
Bool at_end() const;
T current() const; // contents of current element
An iterator is constructed from a list. It starts out pointing to the first list element. Its cursor is controlled just as the list cursor. The typical traversal loop is
for (ListIterator<T> it(l); !it.at_end(); it.next())
do something with it.current();
Any number of iterators can be attached to a list. The iterators can only be used to inspect the list contents, not to modify it.
If a list is edited (through insert, remove), emptied or destroyed, all iterators to it are in an unstable state. If the list still exists, invoke reset on the iterator before using it again. If the list has been destroyed, the iterator can no longer be used. A professional implementation would implement communication between the list and its iterators, but that was omitted to keep the code simple and understandable.