• :00Tage
  • :00Std
  • :00Min
  • 00Sek
Ein neues Zeitalter des Lernens steht bevorKostenlos anmelden
Login Anmelden

Select your language

Suggested languages for you:
StudySmarter - Die all-in-one Lernapp.
4.8 • +11k Ratings
Mehr als 5 Millionen Downloads
Free
|
|

Listen

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…

Von Expert*innen geprüfte Inhalte
Kostenlose StudySmarter App mit über 20 Millionen Studierenden
Mockup Schule

Entdecke über 200 Millionen kostenlose Materialien in unserer App

Illustration

Lerne mit deinen Freunden und bleibe auf dem richtigen Kurs mit deinen persönlichen Lernstatistiken

Jetzt kostenlos anmelden

Nie wieder prokastinieren mit unseren Lernerinnerungen.

Jetzt kostenlos anmelden
Illustration

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.

Listen Informatik

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.

Listen Definition

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:

  • Der erste Teil ist das eigentliche Listenelement, also der Zellinhalt.
  • Der zweite Teil dient der Verkettung der Listen und ist eine Referenz auf das nächste Listenelement (genauer gesagt die Zelle des nächsten Listenelements).

Da die letzte Zelle per Definition keine "nächste" Zelle hat, muss der nicht referenzierte Nullwert dort stehen.

Operationen mit Listen

Du kannst Listen flexibel auf- und abbauen. Dazu gibt es ganz einfache Standardoperationen:

  • 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

Lineare Liste

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:

  1. Es kann nur ein Listenelement geben, das keinen Vorgänger hat und als Anfang der Liste bezeichnet wird. Ein Listenanker zeigt auf dieses Element.
  2. Es kann nur ein Listenelement geben, das keine Nachfolger hat und als Ende der Liste bezeichnet wird.
  3. Die restlichen Listeneinträge haben genau einen Vorgänger und genau einen Nachfolger.

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:

  • ADT Stack (Stapel)
  • ADT Queue (Schlange)
  • ADT List (Liste)
  • ADT Binary search tree (Binärer Suchbaum)

Weitere Informationen zu Stack und Queue findest Du in den gleichnamigen Erklärungen auf StudySmarter.

Verkettete Listen

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:

  • Du möchtest eine Textdatei lesen und alle Wörter speichern. Ein Array funktioniert nicht, weil Du die Wortanzahl nicht kennst.
  • Verkettete Listen unterstützen Generics, Arrays jedoch nicht immer (Java).

Arten von verketteten Listen

Es gibt verschiedene Arten von verkettete Listen:

Verkettete ListenBeschreibung
Einfach verkettete ListeIn einer einfach verknüpften Liste hat jeder Knoten einen Zeiger auf den nächsten Knoten.
Doppelt verkettete ListeBei doppelt verketteten Listen besitzt jeder Knoten zwei Zeiger: einen auf den nächsten und einen auf den vorangehenden Knoten.

Einfach verkettete Liste

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.

Listen einfach verkettete Liste mit vier Elementen StudySmarterAbb. 1 - Einfach verkettete Liste mit vier Elementen

Einfach verkettete Liste Java

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:

OperationFunktionKomplexität
addFirst()Element vorne anhängenO(1)
getFirst()erstes ElementO(1)
removeFirst()erstes Element entfernenO(1)
addLast()Element hinten anhängenO(n)
getLast()letztes ElementO(n)
removeLast()letztes Element entfernenO(n)
void add()Element an der Stelle i einfügenO(n)
void remove()Element an der Stelle i entfernenO(n)
void set()Element an der Stelle i ersetzenO(n)

Doppelt verkettete Liste

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:

Listen Doppelt Verkettete Liste StudySmarterAbb. 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.

Zirkuläre Listen

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.

Array Listen

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.

ArrayListLinkedList
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.

Listen - Das Wichtigste

  • Listen Informatik: In der Informatik ist eine verkettete Liste eine dynamische Datenstruktur.
  • Listen Definition: Eine Liste ist eine endliche Folge von Elementen, deren Länge durch Hinzufügen und Subtrahieren von Elementen geändert werden kann.
  • Lineare Listen: Eine lineare Liste ist eine verkettete Folge von Elementen, die aus Standarddatentypen bestehen.
  • Verkettete Listen: Eine verkettete Liste ist ein Datencontainer, dessen Elemente (Knoten) nicht hintereinander im Hauptspeicher abgelegt werden müssen, sondern beliebig über alle Speicher verteilt werden können.
  • Einfach verkettete Liste: Eine einfach verkettete Liste ist eine Folge beliebig vieler Listenelemente (Knoten), die durch Zeiger miteinander verbunden sind.
  • Doppelt verkettete Liste: 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.

Nachweise

  1. Gunter Saake, Kai-Uwe Sattler (2020). Algorithmen und Datenstrukturen. dpunkt.verlag
  2. Thomas Ottmann, Peter Widmayer (2012). Algorithmen und Datenstrukturen. Spektrum

Häufig gestellte Fragen zum Thema Listen

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.

Finales Listen Quiz

Listen Quiz - Teste dein Wissen

Frage

Was ist eine Liste in der Informatik

Antwort anzeigen

Antwort

In der Informatik ist eine verkettete Liste eine dynamische Datenstruktur, die die geordnete Speicherung von Datenelementen unterstützt.

Frage anzeigen

Frage

Ergänze

Nicht nur Algorithmen, sondern auch (1) ______ können rekursiv sein: Ein klassisches Beispiel hierfür ist die verkettete (2) ______. 

Antwort anzeigen

Antwort

(1) Datenstrukturen

(2) Liste

Frage anzeigen

Frage

Wahr oder Falsch

Die Liste besteht aus "Kanten", und jede Kante besteht aus zwei Teilen.

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Was ist eine Liste?

Antwort anzeigen

Antwort

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.

Frage anzeigen

Frage

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).


Antwort anzeigen

Antwort

Referenz

Frage anzeigen

Frage

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

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

Frage

Was ist eine einfach verkettete Liste? 

Antwort anzeigen

Antwort

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.

Frage anzeigen

Frage

Ergänze

Es gibt verschiedene Arten von verkettete Listen: (1) ______ verkettete Listen und (2) ______ verkettete Listen.

Antwort anzeigen

Antwort

(1) einfach

(2) doppelt

Frage anzeigen

Frage

Wahr oder Falsch

Bei doppelt verketteten Listen besitzt jeder Knoten drei Zeiger: einen auf den nächsten, einen auf sich selbst und einen auf den vorangehenden Knoten.

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Was ist eine Lineare Liste?

Antwort anzeigen

Antwort

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.

Frage anzeigen

Frage

Ergänze

Für lineare Listen gilt Folgendes:

1. Es kann nur ein Listenelement geben, das keinen Vorgänger hat und als (1) ______ der Liste bezeichnet wird. Ein Listenanker zeigt auf dieses Element.

2. Es kann nur ein Listenelement geben, das keine Nachfolger hat und als (2) ______ der Liste bezeichnet wird.

3. Die restlichen Listeneinträge haben genau einen (3) ______ und genau einen (4) ______.

Antwort anzeigen

Antwort

(1) Anfang

(2) Ende

(3) Vorgänger

(4) Nachfolger

Frage anzeigen

Frage

Wahr oder Falsch

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 eine ArrayList-Klasse vordefiniert ist.

Antwort anzeigen

Antwort

Falsch

Frage anzeigen

Frage

Was ist eine zirkuläre Liste

Antwort anzeigen

Antwort

Zirkuläre- oder Ringliste: Jedes Listenelement hat ein Nachfolgeelement, und der Zeiger des letzten Elements zeigt auf das erste Element.

Frage anzeigen

Frage

Ergänze

Basierend auf einer einfach verketteten Liste kann eine ______ verkettete Liste als konzeptionelle Erweiterung beschrieben werden, bei der jeder Knoten nicht nur den nächsten Knoten, sondern auch den vorherigen Knoten referenziert.

Antwort anzeigen

Antwort

doppelt

Frage anzeigen

Frage

Wahr oder Falsch

ArrayList und LinkedList implementieren die List-Schnittstelle und behalten die Einfügungsreihenfolge bei.

Antwort anzeigen

Antwort

Wahr

Frage anzeigen

60%

der Nutzer schaffen das Listen Quiz nicht! Kannst du es schaffen?

Quiz starten

Wie möchtest du den Inhalt lernen?

Karteikarten erstellen
Inhalte meiner Freund:innen lernen
Ein Quiz machen

94% der StudySmarter Nutzer erzielen bessere Noten.

Jetzt anmelden

94% der StudySmarter Nutzer erzielen bessere Noten.

Jetzt anmelden

Wie möchtest du den Inhalt lernen?

Karteikarten erstellen
Inhalte meiner Freund:innen lernen
Ein Quiz machen

Kostenloser informatik Spickzettel

Alles was du zu . wissen musst. Perfekt zusammengefasst, sodass du es dir leicht merken kannst!

Jetzt anmelden

Finde passende Lernmaterialien für deine Fächer

Alles was du für deinen Lernerfolg brauchst - in einer App!

Lernplan

Sei rechtzeitig vorbereitet für deine Prüfungen.

Quizzes

Teste dein Wissen mit spielerischen Quizzes.

Karteikarten

Erstelle und finde Karteikarten in Rekordzeit.

Notizen

Erstelle die schönsten Notizen schneller als je zuvor.

Lern-Sets

Hab all deine Lermaterialien an einem Ort.

Dokumente

Lade unzählige Dokumente hoch und habe sie immer dabei.

Lern Statistiken

Kenne deine Schwächen und Stärken.

Wöchentliche

Ziele Setze dir individuelle Ziele und sammle Punkte.

Smart Reminders

Nie wieder prokrastinieren mit unseren Lernerinnerungen.

Trophäen

Sammle Punkte und erreiche neue Levels beim Lernen.

Magic Marker

Lass dir Karteikarten automatisch erstellen.

Smartes Formatieren

Erstelle die schönsten Lernmaterialien mit unseren Vorlagen.

Melde dich an für Notizen & Bearbeitung. 100% for free.

Fang an mit StudySmarter zu lernen, die einzige Lernapp, die du brauchst.

Jetzt kostenlos anmelden
Illustration