AuK/Konkrete Datenstrukturen

Wiki-Quelltext dieser Seite.

Konkrete Datenstrukturen sind Implementierungen eines ADT. Zur Implementierung ein und desselben ADT kann es unterschiedliche konkrete Datentypen geben. Gleiche Operationen können für verschiedene konkrete Datenstrukturen sehr unterschiedliche Laufzeiten haben.

== [[AuK/Konkrete_Datenstrukturen/Array|Array]] ==
== [[AuK/Konkrete_Datenstrukturen/Linked_List|Linked List]] ==
== [[AuK/Konkrete_Datenstrukturen/Dynamisches_Array|Dynamisches Array]] ==
== [[AuK/Konkrete_Datenstrukturen/Stack|Stack]] ==
== [[AuK/Konkrete_Datenstrukturen/Queue|Queue]] ==

==Fazit==

Abschließend stellen wir die Aufwände der einzelnen Operationen übersichtlich zusammen. Derartige Angaben bilden die wichtigste Grundlage für die Interpretation und Entscheidung für oder gegen einen bestimmten Datentyp in entsprechenden Softwareprojekten.

<table>
    <tr>
      <th></th>
      <th>Access</th>
      <th>Search</th>
      <th>Insert</th>
      <th>Delete</th>
    </tr>
    <tr>
      <td>Array</td>
      <td>$\mathcal{O}(1)$</td>
      <td>$\mathcal{O}(\log_2 n)$, wenn sortiert, sonst $\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(1)$</td>
      <td>$\mathcal{O}(n)$</td>
    </tr>
    <tr>
      <td>Singly linked list</td>
      <td>$\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(1)$, an vorgegebener Position</td>
      <td>$\mathcal{O}(n)$</td>
    </tr>
    <tr>
      <td>Doubly linked list</td>
      <td>$\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(1)$, an vorgegebener Position</td>
      <td>$\mathcal{O}(1)$</td>
    </tr>
    <tr>
      <td>Dynamisches Array</td>
      <td>$\mathcal{O}(1)$</td>
      <td>$\mathcal{O}(\log_2 n)$, wenn sortiert, sonst $\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(1)$, amortisiert, sonst $\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(1)$, amortisiert, sonst $\mathcal{O}(n)$</td>
    </tr>    
    <tr>
      <td>Stack</td>
      <td>$\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(1)$</td>
      <td>$\mathcal{O}(1)$</td>
    </tr>
    <tr>
      <td>Queue</td>
      <td>$\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(n)$</td>
      <td>$\mathcal{O}(1)$</td>
      <td>$\mathcal{O}(1)$</td>
    </tr>    
</table>