Siehe hierzu auch das Thema "Einfach verkettete Liste" an anderer Stelle.
Die zuvor betrachteten Datenstrukturen sehen entweder kein Einfügen oder Entfernen aus der Mitte vor (Stapel, Warteschlange) oder diese Vorgänge sind wenig effizient (Datenfeld).
Sobald eine Datenstruktur in irgendeiner Weise geordnet sein soll, werden in der Regel das Einfügen und Entfernen auch im "mittleren Bereich" dieser Datenstruktur benötigt.
Zum Beispiel "Lego-Simulation":
Will ein Anwender in eine Wand ein Fenster setzen, sind die dort befindlichen Steine "mitten aus der Wand" zu entfernen und dort ein Fenster einzufügen. Die Ordnung der Bauelemente könnte beim Fundament bzw. der Bodenplatte beginnen und beim Dachfirst enden.
Zum Beispiel "Kleine Adressendatenbank":
Damit ein Eintrag schnell auffindbar ist, können alle Einträge per Nachnamen alphabetisch (lexikografisch) geordnet vorliegen. Soll daraus der Eintrag einer verflossenen Liebschaft entfernt werden, so wird dies zumeist irgendwo im mittleren Bereich der Datenbank erfolgen. Entsprechend ist ein neuer Eintrag einzufügen.
Eine verkettete Liste beinhaltet Datenelemente, welche per Zeiger miteinander verkettet sind. Dies entspricht der Struktur einer Kette, deren Elemente die Kettenglieder sind oder einem Zug, deren Elemente die Waggons sind. Die Waggons sind per Kupplungen miteinander verkettet.
Die Elemente einer Kette und die eines Zuges liegen auch lokal nebeneinander. Die Elemente einer Liste können jedoch im Speicher verteilt liegen. Sie können dort nebeneinander liegen, müssen es aber nicht.
Die Lokation der Listenelemente im Speicher ist nicht relevant, weil jene durch Links (Zeiger) miteinander verbunden sind.
Anders als ein Element eines Datenfeldes benötigt ein Listenelement ein oder zwei zusätzliche Zeiger zum Verketten. Eine einfach verkettete Liste kommt mit einem Zeiger aus. Diese kann aber nur in einer Richtung durchlaufen werden. Eine doppelt verkettete Liste benötigt zwei Zeiger. Sie kann vorwärts und rückwärts durchlaufen werden.
Weil eine Liste keinen zusammenhängenden Speicher benötigt, ist kein wahlfreier Zugriff per Adresse möglich. Ein Einfügen oder Entfernen ist in einer Liste aber schnell durchführbar, weil hierzu nur die Zeiger anzupassen sind. Wenn Sie ein Glied aus einer Kette nehmen, brauchen Sie nur die beiden Nachbarglieder miteinander zu verbinden. Danach ist die Kette um ein Glied kürzer. Entsprechend geht es mit einem Listenelement und dessen Zeigern.
Eine Liste wächst oder schrumpft dynamisch zur Laufzeit. Sie hat anders als ein Datenfeld keine statische Größe, weil sie keinen zusammenhängenden Speicherbereich benötigt.
Fazit: