Definition
An instance L of the parameterized data type list<E> is a sequence of items (list<E>::item). Each item in L contains an element of data type E, called the element or value 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/core/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
Update Operations
Sorting and Searching
void  L.sort(int (*cmp)(const E& , const E& ))  
sorts the items of L using the ordering defined
by the compare function
cmp : E x E int,
with
More precisely, if (in_{1},..., in_{n}) and (out_{1},..., out_{n}) denote the values of L before and after the call of sort, then cmp(L[out_{j}], L[out_{j+1}]) < = 0 for 1 < = j < n and there is a permutation of [1..n] such that out_{i} = in_{} for 1 < = i < = n. 

void  L.sort()  sorts the items of L using the default ordering of type E, i.e., the linear order defined by function int compare (const E&, const E&). If E is a userdefined type, you have to provide the compare function (see Section User Defined Parameter Types). 
void  L.merge_sort(int (*cmp)(const E& , const E& ))  
sorts the items of L using merge sort and the ordering defined by cmp. The sort is stable, i.e., if x = y and < x > is before < y > in L then < x > is before < y > after the sort. L.merge_sort() is more efficient than L.sort() if L contains large presorted intervals.  
void  L.merge_sort()  as above, but uses the default ordering of type E. If E is a userdefined type, you have to provide the compare function (see Section User Defined Parameter Types). 
void  L.bucket_sort(int i, int j, int (*b)(const E& ))  
sorts the items of L using bucket sort, where b maps every element x of L to a bucket b(x) [i..j]. If b(x) < b(y) then < x > appears before < y > after the sort. If b(x) = b(y), the relative order of x and y before the sort is retained, thus the sort is stable.  
void  L.bucket_sort(int (*b)(const E& ))  
sorts list<E> into increasing order as prescribed by b Precondition b is an integervalued function on E.  
()  merges the items of L and L1 using the ordering defined by
cmp. The result is assigned to L and L1 is made empty.
Precondition L and L1 are sorted incresingly according to the linear order defined by cmp. 

void  L.merge(list<E>& L1)  merges the items of L and L1 using the default linear order of type E. If E is a userdefined type, you have to define the linear order by providing the compare function (see Section User Defined Parameter Types). 
void  L.unique(int (*cmp)(const E& , const E& ))  
removes duplicates from L.
Precondition L is sorted incresingly according to the ordering defined by cmp. 

void  L.unique()  removes duplicates from L.
Precondition L is sorted increasingly according to the default ordering of type E and operator== is defined for E. If E is a userdefined type, you have to define the linear order by providing the compare function (see Section User Defined Parameter Types). 
list_item  L.search(const E& x)  returns the first item of L that contains x,
nil if x is not an element of L.
Precondition operator== has to be defined for type E. 
list_item  L.min(const leda_cmp_base<E>& cmp)  
returns the item with the minimal contents with respect to the linear order defined by compare function cmp.  
list_item  L.min()  returns the item with the minimal contents with respect to the default linear order of type E. 
list_item  L.max(const leda_cmp_base<E>& cmp)  
returns the item with the maximal contents with respect to the linear order defined by compare function cmp.  
list_item  L.max()  returns the item with the maximal contents with respect to the default linear order of type E. 
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 = const list<E>& 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 += const E& x  same as L.append(x); returns the new item. 
ostream&  ostream& out « const list<E>& 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. Let c be the time complexity of the compare function and let d be the time needed to copy an object of type list<E>. All operations take constant time except of the following operations: search, revers_items, permute and rank take linear time O(n), item(i) takes time O(i), min, max, and unique take time O(c*n), merge takes time O(c*(n1 + n2)), operator=, apply, reverse, read, and print take time O(d*n), sort and merge_sort take time O(n*c*log n), and bucket_sort takes time O(e*n + j  i), where e is the time complexity of f. n is always the current length of the list.