Container (Informatik)

Ein Container 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 Array oder Liste, eine detailliertere Auflistung ist auf der Seite der Datenstrukturen zu finden.

Speicher- und Rechenzeitbedarf

Speicher- und Rechenzeitbedarf

	Array	Dynamisches Array	Verlinkte Liste	Balancierter Baum	Hashtabelle
Indizierung	Θ(1)	Θ(1)	Θ(n)	Θ(n)	Θ(n)
Einfügung/Löschung am Anfang	N/A	Θ(n)	Θ(1)	Θ(log n)	Θ(1) bis Θ(n)[1]
Einfügung/Löschung am Ende	N/A	Θ(1)	Θ(1)[2]
Einfügung/Löschung mittig	N/A	Θ(n)	suche + Θ(1)[3]
Suche	Θ(n)	Θ(n)	Θ(n)	Θ(log n)	Θ(1) bis Θ(n)
Mittlere Speicherplatz- verschwendung	0	0 (Θ(n)[4])	Θ(n)	Θ(n)	Θ(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 $\mathcal{O}(1)$ – eingefügt werden, die Suche nach bereits im Container eingelagerten Daten kann jedoch im ungünstigsten Fall Θ(n) – 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 $\mathcal{O}(\log n)$ – für eine Suche muss nur noch ein kleiner Teil des Datenbestands gesichtet werden, Einfügen neuer Daten hingegen erfordert einen etwas größeren Aufwand.

Belege

1. ↑ Dan Schmidt The Perl Journal 1999: Building a Better Hash
2. ↑ Unter der Annahme, dass die verlinkte Liste sich einen Pointer der Datenendposition merkt, sonst muss erst das Ende der Liste mit dem Zeitaufwand Θ(n) ermittelt werden.
3. ↑ Gerald Kruse. CS 240 Lecture Notes: Linked Lists Plus: Complexity Trade-offs. Juniata College. Spring 2008.
4. ↑ Unter der Annahme, dass ein Puffer für Erweiterungen vorgehalten wird, sonst 0.

Siehe auch

• Containerformat
• Container (Begriffsklärung)