Container (Informatik)
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.
Speicher- und Rechenzeitbedarf
| Array | Dynamisches Array |
Verkettete Liste |
Balancierter Baum |
Hashtabelle | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Wahlfreier Zugriff | O(1) | O(1) | O(n) | O(log n)<ref>Wenn über Schlüssel oder Index.</ref> | N/A<ref>Nicht sinnvoll möglich, da die Reihenfolge in der Hashtabelle von der Hashfunktion abhängt.</ref> | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Einfügen/Löschen am Anfang | N/A | O(1)<ref name="amortisiert">amortisiert</ref><ref>Wenn ein zyklisches Array verwendet wird.</ref> | O(1) | O(log n) | O(1)<ref>amortisierte erwartete Laufzeit, zum Beispiel mit Kuckucks-Hashing.</ref> | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Einfügen/Löschen am Ende | N/A | O(1)<ref name="amortisiert" /> | O(1)<ref>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.</ref> | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Einfügen/Löschen mittig | N/A | O(n) | suche + O(1)<ref>Gerald Kruse. {{#switch: |
=Vorlage:Toter Link/Core{{#if: http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm | CS 240 Lecture Notes }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: 2018-04 | , festgestellt im {{#invoke:DateTime|format|2018-04|F Y}} }}. Suche im Internet Archive ){{#if: 2018-04-04 22:16:16 InternetArchiveBot | | Vorlage:Toter Link/archivebot }}
}} |
(Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: 2018-04 | , festgestellt im {{#invoke:DateTime|format|2018-04|F Y}} }}.)
}}{{#switch:
|
0|= | #default={{#if: | }}
}}{{#invoke:TemplatePar|check
|
opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= | cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link | errNS = 0 | template = Vorlage:Toter Link | format = | preview = 1
}}{{#if: http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm
|
isWebURL|http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm}} | {{#if: | }}
}} |
{{#if: CS 240 Lecture Notes | {{#if: | }} | {{#if: | }}
}}
}}{{#if: 2018-04
|
format|2018-04|F Y|noerror=1}} | {{#if: | }}
}}
}}{{#switch:
|
deadurl|= | #default= {{#if: | }}
}}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: 2018-04 | , festgestellt im {{#invoke:DateTime|format|2018-04|F Y}} }}. (Suche im Internet Archive. ) {{#if: 2018-04-04 22:16:16 InternetArchiveBot |
| Vorlage:Toter Link/archivebot }}
}}Vorlage:Toter Link/Core{{#switch: |
0|= | #default= {{#if: | }}
}}{{#invoke:TemplatePar|check
|
all = inline= url= | opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= | cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link | errNS = 0 | template = Vorlage:Toter Link | format = | preview = 1
}}{{#if: http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm
|
isWebURL|http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm}} | {{#if: | }}
}}
}}{{#if: 2018-04
|
format|2018-04|F Y|noerror=1}} | {{#if: | }}
}}
}}{{#switch:
|
deadurl|= | #default= {{#if: | }}
}}[http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm }}: {{#switch: |
=Vorlage:Toter Link/Core{{#if: http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm | Linked Lists Plus: Complexity Trade-offs }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if: 2018-04 | , festgestellt im {{#invoke:DateTime|format|2018-04|F Y}} }}. Suche im Internet Archive ){{#if: 2018-04-04 22:16:16 InternetArchiveBot | | Vorlage:Toter Link/archivebot }}
}} |
(Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if: 2018-04 | , festgestellt im {{#invoke:DateTime|format|2018-04|F Y}} }}.)
}}{{#switch:
|
0|= | #default={{#if: | }}
}}{{#invoke:TemplatePar|check
|
opt = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked= | cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link | errNS = 0 | template = Vorlage:Toter Link | format = | preview = 1
}}{{#if: http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm
|
isWebURL|http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm}} | {{#if: | }}
}} |
{{#if: Linked Lists Plus: Complexity Trade-offs | {{#if: | }} | {{#if: | }}
}}
}}{{#if: 2018-04
|
format|2018-04|F Y|noerror=1}} | {{#if: | }}
}}
}}{{#switch:
|
deadurl|= | #default= {{#if: | }}
}}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if: 2018-04 | , festgestellt im {{#invoke:DateTime|format|2018-04|F Y}} }}. (Suche im Internet Archive. ) {{#if: 2018-04-04 22:16:16 InternetArchiveBot |
| Vorlage:Toter Link/archivebot }}
}}Vorlage:Toter Link/Core{{#switch: |
0|= | #default= {{#if: | }}
}}{{#invoke:TemplatePar|check
|
all = inline= url= | opt = datum= date= archivebot= bot= botlauf= fix-attempted= checked= | cat = Wikipedia:Vorlagenfehler/Vorlage:Toter Link | errNS = 0 | template = Vorlage:Toter Link | format = | preview = 1
}}{{#if: http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm
|
isWebURL|http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm}} | {{#if: | }}
}}
}}{{#if: 2018-04
|
format|2018-04|F Y|noerror=1}} | {{#if: | }}
}}
}}{{#switch:
|
deadurl|= | #default= {{#if: | }}
}}[http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm }}. Juniata College. Spring 2008.</ref> |
| Suche | O(n) | O(n) | O(n) | O(log n) | O(1) | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Mittlerer Speicherplatzbedarf<ref>Gemeint ist der zusätzliche Speicherplatzbedarf. Er ist meist ein Bruchteil des ohnehin erforderlichen Speicherplatzbedarfs von O(n).</ref> | 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 <math>\mathcal{O}(1)</math> – eingefügt werden, die Suche nach bereits im Container eingelagerten Daten kann jedoch im ungünstigsten Fall <math>\mathcal{O}(n)</math> – 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 <math>\mathcal{O}(\log n)</math>. 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.
Siehe auch
Anmerkungen und Einzelnachweise
<references/>