Infos zu Listen als Datenstruktur
Neben Algorithmen können auch Datenstrukturen berechenbar sein. Ein typisches Beispiel dafür ist die verkettete Liste. In der Informatik handelt es sich bei der verketteten Liste um eine dynamische Datenstruktur, die es unterstützt, Datenelemente geordnet zu speichern. Die Anzahl der Objekte muss dabei im Vorfeld nicht bekannt sein und bleibt über die gesamte Lebensdauer der Liste offen.
In diesem Beitrag schauen wir uns Listen als Datenstruktur einmal genauer an!:
Inhalt
Die Definition von Listen
Ein Nachteil eines Arrays besteht darin, dass im Vorfeld bekannt sein muss, wie viele Artikel notwendig sind. Die Datenstruktur einer Liste löst dieses Problem. Als endliche Folge von Elementen ist es bei der Liste möglich, ihre Länge jederzeit zu verändern, indem Elemente hinzugefügt oder entfernt werden.
Dabei besteht eine Liste aus Zellen und jede Zelle setzt sich aus zwei Teilen zusammen:
-
Der erste Teil ist der Zellinhalt und damit das eigentliche Listenelement.
-
Der zweite Teil wird für die Verkettung der Listen benötigt und dient als Referenz auf die Zelle des nächsten Listenelements.
Per Definition folgt auf die letzte Zelle keine nächste Zelle. Deshalb muss dort der auf nichts verweisende Nullwert stehen.
Listen können flexibel auf- und abgebaut werden.
Dafür gibt es einige simple Standardoperationen:
-
Create = Listenelemente erstellen und verketten
-
Delete = einzelne Listenelemente entketten und löschen
-
Search = nach einem bestimmten Listenelement suchen
-
Insert = ein Listenelement hinzufügen
-
Destroy = alle Listenelemente löschen
Der Begriff Size steht für die Anzahl der Elemente in einer Liste.
Lineare Listen
Wie die meisten abstrakten Datentypen (ADT) ist auch die lineare ADT-Liste ein zusammengesetzter Datentyp. Jedes Objekt setzt sich aus einer endlichen Anzahl von Elementen oder Teilobjekten zusammen und ist linear angeordnet. Bei einer linearen Liste sind Standarddatentypen als Elemente miteinander verkettet.
Dabei gilt für eine lineare Liste:
-
Es kann nur ein Element geben, das den Anfang der Liste bildet und folglich keinen Vorgänger hat. Ein Listenanker verweist auf dieses Element.
-
Nur ein Listenelement kann das Ende der Liste sein. Dieses Element hat keine Nachfolger.
-
Alle anderen Einträge in der Liste haben exakt einen Vorgänger und einen Nachfolger.
Bei einem abstrakten Datentyp ist es nicht notwendig, seine Struktur, innere Organisation oder Implementierung festzulegen. Es genügt, die Operationen anzugeben, die der abstrakte Datentyp ausführen soll.
Verkettete Listen
Bei der verketteten Liste handelt es sich um eine Datensammlung. Anders als bei Arrays müssen die enthaltenen Elemente nicht als Knoten hintereinander im Hauptspeicher abgelegt sein, sondern können beliebig über alle Speicher verteilt werden.
Zeiger verbinden die Knoten miteinander, die aufeinander folgen.
Verkettete Listen bieten sich immer dann an, wenn noch nicht feststeht, wie viele Elemente erforderlich sind. Dabei werden einfach und doppelt verkettete Listen voneinander unterschieden.
Einfach verkettete Listen
Eine einfach verkettete Liste ist eine Folge von beliebig vielen Elementen. Sie sind durch Zeiger miteinander verbunden. Während das Programm ausgeführt wird, kann die Anzahl der Listenelemente beliebig verändert werden.
Jeder Eintrag in der Liste umfasst einen Datenbereich und einen Zeiger, durch den er mit dem nächsten Element in der Liste verknüpft ist.
Beim Datenbereich handelt es sich um eine oder mehrere Variablen, die tatsächliche Daten wie zum Beispiel Werte oder Zeichenfolgen speichern.
Informationen über seine Position in der Liste hat ein Listenelement nicht. Stattdessen kennt es nur die Adresse des nachfolgenden Elements.
Doppelt verkettete Listen
Ausgehend von einer einfach verketteten Liste, ist eine doppelt verkettete Liste im Prinzip eine konzeptionelle Erweiterung. Hier hat jedes Listenelement zwei Zeiger, nämlich einen auf seinen Nachfolger und einen auf seinen Vorgänger.
Das führt dazu, dass die Liste von jedem Knotenpunkt aus in beide Richtungen durchlaufen werden kann.
In einer doppelt verketteten Liste gestalten sich einige Operationen einfacher. Dazu zählt zum Beispiel das Entfernen eines Elements mit einem bestimmten Wert. Denn der gelöschte Knoten verweist auf die beiden benachbarten Elemente, deren Verknüpfungen mit dem nicht mehr vorhandenen Elemente geändert werden müssen.
Zirkuläre Listen
Einige Anwendungen erfordern Listen, die keinen festen Anfangs- und Endpunkt haben. Um so eine Liste trotzdem immer wieder von vorne durchlaufen zu können, wird der Zeiger nicht als Nullwert definiert, sondern verweist auf das erste Element.
Weil in einer zirkulären Liste jedes Listenelement einen Nachfolger hat, der Zeiger des letzten Elements aber mit dem ersten Element verknüpft ist, wird auch von einer Ringliste gesprochen.
Ein simples Viereck, bei dem die vier Eckpunkte miteinander verbunden ist, wäre ein Beispiel für eine zirkuläre Liste. Denn das Viereck endet nicht am vierten Eckpunkt. Stattdessen ist dieser Punkt mit dem ersten Eckpunkt verbunden.
Array und Linked Listen
Array Listen und Linked Listen implementieren die Listenschnittstelle und behalten dabei die Reihenfolge bei, in der die Elemente eingefügt wurden. Beide Varianten gehören zu den asynchronen Klassen, unterscheiden sich aber in einigen wesentlichen Punkten voneinander.
Eine Array Liste greift intern auf dynamische Arrays zurück, um die Elemente zu speichern. Weil sie nur Listen implementiert, kann sie auch nur als Liste eingesetzt werden. Dafür eignet sie sich gut, um Daten zu speichern und darauf zuzugreifen.
Eine Linked Liste speichert die einzelnen Elemente intern in einer verketteten Liste. Weil sie verschiedene Schnittstellen implementiert, kann sie sowohl als Liste als auch als Queue dienen. Die Linked Liste spielt ihre Stärken aus, wenn es darum geht, mit Daten zu arbeiten.
Mehr Ratgeber, Tipps und Anleitungen:
- Die wichtigsten Infos rund um Suchalgorithmen, 2. Teil
- Die wichtigsten Infos rund um Suchalgorithmen, 1. Teil
- KI-basierte Code-Sicherheit: Wie KI-Systeme unser digitales Leben sicherer machen
- 3 wichtige Aufgaben von KI-Systemen im Recruiting
- Starlink als Mittel zur Förderung von Bildung und Wissenschaft
- 7 Tipps für einen DSGVO-gerechten Umgang mit Daten im Homeoffice
- Leitfaden: SEO und Social-Media – Wirtschaftliche und geschäftliche Leistungsvorteile
- Lehrplan für das Schulfach Informatik
Thema: Infos zu Listen als Datenstruktur
Übersicht:
Fachartikel
Verzeichnis
Über uns
- Die 5 größten Gefahren für externe Festplatten - 6. April 2024
- Eine E-Mail an mehrere Empfänger verschicken – so geht’s richtig - 15. März 2024
- Grundlegendes Wissen zu verteilten Datenstrukturen, 2. Teil - 7. März 2024