Wie ein Array speichert auch eine lineare Liste eine Ansammlung von Objekten eines bestimmten Typs, meist als Elemente der Liste bezeichnet. Die Elemente sind innerhalb der linearen Liste in einer linearen Abfolge angeordnet. Meist werden lineare Listen einfach als „Liste“ bezeichnet.

Im Gegensatz zu einem Array ist eine Liste eine Datenstruktur, die Einfügen und Löschen von Elementen an einer beliebigen Stelle in der Folge der Elemente erlaubt. Ist die betreffende Stelle gegeben, etwa durch eine Referenz darauf, so benötigt eine solche Änderung nur konstant viele Operationen, d. h., es ist kein zeitaufwändiges Umkopieren von Einträgen nötig, und alle Einfüge- und Löschoperationen dauern gleich lang. Umgekehrt kann aber auf ein einzelnes Element nicht - wie bei einem Array - in konstanter Zeit über einen (ganzzahligen) Index zugegriffen werden, jedenfalls nicht, ohne vorher danach gesucht und eine Referenz darauf erhalten zu haben. Darüber hinaus sind Listen nicht (wie ein Array) von vorneherein auf eine bestimmte Höchstanzahl von Elementen festgelegt. Sie sind also eine dynamische Datenstruktur.^[13]

LEDA bietet für lineare Listen die sehr mächtige Klasse list an. Diese ist eine der wichtigsten, wenn nicht sogar die wichtigste Klasse von LEDA. Bei vielen Anwendern ist es die mit Abstand am häufigsten eingesetzte Klasse. Wir werden uns daher im Folgenden eingehend mit der Klasse list beschäftigen.