Datenstruktur

Sobald Daten eine komplexere Form annehmen als eine einzelne Variable verarbeiten kann, müssen sie in speziellen Datenstrukturen organisiert werden.

Diese Datenstrukturen unterscheiden sich im Hinblick auf die Zugriffsmöglichkeiten, die sie auf die Daten bieten, sowie auf die Zeit, die dafür nötig ist.

🕳

Lückenhaft

In diesem Artikel oder Abschnitt fehlen noch folgende wichtige Informationen:

Alle Datenstrukturen müssen noch detaillierter beschrieben werden.

Hilf dem KGS-Wiki, indem du sie recherchierst und einfügst.

Array

Siehe auch Array

Ein Array, in der deutschsprachigen Literatur auch Feld genannt, ist eine der einfachsten Datenstrukturen. Ursprünglich ist ein Array eine Reihe von hintereinander liegenden Speicherzellen. Bei der Erstellung des Arrays wird ein Block an Speicherzellen mit einer festen Größe reserviert. Deswegen muss man z.B. in C oder Java immer noch bei der Initialisierung eines Arrays dessen Größe angeben und kann diese nachträglich nicht mehr verändern.

Auf die Werte eines Arrays wird mit einem Index zugegriffen, der typischerweise bei 0 beginnt.

Verkettete Liste

Siehe auch Verkettete Liste

Eine verkettete Liste (engl. linked list) ist eine Datenstruktur, die beliebig viele Elemente in linearer Form speichern kann, d.h. zu jedem Element außer dem letzten existiert genau ein Nachfolger und zu jedem Element außer dem ersten existiert genau ein Vorgänger.

Praktisch an verketteten Listen ist, dass man mit relativ geringem Aufwand mittendrin Elemente löschen oder einfügen kann, ohne dass Lücken entstehen oder potenziell größere Datenmengen verschoben werden müssen. Auch für die Implementierung von Stacks oder Queues sind sie geeeignet.

Nachteilig ist, dass Operationen wie Suchen eine Laufzeit in ${\mathcal {O}}(n)$ aufweisen.

Tupel

Siehe auch Tupel

Menge

Siehe auch Menge

Stack

Siehe auch Stack

Auch bekannt als Stapel oder Kellerspeicher

Queue

Siehe auch Warteschlange

Schlüssel-Wert-Paare

Siehe auch Schlüssel-Wert-Datenstruktur

Auch bekannt als Assoziatives Array, Wörterbuch, Dictionary, Map (in Java) oder Hash (in Perl)

Baum

Siehe auch Baum

Heap

Siehe auch Heap

Graph

Siehe auch Graph