eine dynamische Datenstruktur mit variabler Länge.

Will man eine flexible maschinelle Listenverarbeitung entwickeln, so verwendet man in der Regel verkettete Listen. Bei vorwärts verketteten Listen bestehen die Elemente der Liste, die sogenannten Knoten, aus zwei Komponenten. Die erste Komponente trägt die eigentliche Information, während die zweite Komponente einen Verweis auf das nächste Listenelement enthält. Sobald man über einen Einstiegspunkt in den Anfang der Liste verfügt, kann man also mit Hilfe der in den Knoten abgelegten Referenzen die gesamte Liste durchlaufen. Darüber hinaus ist die Länge der Liste nicht zum Zeitpunkt der Kompilierung festgelegt, sondern kann jederzeit erweitert oder auch verringert werden.

In Analogie zu einer vorwärts verketteten Liste trägt bei einer rückwärts verketteten Liste die zweite Komponente einen Verweis auf das vorhergehende Element. Für komplexe Verarbeitungen kann es auch sinnvoll sein, sowohl auf das vorhergehende als auch auf das nachfolgende Element zu verweisen. In diesem Fall spricht man von einer doppelt verketteten Liste, deren Knoten aus drei Komponenten bestehen.