mibeon
/ Datenstrukturen

Linked List Zugriffszeit

Anzahl Schritte zum Erreichen eines Elements in einer einfach verketteten Liste: Schritte = Index. Lineare Zeit O(n).

Linked List Zugriffszeit
01 · Eingabe

Linked List Zugriffszeit berechnen

Anzahl Schritte zum Erreichen eines Elements in einer einfach verketteten Liste: Schritte = Index. Lineare Zeit O(n).

Lösen für
Schritte = Index

Worum geht es?

Eine einfach verkettete Liste speichert ihre Elemente nicht zusammenhängend, sondern in über Zeiger verknüpften Knoten. Um Element n zu erreichen, musst Du den next-Zeiger n-mal verfolgen — es gibt keinen Random Access.

Daraus folgt: Schritte = Index und damit eine Zugriffskomplexität von O(n). Dafür sind Einfügen und Löschen an bekannter Position O(1) — der Trade-off gegenüber dem Array.

Die Formel

Formel Traversierung 
Schritte = Index

Umstellung:
    Index = Schritte

Die Variablen

SymbolBedeutungEinheitErklärung
IndexIndex—Zielposition (0-basiert).
SchritteSchritte—Anzahl next-Dereferenzierungen.

Minimal-Beispiel

Zugriff auf das 5. Element (Index 4):

Rechnung Element 4 
Schritte = 4

Praxis-Beispiele

Beispiel 1 — Mittlere Suche

Bei einer Liste mit 1000 Elementen ist der durchschnittliche Zugriff:

Rechnung Mittelwert 
Schritte_mittel = (n − 1) / 2
                = 999 / 2
                ≈ 500 Schritte

Beispiel 2 — Array vs. Linked List

Tabelle für Zugriff auf das letzte Element bei n = 10⁶:

Rechnung Vergleich 
Array:       1 Schritt   (O(1))
Linked List: 999 999 Schritte (O(n))

Beispiel 3 — Doppelt verkettete Liste

Eine doppelt verkettete Liste mit Head- und Tail-Zeiger erreicht das letzte Element in einem Schritt — die Formel gilt nur für einseitige Traversierung von Head aus.