Definition
An instance L of the parameterized data type list<E> is a sequence of items (list_item). Each item in L contains an element of data type E, called the element type of L. The number of items in L is called the length of L. If L has length zero it is called the empty list. In the sequel < x > is used to denote a list item containing the element x and L[i] is used to denote the contents of list item i in L.
#include < LEDA/list.h >
Types
list<E>::item | the item type. |
list<E>::value_type | the value type. |
Creation
list<E> | L | creates an instance L of type list<E> and initializes it to the empty list. |
Operations
Access Operations
int | L.length() | returns the length of L. |
int | L.size() | returns L.length(). |
bool | L.empty() | returns true if L is empty, false otherwise. |
list_item | L.first() | returns the first item of L (nil if L is empty). |
list_item | L.last() | returns the last item of L. (nil if L is empty) |
list_item | L.get_item(int i) | returns the item at position i (the first position is 0).
Precondition 0 < = i < L.length(). Note that this takes time linear in i. |
list_item | L.succ(list_item it) | returns the successor item of item it, nil if
it = L.last().
Precondition it is an item in L. |
list_item | L.pred(list_item it) | returns the predecessor item of item it, nil if
it = L.first().
Precondition it is an item in L. |
list_item | L.cyclic_succ(list_item it) | |
returns the cyclic successor of item it, i.e., L.first() if it = L.last(), L.succ(it) otherwise. | ||
list_item | L.cyclic_pred(list_item it) | |
returns the cyclic predecessor of item it, i.e, L.last() if it = L.first(), L.pred(it) otherwise. | ||
E | L.contents(list_item it) | returns the contents L[it] of item it.
Precondition it is an item in L. |
E | L.inf(list_item it) | returns L.contents(it). |
E | L.front() | returns the first element of L, i.e. the contents
of L.first().
Precondition L is not empty. |
E | L.head() | same as L.front(). |
E | L.back() | returns the last element of L, i.e. the contents
of L.last().
Precondition L is not empty. |
E | L.tail() | same as L.back(). |
int | L.rank(E x) | returns the rank of x in L, i.e. its first position in L as an integer from [1...| L|] (0 if x is not in L). Note that this takes time linear in rank(x). Precondition compare has to be defined for type E. |
Update Operations
Sorting and Searching
Input and Output
void | L.read(istream& I) | reads a sequence of objects of type E from the input stream I using operator>>(istream&,E&). L is made a list of appropriate length and the sequence is stored in L. |
void | L.read(istream& I, char delim) | |
as above but stops reading as soon as the first occurence of character delim is encountered. | ||
void | L.read(char delim = ' \n') | calls L.read(cin, delim) to read L from the standard input stream cin. |
void | L.read(string prompt, char delim = ' \n') | |
As above, but first writes string prompt to cout. | ||
void | L.print(ostream& O, char space = ' ') | |
prints the contents of list L to the output tream O using operator<<(ostream&,const E&) to print each element. The elements are separated by character space. | ||
void | L.print(char space = ' ') | calls L.print(cout, space) to print L on the standard output stream cout. |
void | L.print(string header, char space = ' ') | |
As above, but first outputs string header. |
Operators
list<E>& | L = L1 | The assignment operator makes L a copy of list L_{1}. More precisely if L_{1} is the sequence of items x_{1}, x_{2},..., x_{n} then L is made a sequence of items y_{1}, y_{2},..., y_{n} with L[y_{i}] = L_{1}[x_{i}] for 1 < = i < = n. |
E& | L[list_item it] | returns a reference to the contents of it. |
list_item | L[int i] | an abbreviation for L.get_item(i). |
list_item | L += E x | same as L.append(x); returns the new item. |
ostream& | ostream& out << L | same as L.print(out); returns out. |
istream& | istream& in >> list<E>& L | same as L.read(in)); returns in. |
Iteration
forall_items(it, L) { ``the items of L are successively assigned to it'' }
forall(x, L) { ``the elements of L are successively assigned to x'' }
STL compatible iterators are provided when compiled with -DLEDA_STL_ITERATORS (see LEDAROOT/demo/stl/list.c for an example).
Implementation
The data type list is realized by doubly linked linear lists. All operations take constant time except for the following operations: search and rank take linear time O(n), item(i) takes time O(i), bucket_sort takes time O(n + j - i) and sort takes time O(n*c*log n) where c is the time complexity of the compare function. n is always the current length of the list.