2.3.7. Further information and tips

2.3.7. Further information and tips
	2.3. Linear lists (class list)

Further information about the class `list`

The class list has a large interface with many methods. In this introduction we could describe only the most important ones.

For example, min() and max() return an item which refers to the minimum and maximum, respectively, of the values stored in a list (regarding the default order compare()). The method print() has a sister method read(), which can be parameterized in many different ways. The bounds of the interval [l..r] can be passed to the method bucket_sort() if they are already known, and similar more.

The corresponding manual page gives more detailed information about all these methods and possibilities.

Implementation

The class list is implemented by doubly linked linear lists.

If a list contains n elements of type T and c is the time it takes to compare two objects of type T, the following asymptotic running times hold:

O(n): search(), reverse_items(), permute().
O(c·n): min(), max(), unique().
O(c·(n1+n2)): merge().
O(k·n): operator=(), apply(), reverse(), read(), print(); here, k is the time it takes to copy an object of type T.
O(d·n): clear(); here, d is the time it takes to destroy an object of type T.
O(c·n·log(n)): sort(), merge_sort().
O(e·n+(r-l)): bucket_sort(); here, e is the time it takes to apply function f (which computes the bucket numbers) to an object of type T.
O(1): all other operations.

Tips for the use of doubly linked lists

The class list is the structure of choice if objects must be stored in a linear sequence and if a new object must frequently be inserted or deleted in front of or behind a certain object.
If one does not need direct access to the predecessor of a container, an slist is more storage efficient than a list.
If one must often search for elements, a set may rather be the structure of choice. This primarily holds when no good “starting point” is known for the search.
If elements must be accessed via their position (that is their index in the sequence), an array can be more useful.


2.3.6. Copying and comparing item-based types and item types		2.3.8. Singly linked lists (class slist)