Container (Informatik)

Ein Container (auch Collection) i​n der Informatik i​st ein abstraktes Objekt, d​as Elemente d​es gleichen Typs speichert. Je n​ach Anforderungen verwendet m​an dabei unterschiedliche Datenstrukturen, u​m einen Container z​u realisieren. Beispiele für Container s​ind Arrays o​der Listen, e​ine detailliertere Auflistung i​st auf d​er Seite d​er Datenstrukturen z​u finden.

Speicher- und Rechenzeitbedarf
Speicher- und Rechenzeitbedarf
  Array Dynamisches
Array		 Verkettete
Liste		 Balancierter
Baum		 Hashtabelle
Wahlfreier Zugriff O(1) O(1) O(n) O(log n)[1] N/A[2]
Einfügen/Löschen am Anfang N/A O(1)[3][4] O(1) O(log n) O(1)[5]
Einfügen/Löschen am Ende N/A O(1)[3] O(1)[6]
Einfügen/Löschen mittig N/A O(n) suche +
O(1)[7]
Suche O(n) O(n) O(n) O(log n) O(1)
Mittlerer Speicherplatzbedarf[8] 0 O(n) O(n) O(n) O(n)

Die verschiedenen Datenstrukturen haben unterschiedliche Eigenschaften in Bezug auf Speicher- und Rechenzeitbedarf beim Einfügen neuer Elemente, Löschen bereits in der Datenstruktur vorhandener Elemente oder der Suche nach einem bestimmten Element. In Arrays und Listen kann Neues in konstanter Zeit – in Landau-Notation – eingefügt werden, die Suche nach bereits im Container eingelagerten Daten kann jedoch im ungünstigsten Fall – ein Sichten des gesamten Datenbestands – erfordern.

Wird als Container hingegen ein balancierter Baum, wie AVL- oder Rot-Schwarz-Bäume, verwendet, erfordern alle Operationen Zeit . Für eine Suche muss nur noch ein kleiner Teil des Datenbestands gesichtet werden, das Einfügen neuer Daten hingegen erfordert einen etwas größeren Aufwand.

Anmerkungen und Einzelnachweise
  1. Wenn über Schlüssel oder Index.
  2. Nicht sinnvoll möglich, da die Reihenfolge in der Hashtabelle von der Hashfunktion abhängt.
  3. amortisiert
  4. Wenn ein zyklisches Array verwendet wird.
  5. amortisierte erwartete Laufzeit, zum Beispiel mit Kuckucks-Hashing.
  6. Unter der Annahme, dass die verlinkte Liste sich einen Pointer der Datenendposition merkt, sonst muss erst das Ende der Liste mit dem Zeitaufwand O(n) ermittelt werden.
  7. Gerald Kruse. CS 240 Lecture Notes@1@2Vorlage:Toter Link/www.juniata.edu (Seite nicht mehr abrufbar, Suche in Webarchiven)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis. : Linked Lists Plus: Complexity Trade-offs@1@2Vorlage:Toter Link/www.juniata.edu (Seite nicht mehr abrufbar, Suche in Webarchiven)  Info: Der Link wurde automatisch als defekt markiert. Bitte prüfe den Link gemäß Anleitung und entferne dann diesen Hinweis. . Juniata College. Spring 2008.
  8. Gemeint ist der zusätzliche Speicherplatzbedarf. Er ist meist ein Bruchteil des ohnehin erforderlichen Speicherplatzbedarfs von O(n).

Siehe auch
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.