imported>TaxonBot: Bot: Auflösung doppelter toter Links nach https://de.wikipedia.org/w/index.php?title=Wikipedia:Bots/Anfragen&oldid=266185123#Aufl%C3%B6sung_der_doppelten_Toten_Links

2026-04-16T16:21:48Z

Bot: Auflösung doppelter toter Links nach https://de.wikipedia.org/w/index.php?title=Wikipedia:Bots/Anfragen&oldid=266185123#Aufl%C3%B6sung_der_doppelten_Toten_Links

Neue Seite

Ein '''Container''' (auch '''Collection''') in der [[Informatik]] ist ein abstraktes Objekt, das Elemente des gleichen Typs speichert. Je nach Anforderungen verwendet man dabei unterschiedliche [[Datenstruktur]]en, um einen Container zu realisieren. Beispiele für Container sind [[Feld (Datentyp)|Arrays]] oder [[Liste (Datenstruktur)|Listen]], eine detailliertere Auflistung ist auf der Seite der Datenstrukturen zu finden.

== Speicher- und Rechenzeitbedarf ==

{|class="wikitable centered"
|+ Speicher- und Rechenzeitbedarf
!  
! valign="top" | [[Feld (Datentyp)|Array]]
! valign="top" | Dynamisches<br />Array
! valign="top" | Verkettete<br />[[Liste (Datenstruktur)|Liste]]
! valign="top" | Balancierter<br />[[balancierter Baum|Baum]]
! valign="top" | [[Hashtabelle]]
|-
| valign="top" | '''[[Wahlfreier Zugriff]]'''
| style="background:#ddffdd; text-align:center" |O(1)
| style="background:#ddffdd; text-align:center" |O(1)
| style="background:#ffdddd; text-align:center" |O(''n'')
| style="background:#ffdddd; text-align:center" |O(''log n'')<ref>Wenn über [[Binärer Suchbaum|Schlüssel]] oder [[Binärbaum#Repräsentation und Zugriff|Index]].</ref>
| style="background:#ffdddd; text-align:center" |''N/A''<ref>Nicht sinnvoll möglich, da die Reihenfolge in der Hashtabelle von der Hashfunktion abhängt.</ref>
|-
| valign="top" | '''Einfügen/Löschen am Anfang'''
| style="background:#ffdddd; text-align:center" |''N/A''
| style="background:#ddffdd; text-align:center" |O(1)<ref name="amortisiert">[[Amortisierte Laufzeitanalyse|amortisiert]]</ref><ref>Wenn ein zyklisches Array verwendet wird.</ref>
| style="background:#ddffdd; text-align:center" |O(1)
| rowspan="3" style="background:#ffffdd; text-align:center" |O(''log n'')
| rowspan="3" style="background:#ddffdd; text-align:center" |O(''1'')<ref>amortisierte erwartete Laufzeit, zum Beispiel mit [[Kuckucks-Hashing]].</ref>
|-
| valign="top" | '''Einfügen/Löschen am Ende'''
| style="background:#ffdddd; text-align:center" |''N/A''
| style="background:#ddffdd; text-align:center" |O(1)<ref name="amortisiert" />
| style="background:#ddffdd; text-align:center" |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>
|-
| valign="top" | '''Einfügen/Löschen mittig'''
| style="background:#ffdddd; text-align:center" |''N/A''
| style="background:#ffdddd; text-align:center" |O(''n'')
| style="background:#ddffdd; text-align:center" |suche +<br/>O(1)<ref>Gerald Kruse. {{Toter Link |datum=2018-04 |url=http://www.juniata.edu/faculty/kruse/cs240/syllabus.htm |text=CS 240 Lecture Notes |archivebot=2018-04-04 22:16:16 InternetArchiveBot}}: {{Toter Link |datum=2018-04 |url=http://www.juniata.edu/faculty/kruse/cs240/linkedlist2.htm |text=Linked Lists Plus: Complexity Trade-offs |archivebot=2018-04-04 22:16:16 InternetArchiveBot}}. Juniata College. Spring 2008.</ref>
|-
| valign="top" | '''Suche'''
| style="background:#ffdddd; text-align:center" |O(''n'')
| style="background:#ffdddd; text-align:center" |O(''n'')
| style="background:#ffdddd; text-align:center" |O(''n'')
| style="background:#ffffdd; text-align:center" |O(''log n'')
| style="background:#ddffdd; text-align:center" |O(''1'')
|-
| valign="top" | '''Mittlerer Speicherplatzbedarf'''<ref>Gemeint ist der '''zusätzliche''' Speicherplatzbedarf. Er ist meist ein Bruchteil des '''ohnehin erforderlichen''' Speicherplatzbedarfs von O(''n'').</ref>
| style="background:#ddffdd; text-align:center" |0
| style="background:#ffdddd; text-align:center" |O(''n'')
| style="background:#ffdddd; text-align:center" |O(''n'')
| style="background:#ffdddd; text-align:center" |O(''n'')
| style="background:#ffdddd; text-align:center" |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-Symbole|Landau-Notation]] <math>\mathcal{O}(1)</math> – eingefügt werden, die Suche nach bereits im Container eingelagerten Daten kann jedoch im [[Worst Case|ungünstigsten Fall]] <math>\mathcal{O}(n)</math> – ein Sichten des gesamten Datenbestands – erfordern.

Wird als Container hingegen ein [[balancierter Baum]], wie [[AVL-Baum|AVL-]] oder [[Rot-Schwarz-Baum|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 ==
* [[Containerformat]]
* [[Container (Begriffsklärung)]]

== Anmerkungen und Einzelnachweise ==
<references/>

[[Kategorie:Praktische Informatik]]

Container (Informatik) - Versionsgeschichte

imported>TaxonBot: Bot: Auflösung doppelter toter Links nach https://de.wikipedia.org/w/index.php?title=Wikipedia:Bots/Anfragen&oldid=266185123#Aufl%C3%B6sung_der_doppelten_Toten_Links