Informatik Datenstrukturen – Arrays und verkettete Listen
Karteikarten zum Thema „Informatik“ · 13 Karten · von atrio. Beispiele: Was ist ein Array in der Informatik? · Was ist eine einfach verkettete Liste?
Karten
13 KartenWas ist ein Array in der Informatik?
Rückseite
Ein Array ist ein zusammenhängender Speicherblock fester Größe, der Elemente gleichen Typs über einen Index direkt adressierbar speichert.
Was ist eine einfach verkettete Liste?
Rückseite
Eine verkettete Liste besteht aus Knoten, die jeweils ein Datenelement und einen Pointer auf den nächsten Knoten enthalten – der Speicher muss nicht zusammenhängend sein.
Wie lautet die Laufzeitkomplexität für den wahlfreien Zugriff per Index im Array?
Rückseite
O(1), da die Speicheradresse durch Basisadresse plus Index mal Elementgröße direkt berechnet wird.
Wie lautet die Laufzeitkomplexität für den Zugriff per Index in einer verketteten Liste?
Rückseite
O(n), da vom Head-Knoten ausgehend der Pointer-Kette gefolgt werden muss, bis der gewünschte Index erreicht ist.
Wie effizient ist das Einfügen am Anfang eines Arrays?
Rückseite
O(n), weil alle bestehenden Elemente um eine Position nach rechts verschoben werden müssen, um Platz zu schaffen.
Wie effizient ist das Einfügen am Anfang einer verketteten Liste?
Rückseite
O(1), da nur der neue Knoten als neuer Head eingetragen und sein Next-Pointer auf den alten Head gesetzt wird.
Wie effizient ist das Anhängen an ein Array mit freier Kapazität am Ende?
Rückseite
O(1) amortisiert, da das Element einfach an den nächsten freien Index geschrieben wird – bei Kapazitätsüberschreitung erfolgt Reallokation und Kopie.
Wie effizient ist das Anhängen an eine verkettete Liste ohne Tail-Pointer?
Rückseite
O(n), weil die gesamte Liste durchlaufen werden muss, um den letzten Knoten zu finden, bevor der neue Knoten angehängt wird.
Wie effizient ist das Löschen eines Elements an bekanntem Index im Array?
Rückseite
O(n), da alle nachfolgenden Elemente um eine Position nach links verschoben werden müssen, um die Lücke zu schließen.
Wie effizient ist das Löschen eines Knotens in einer verketteten Liste, wenn der Vorgänger bekannt ist?
Rückseite
O(1), da nur der Next-Pointer des Vorgängers auf den Nachfolger des zu löschenden Knotens umgebogen wird.
Welchen Speicheroverhead hat eine verkettete Liste gegenüber einem Array?
Rückseite
Pro Knoten wird ein zusätzlicher Pointer (4–8 Byte) benötigt, während Arrays nur die reinen Nutzdaten speichern.
Warum profitieren Arrays von besserer Cache-Lokalität als verkettete Listen?
Rückseite
Arrays liegen zusammenhängend im Speicher, sodass benachbarte Elemente bei einem Cache-Miss gemeinsam in die Cache-Line geladen werden – bei Listen sind Knoten verstreut.
Wann ist ein Array einer verketteten Liste vorzuziehen?
Rückseite
Bei häufigem wahlfreiem Zugriff, bekanntem maximalen Größenbedarf und wenn Cache-Performance kritisch ist – z. B. bei Lookup-Tabellen oder festen Puffern.