Lineare Liste

Eine Lineare Liste ist eine Ansammlung von Objekten, die auch Elemente genannt. Die Elemente sind innerhalb der linearen Liste in einer linearen Abfolge angeordnet(ein Element hat genau einen Nachfolger). Meist werden lineare Listen einfach als „Liste“ bezeichnet.

Vergleich mit dem Array

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. Deshalb wird sie auch als dynamische Datenstruktur bezeichnet.

Typen

Man unterscheidet zwischen einfach und doppelten (mehrfach) verketteten Listen.