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. 

Listen Listen

Erstelle Lernmaterialien über Listen mit unserer kostenlosen Lern-App!

  • Sofortiger Zugriff auf Millionen von Lernmaterialien
  • Karteikarten, Notizen, Übungsprüfungen und mehr
  • Alles, was du brauchst, um bei deinen Prüfungen zu glänzen
Kostenlos anmelden
Inhaltsverzeichnis
Inhaltsangabe

    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:

    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

    Was ist eine Liste in Informatik? 

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

    Was ist eine einfach verkettete Liste? 

    Eine einfach verkettete Liste ist eine Folge beliebig vieler Listenelemente (Knoten), die durch Zeiger miteinander verbunden sind.

    Was ist eine zirkuläre Liste? 

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

    Ist ein Array eine Liste? 

    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.

    Teste dein Wissen mit Multiple-Choice-Karteikarten

    Wahr oder FalschDie Liste besteht aus "Kanten", und jede Kante besteht aus zwei Teilen.

    Wahr oder FalschOperationen mit Listen sind:create(): Erstellen und Verketten von Listenelementendelete(): Entketten und Löschen eines Listenelementssearch(): Suchen nach einem bestimmten Listenelementdestroy(): Alle Elemente löscheninsert(): Element hinzufügensize(): Elementanzahl

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

    Weiter
    1
    Über StudySmarter

    StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.

    Erfahre mehr
    StudySmarter Redaktionsteam

    Team Listen Lehrer

    • 8 Minuten Lesezeit
    • Geprüft vom StudySmarter Redaktionsteam
    Erklärung speichern

    Lerne jederzeit. Lerne überall. Auf allen Geräten.

    Kostenfrei loslegen

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

    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!

    Die erste Lern-App, die wirklich alles bietet, was du brauchst, um deine Prüfungen an einem Ort zu meistern.

    • Karteikarten & Quizze
    • KI-Lernassistent
    • Lernplaner
    • Probeklausuren
    • Intelligente Notizen
    Schließ dich über 22 Millionen Schülern und Studierenden an und lerne mit unserer StudySmarter App!