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.