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.
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.
 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