Introduction to Linked List

Bisher hast du mit Arrays gearbeitet – einer einfachen und weit verbreiteten Datenstruktur in C. Arrays speichern mehrere Werte desselben Typs und ermöglichen den Zugriff über einen Index, was gut funktioniert, wenn die Anzahl der Elemente fest und im Voraus bekannt ist.

In realen Programmen ist jedoch oft mehr Flexibilität erforderlich. Die Datenmenge kann sich im Laufe der Zeit ändern, und das Einfügen oder Entfernen von Elementen in einem Array kann ineffizient sein. Arrays benötigen außerdem einen zusammenhängenden Speicherblock, was nicht immer praktikabel ist.

Um diese Einschränkungen zu überwinden, bietet C eine weitere grundlegende Struktur – die Linked List.

Was ist eine Linked List?

Wenn ein Array ein fester Speicherblock mit nebeneinander gespeicherten Elementen ist, dann ist eine Linked List eine Kette separater Knoten, die durch Zeiger miteinander verbunden sind.

Anstelle eines festen Layouts mit vordefinierter Größe wird die verkettete Liste dynamisch aufgebaut – Knoten werden während der Programmausführung einzeln erstellt, und jeder Knoten ist mit dem nächsten verbunden.

Arrays vs. verkettete Listen

Verkettete Listen sind eine natürliche Wahl in Situationen, in denen die Datenstruktur flexibel sein muss. Sie eignen sich gut, wenn sich die Anzahl der Elemente zur Laufzeit ändern kann, wenn Elemente eingefügt oder entfernt werden müssen, ohne dass unnötige Datenverschiebungen stattfinden, und wenn die Zuweisung eines großen zusammenhängenden Speicherblocks nicht ideal ist.