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. 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…
Entdecke über 200 Millionen kostenlose Materialien 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.
Wie möchtest du den Inhalt lernen?
94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmelden94% der StudySmarter Nutzer erzielen bessere Noten.
Jetzt anmeldenWie möchtest du den Inhalt lernen?
Kostenloser informatik Spickzettel
Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!
Sei rechtzeitig vorbereitet für deine Prüfungen.
Teste dein Wissen mit spielerischen Quizzes.
Erstelle und finde Karteikarten in Rekordzeit.
Erstelle die schönsten Notizen schneller als je zuvor.
Hab all deine Lermaterialien an einem Ort.
Lade unzählige Dokumente hoch und habe sie immer dabei.
Kenne deine Schwächen und Stärken.
Ziele Setze dir individuelle Ziele und sammle Punkte.
Nie wieder prokrastinieren mit unseren Lernerinnerungen.
Sammle Punkte und erreiche neue Levels beim Lernen.
Lass dir Karteikarten automatisch erstellen.
Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.
Melde dich an für Notizen & Bearbeitung. 100% for free.