Datenstruktur: Unterschied zwischen den Versionen
Sn (Diskussion | Beiträge) (→Verkettete Liste: Kapitel eingefügt) |
Sn (Diskussion | Beiträge) K (Link gefixt) |
||
| Zeile 1: | Zeile 1: | ||
Sobald Daten eine komplexere Form annehmen als eine einzelne [[Variable]] verarbeiten kann, müssen sie in speziellen [[Datenstruktur]]en organisiert werden. | Sobald Daten eine komplexere Form annehmen als eine einzelne [[Variable (Informatik)|Variable]] verarbeiten kann, müssen sie in speziellen [[Datenstruktur]]en organisiert werden. | ||
Diese Datenstrukturen unterscheiden sich im Hinblick auf die Zugriffsmöglichkeiten, die sie auf die Daten bieten, sowie auf die [[Laufzeit|Zeit]], die dafür nötig ist. | Diese Datenstrukturen unterscheiden sich im Hinblick auf die Zugriffsmöglichkeiten, die sie auf die Daten bieten, sowie auf die [[Laufzeit|Zeit]], die dafür nötig ist. | ||
| Zeile 17: | Zeile 17: | ||
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. | 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 [[Stack| | 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 [[Stack|Stack]]s oder [[Queue|Queue]]s sind sie geeeignet. | ||
Nachteilig ist, dass Operationen wie Suchen eine Laufzeit in {{O|n}} aufweisen. | Nachteilig ist, dass Operationen wie Suchen eine Laufzeit in {{O|n}} aufweisen. | ||
| Zeile 38: | Zeile 38: | ||
Siehe auch [[Schlüssel-Wert-Datenstruktur]] | Siehe auch [[Schlüssel-Wert-Datenstruktur]] | ||
Auch bekannt als ''Assoziatives Array, ''Wörterbuch'', ''Dictionary'', ''Map'' (in | Auch bekannt als ''Assoziatives Array, ''Wörterbuch'', ''Dictionary'', ''Map'' (in Java) oder ''Hash'' (in [[Perl]]) | ||
== Baum == | == Baum == | ||
Version vom 3. April 2024, 16:26 Uhr
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.
In diesem Artikel oder Abschnitt fehlen noch folgende wichtige Informationen:
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 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
