The Linked List

Eine Linked List ist, wie der Name schon sagt, eine Liste von verknüpften/verketteten Elementen. Diese Datenstruktur ist, nach den Arrays, die zweithäufigst genutze Struktur. Linked Lists wachsen und schrumpfen automatisch, brauchen aber auch mehr Speicherplatz. Jedes Element zeigt auf den nächsten Knoten in der Liste. Stell dir eine verlinkte Liste als Schnitzeljagd vor. Du beginnst mit einem Hinweis (dem "Head" der Liste) und jeder Hinweis führt dich zum nächsten Hinweis (dem nächsten Zeiger), bis du am Ende der Liste angelangt bist (dem "Tail").

Einige häufige Gründe für die Verwendung von verknüpften Listen sind:

Einfügen von Elementen in die Mitte der Daten:
Wir können überall in der Liste einfügen, solange wir den Knoten vor dem Einfügeindex kennen.
O(n) in einem Vektor, O(1) in einer verknüpften Liste.

Schnelleres Erweitern des Speicherplatzes für unsere Daten:
Da sich Linked Lists auf diese Idee der Verwendung von Zeigern konzentrieren, müssen wir unseren Daten keine zusammenhängenden Speicherblöcke zuweisen. Dies spart uns O(n) Zeit.

Ein großer Nachteil von verknüpften Listen besteht darin, dass wir keinen wahlfreien Zugriff auf ein Element in der Liste über seinen Index haben.
Beispiel: Wenn wir das 5. Element in einer Liste abrufen wollten, müssten wir die Liste durchlaufen, bis wir darauf gestoßen sind.

Search by Index: O(n)
by Value: O(n)

Insert Beginning/End: O(1)
Middle: O(n)

Delete Beginning: O(1)
Middle: O(n)
End: O(n)

Link List - Typen

Singly - Vom Ende löschen (O (n))
Doubly - Vom Ende löschen (O (1), brauchen mehr Space, da sie einen Link zum Vorgänger-Knoten haben)
Circular - der letzte Knoten referenziert den ersten Knoten (z.B. bei einer sich wiederholenden Spotify-Playlist)