StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
Americas
Europe
Nicht nur Algorithmen, sondern auch Datenstrukturen können rekursiv sein: Ein klassisches Beispiel hierfür ist die verkettete Liste. In dieser Erklärung wirst Du die einfach und doppelt verkettete Liste kennenlernen.
Entdecke über 50 Millionen kostenlose Lernmaterialien in unserer App.
Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken
Jetzt kostenlos anmeldenNicht nur Algorithmen, sondern auch Datenstrukturen können rekursiv sein: Ein klassisches Beispiel hierfür ist die verkettete Liste. In dieser Erklärung wirst Du die einfach und doppelt verkettete Liste kennenlernen.
In der Informatik ist eine verkettete Liste eine dynamische Datenstruktur, die die geordnete Speicherung von Datenelementen unterstützt. Die Anzahl der Objekte muss nicht im Voraus bekannt sein (z. B. zur Kompilierzeit) und bleibt für die Lebensdauer der Liste offen.
Wenn Du mehr über dynamische Datenstrukturen wissen möchtest, dann ließ Dir doch die Erklärung "Datenstrukturen" durch.
Ein Array hat einen Nachteil. Du musst im Voraus wissen, wie viele Artikel Du benötigst. Dieses Problem wird mit der Datenstruktur einer Liste gelöst.
Eine Liste ist eine endliche Folge von Elementen, deren Länge (im Gegensatz zu einem Array) durch Hinzufügen und Subtrahieren von Elementen geändert werden kann.
Die Liste besteht aus "Zellen" und jede Zelle besteht aus zwei Teilen:
Da die letzte Zelle per Definition keine "nächste" Zelle hat, muss der nicht referenzierte Nullwert dort stehen.
Du kannst Listen flexibel auf- und abbauen. Dazu gibt es ganz einfache Standardoperationen:
Wie die meisten abstrakten Datentypen ist die lineare ADT-Liste ein zusammengesetzter Datentyp. Jedes seiner Objekte besteht aus einer endlichen Anzahl von Teilobjekten oder Elementen und ist linear angeordnet.
Eine lineare Liste ist eine verkettete Folge von Elementen, die aus Standarddatentypen bestehen.
Für lineare Listen gilt Folgendes:
Abstrakten Datentypen (ADT)
Wenn Du einen abstrakten Datentyp definierst, muss Du Dir keine Gedanken über die "Struktur", "innere Organisation" oder "Implementierung" der Daten machen. Du gibst einfach die Operation an, die der ADT ausführen soll.
Die bekanntesten ADT's in der Informatik sind:
Eine verkettete Liste ist ein Datencontainer, dessen Elemente (Knoten) nicht hintereinander im Hauptspeicher abgelegt werden müssen (wie bei Arrays), sondern beliebig über alle Speicher verteilt werden können. Aufeinanderfolgende Knoten sind durch Zeiger miteinander verbunden.
Verkettete Listen sollten immer verwendet werden, wenn Du nicht im Voraus weißt, wie viele Elemente Du benötigst:
Es gibt verschiedene Arten von verkettete Listen:
Verkettete Listen | Beschreibung |
Einfach verkettete Liste | In einer einfach verknüpften Liste hat jeder Knoten einen Zeiger auf den nächsten Knoten. |
Doppelt verkettete Liste | Bei doppelt verketteten Listen besitzt jeder Knoten zwei Zeiger: einen auf den nächsten und einen auf den vorangehenden Knoten. |
Eine einfach verkettete Liste ist eine Folge beliebig vieler Listenelemente (Knoten), die durch Zeiger miteinander verbunden sind. Die Anzahl der Elemente kann während der Programmausführung beliebig verändert werden.
Jeder Listeneintrag besteht aus einem Datenbereich und einem Zeiger auf das nächste Listenelement. Datenbereich bedeutet eine oder mehrere Variablen, die tatsächliche Daten (Werte, Zeichenfolgen usw.) speichern.
Ein Listenelement hat keine Informationen über seine Position in der Liste. Er kennt nur die Adresse seines Nachfolgers. Die folgende Abbildung soll das ganze Prinzip noch einmal verdeutlichen.
Abb. 1 - Einfach verkettete Liste mit vier Elementen
Wenn man eine Datenstruktur mit einigen Standardoperationen hat, sollte man diese in einer einzigen Klasse zusammenfassen. Dies gilt offensichtlich für Listen, weshalb in Java (im Paket java.util) eine LinkedList-Klasse vordefiniert ist.
Hier erwartet Dich die Java-Implementierung einer einfach verketteten Liste:
// Ein verketteter Listenknoten class Node{ int data; Node next; Node(int data){ this.data = data; this.next = null; } } class Main{ // Hilfsfunktion zum Ausgeben einer gegebenen einfach verketteten Liste public static void printList(Node head){ Node ptr = head; while (ptr != null){ System.out.print(ptr.data + " —> "); ptr = ptr.next; } System.out.println("null"); } // Naive Funktion für die Darstellung von verketteten Listen mit vier Knoten public static Node constructList(){ // Verkettete Listenknoten erstellen Node first = new Node(1); Node second = new Node(2); Node third = new Node(3); Node fourth = new Node(4); // Ordne die Pointer neu an, um eine Liste zu erzeugen Node head = first; first.next = second; second.next = third; third.next = fourth; // Pointer auf den ersten Knoten in der Liste zurückgeben return head; } public static void main(String[] args){ // "head" zeigt auf das Startelement der verketteten Liste Node head = constructList(); // Verkettete Liste ausgeben printList(head); } }
Output: 1 ⇢ 2 ⇢ 3 ⇢ 4 ⇢ null
Um effektiv mit einer Liste arbeiten zu können, benötigst Du natürlich die in der folgenden Tabelle aufgeführten Listenoperationen:
Operation | Funktion | Komplexität |
addFirst() | Element vorne anhängen | O(1) |
getFirst() | erstes Element | O(1) |
removeFirst() | erstes Element entfernen | O(1) |
addLast() | Element hinten anhängen | O(n) |
getLast() | letztes Element | O(n) |
removeLast() | letztes Element entfernen | O(n) |
void add() | Element an der Stelle i einfügen | O(n) |
void remove() | Element an der Stelle i entfernen | O(n) |
void set() | Element an der Stelle i ersetzen | O(n) |
Basierend auf einer einfach verketteten Liste kann eine doppelt verkettete Liste als konzeptionelle Erweiterung beschrieben werden, bei der jeder Knoten nicht nur den nächsten Knoten, sondern auch den vorherigen Knoten referenziert. Die Liste kann also (von jedem Knoten aus) in beide Richtungen durchlaufen werden:
Abb. 2 - Doppelt verkettete Liste
Eine entsprechende JAVA-Klasse sieht (vereinfacht, ohne private Klassenattribute) etwa so aus:
public class Node {
int data;
Node previous;
Node next;
// Konstruktor für Wert, etc. ...
}
Die doppelt verkettete Liste erleichtert einige Operationen – wie das Löschen eines Knotens mit einem bestimmten Wert, da der entfernte Knoten selbst auf zwei benachbarte Knoten verweist, deren Referenzen (auf den gelöschten Knoten) geändert werden müssen.
In einigen Anwendungen benötigst Du Listen, die keinen Anfang und kein Ende haben, bei denen man aber wieder von vorn beginnen möchte. Dann setzt man den Zeiger nicht auf null, sondern lässt ihn auf das erste Element verweisen.
Zirkuläre- oder Ringliste: Jedes Listenelement hat ein Nachfolgeelement, und der Zeiger des letzten Elements zeigt auf das erste Element.
Beispielsweise kann ein Viereck als zirkuläre Liste betrachtet werden, das aus vier Punkten A, B, C, D besteht.
ArrayList und LinkedList implementieren die List-Schnittstelle und behalten die Einfügungsreihenfolge bei. Beides sind asynchrone Klassen.
Es gibt jedoch Unterschiede zwischen den beide Klassen.
ArrayList | LinkedList |
Intern verwendet die ArrayList dynamische Arrays, um ihre Elemente zu speichern. | Eine LinkedList verwendet intern eine verkettete Liste, um ihre Elemente zu speichern. |
Eine ArrayList-Klasse kann nur als Liste fungieren, da sie nur Listen implementiert. | Die LinkedList-Klasse implementiert die List- und Deque-Schnittstellen, sodass sie sowohl als Liste auch als Queue fungieren kann. |
ArrayList eignet sich gut zum Speichern und Zugreifen auf Daten. | LinkedList eignet sich gut für die Arbeit mit Daten. |
In der Informatik ist eine verkettete Liste eine dynamische Datenstruktur, die die geordnete Speicherung von Datenelementen unterstützt.
Eine einfach verkettete Liste ist eine Folge beliebig vieler Listenelemente (Knoten), die durch Zeiger miteinander verbunden sind.
Zirkuläre- oder Ringliste: Jedes Listenelement hat ein Nachfolgeelement und der Zeiger des letzten Elements zeigt auf das erste Element.
Der Hauptunterschied zwischen Arrays und verketteten Listen ist ihre Struktur. Ein Array ist eine datengesteuerte Struktur, bei der jedem Element ein Index zugeordnet ist. Bei einer referenzbasierten verketteten Liste, enthält hingegen jeder Knoten Daten und Verweise auf das vorherige und das nächste Element.
Karteikarten in Listen15
Lerne jetztWas ist eine Liste in der Informatik?
In der Informatik ist eine verkettete Liste eine dynamische Datenstruktur, die die geordnete Speicherung von Datenelementen unterstützt.
Ergänze
Nicht nur Algorithmen, sondern auch (1) ______ können rekursiv sein: Ein klassisches Beispiel hierfür ist die verkettete (2) ______.
(1) Datenstrukturen
(2) Liste
Wahr oder Falsch
Die Liste besteht aus "Kanten", und jede Kante besteht aus zwei Teilen.
Falsch
Was ist eine Liste?
Eine Liste ist eine endliche Folge von Elementen, deren Länge (im Gegensatz zu einem Array) durch Hinzufügen und Subtrahieren von Elementen geändert werden kann.
Ergänzenze
Der zweite Teil des Listenelements dient der Verkettung der Listen und ist eine ______ auf das nächste Listenelement (genauer gesagt die Zelle des nächsten Listenelements).
Referenz
Wahr oder Falsch
Operationen mit Listen sind:
create(): Erstellen und Verketten von Listenelementen
delete(): Entketten und Löschen eines Listenelements
search(): Suchen nach einem bestimmten Listenelement
destroy(): Alle Elemente löschen
insert(): Element hinzufügen
size(): Elementanzahl
Wahr
Du hast bereits ein Konto? Anmelden
Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.
Melde dich an für Notizen & Bearbeitung. 100% for free.
Speichere Erklärungen in deinem persönlichen Bereich und greife jederzeit und überall auf sie zu!
Mit E-Mail registrieren Mit Apple registrierenDurch deine Registrierung stimmst du den AGBs und der Datenschutzerklärung von StudySmarter zu.
Du hast schon einen Account? Anmelden