Zum Hauptinhalt springen

Array vs List vs LinkedList

Arrays​

  • Feste Größe: Die Größe eines Arrays muss beim Erstellen angegeben werden und kann später nicht geändert werden.
  • Kontinuierlicher Speicher: Alle Elemente eines Arrays werden in einem zusammenhängenden Speicherblock gespeichert, welcher bei der Initialisierung festgelegt wird.
    • Ein Array kann nicht vergrößert werden. Wenn man ein größeres Array benötigt, muss man ein neues Array erstellen, den Inhalt des alten Arrays kopieren und das neue Array verwenden. Dies ist jedoch keine automatische Funktionalität von Arrays, sondern muss manuell implementiert werden.

Beispiel:

int[] array = new int[5];
array[0] = 1;
array[1] = 2;

Vorteile​

  • Direkter Zugriff: Ermöglicht direkten Zugriff auf Elemente über ihren Index in konstanter Zeit.
  • Speichereffizienz: Sehr speichereffizienz, da nur der Speicher für die Elemente selbst benötigt wird.
  • Performance: Schneller Zugriff und Manipulation von Elementen, da sie in einem zusammenhängenden Speicherblock gespeichert sind.

Einsatzgebiete​

  • Geeignet für Szenarien, in denen die Anzahl der Elemente fest ist und sich nicht ändert.
  • Ideal für mathematische Operationen und Algorithmen, die auf feste Datensätze angewendet werden.
  • Perfekt für Situationen, in denen häufiger direkter Indexzugriff benötigt wird.

List<T>​

  • Variable Größe: Eine List<T> kann dynamisch wachsen und schrumpfen.
  • Kontinuierlicher Speicher: Ähnlich wie Arrays werden Elemente in einem zusammenhängenden Speicherblock gespeichert, aber die Liste kann sich vergrößern, indem sie intern ein neues, größeres Array erstellt und die alten Elemente kopiert.

Beispiel:

List<int> list = new List<int>();
list.Add(1);
list.Add(2);

Vorteile​

  • Dynamische Größe: Kann wachsen und schrumpfen, wenn Elemente hinzugefügt oder entfernt werden.
  • Direkter Zugriff: Bietet ebenfalls direkten Zugriff auf Elemente über ihren Index in konstanter Zeit.
  • Einfache Nutzung: Bietet eine Vielzahl nützlicher Methoden, wie Add, Remove, Insert, etc.

Einsatzgebiete:​

  • Geeignet für Szenarien, in denen die Anzahl der Elemente häufig ändert.
  • Ideal, wenn sowohl häufiger direkter Indexzugriff als auch das Einfügen und Entfernen von Elementen erforderlich sind.
  • Gut für Sammlungen, die sortiert oder gefiltert werden müssen.

LinkedList<T>​

  • Variable Größe: Eine LinkedList<T> kann ebenfalls dynamisch wachsen und schrumpfen.
  • Nicht-kontinuierlicher Speicher: Die Elemente (Knoten) werden nicht in einem zusammenhängenden Speicherblock gespeichert. Jeder Knoten enthält einen Verweis auf das nächste (und bei einer doppelt verketteten Liste auch das vorherige) Element.

Beispiel:

LinkedList<int> linkedList = new LinkedList<int>();
linkedList.AddLast(1);
linkedList.AddLast(2);

Einfügen von Elementen in eine LinkedList​

In die Liste wird ein zusätzlicher Knoten (Node) mit dem Namen X eingefügt

  1. Vor dem Einfügen:
  • Node A zeigt auf Node B.
  • Node B zeigt auf Node C.
  1. Nach dem Einfügen:
  • Node A zeigt auf Node X.
  • Node X zeigt auf Node B.
  • Node B zeigt weiterhin auf Node C.

Vorteile:​

  • Effizientes Einfügen und Entfernen: Das Einfügen und Entfernen von Elementen an beliebigen Positionen ist effizient (O(1)), wenn ein Verweis auf den Knoten vorhanden ist.
  • Doppelt verkettet: Kann als doppelt verkettete Liste implementiert werden, was bidirektionale Navigation ermöglicht.

Einsatzgebiete​

  • Geeignet für Szenarien, in denen häufige Einfügungen und Löschungen an beliebigen Positionen in der Liste erforderlich sind.
  • Ideal für Implementierungen von Warteschlangen (Queues) oder Stapeln (Stacks).
  • Perfekt für Anwendungen, bei denen die Elemente in einer sequentiellen Reihenfolge durchlaufen werden müssen, ohne häufigen direkten Indexzugriff.

Kommentare