Loading AI tools
abstraktes Objekt, das Elemente des gleichen Typs speichert Aus Wikipedia, der freien Enzyklopädie
Ein Container (auch Collection) in der Informatik ist ein abstraktes Objekt, das Elemente des gleichen Typs speichert. Je nach Anforderungen verwendet man dabei unterschiedliche Datenstrukturen, um einen Container zu realisieren. Beispiele für Container sind Arrays oder Listen, eine detailliertere Auflistung ist auf der Seite der Datenstrukturen zu finden.
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.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.