Beide speichern Sequenzen, haben aber entgegengesetzte Kostenprofile. Ein Array ist zusammenhängender Speicher mit O(1)-Indexierung; eine verknüpfte Liste ist verstreute Knoten, die durch Zeiger verbunden sind, mit O(1)-Einfügung/Löschung an den Enden, aber ohne Indexierung.
| Operation | Array (dynamisch) | Verknüpfte Liste |
|---|
| Zugriff nach Index | O(1) | O(n) |
| Suche | O(n) | O(n) |
| Einfügung/Löschung am Anfang | O(n) | O(1) |
| Einfügung/Löschung am Ende | O(1) amortisiert | O(1) mit tail ptr |
| Einfügung/Löschung in der Mitte | O(n) | O(n) Suche + O(1) splice |
| Speicheraufwand | niedrig | hoch (Zeiger pro Knoten) |
| Cache-Lokalität | ausgezeichnet | schlecht |
Array: [10][20][30][40] <- one contiguous block
Linked list: [10|*]->[20|*]->[30|null] <- scattered nodes
In der Praxis gewinnen Arrays die meiste Zeit, weil Cache-Lokalität Big-O-Unterschiede bei typischen Größen überwiegt.
Wenn Sie beide kennen, können Sie Ihre Wahl in Interviews begründen, statt blind anzunehmen — und erklären, warum "O(1)-Einfügung" ein zusammenhängendes Array selten schlägt.
Eine Sammlung von IT-Interviewfragen mit ausführlichen Antworten — vom Junior bis zum Senior.
Spenden