2.3. Linear lists (class list)

Like an array, a linear list stores a collection of objects of a certain type, usually denoted as the elements of the list. The elements are ordered within the linear list in a linear sequence. Linear lists are usually simply denoted as lists.

Unlike an array, a list is a data structure allowing insertion and deletion of elements at an arbitrary position of the sequence. If the position in question is given, for example by a reference, such a modification takes only a constant number of operations, that is, no effortful copying of entries is necessary and all insertion and deletion operations take an equally short time. Conversely, however, one cannot access a single element via an (integral) index in constant time, as in the case of an array, without having searched for it before and having received a reference to it. Furthermore, lists are not limited to a certain maximum number of elements from the beginning on (like an array). So they are a dynamic data structure.[13]

LEDA offers the very powerful class list for linear lists. This is one of the most important if not even the most important class of LEDA. For many users it is by far the class most frequently used. We will therefore discuss the class list thoroughly in this section.

[13] LEDA-arrays can likewise be considered as a dynamic structure thanks to resize(), but enlarging or shrinking takes hidden, non-constant time because there might be copying involved.