Verknüpfte Listen in Python – Plato AiStream V2.1

Neuauflage von Plato

Verfolger: 0

Einleitung

Eine verknüpfte Liste ist eine Datenstruktur, die aus einer Folge von Knoten besteht, von denen jeder einen Wert und einen Verweis auf den nächsten Knoten in der Folge enthält. Im Gegensatz zu Arrays erfordern verknüpfte Listen keine zusammenhängende Speicherzuweisung, was sie für bestimmte Vorgänge flexibler und effizienter macht. In diesem Artikel untersuchen wir die Vor- und Nachteile verknüpfter Listen und wie man sie in Python implementiert.

Inhaltsverzeichnis

Vor- und Nachteile verknüpfter Listen

Verknüpfte Listen bieten gegenüber anderen Datenstrukturen mehrere Vorteile. Erstens ermöglichen sie ein effizientes Einfügen und Löschen von Elementen, da sie lediglich die Aktualisierung der Referenzen benachbarter Knoten erfordern. Dies macht LinkedLists ideal für Szenarien, in denen häufige Änderungen zu erwarten sind. Darüber hinaus können LinkedLists im Gegensatz zu Arrays, die eine feste Größe haben, dynamisch vergrößert oder verkleinert werden.

Allerdings haben verknüpfte Listen auch einige Nachteile. Im Gegensatz zu Arrays unterstützen verknüpfte Listen keinen wahlfreien Zugriff auf Elemente, was bedeutet, dass der Zugriff auf ein Element an einem bestimmten Index das Durchlaufen der Liste von Anfang an erfordert. Dies kann bei bestimmten Vorgängen zu einer geringeren Leistung führen. Darüber hinaus benötigen verknüpfte Listen zusätzlichen Speicher, um die Verweise auf die nächsten Knoten zu speichern, was bei kleinen Datensätzen ineffizient sein kann.

Verknüpfte Listen in Python implementieren

Python bietet eine flexible und intuitive Möglichkeit, verknüpfte Listen zu implementieren. Es gibt drei Haupttypen von verknüpften Listen: einfach verknüpfte Listen, doppelt verknüpfte Listen und zirkulär verknüpfte Listen. Lassen Sie uns jeden einzelnen davon im Detail untersuchen.

Einfach verknüpfte Liste

Eine einfach verknüpfte Liste besteht aus Knoten, wobei jeder Knoten einen Wert und einen Verweis auf den nächsten Knoten in der Sequenz enthält. So können Sie eine einfach verknüpfte Liste in Python erstellen:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class Linked List:
    def __init__(self):
        self.head = None

Erstellen einer einfach verknüpften Liste

Um eine einfach verknüpfte Liste zu erstellen, müssen wir eine Node-Klasse definieren, die jeden Knoten in der Liste darstellt. Jeder Knoten enthält einen Wert und einen Verweis auf den nächsten Knoten. Die Klasse „Linked List“ dient als Container für die Knoten, wobei das Head-Attribut auf den ersten Knoten in der Liste zeigt.

Einfügen von Knoten in eine einfach verknüpfte Liste

Das Einfügen von Knoten in eine einfach verknüpfte Liste erfordert die Aktualisierung der Referenzen benachbarter Knoten. Hier ist ein Beispiel für das Einfügen eines Knotens am Anfang der Liste:

def insert_at_beginning(self, value):
    new_node = Node(value)
    new_node.next = self.head
    self.head = new_node

Knoten aus einer einfach verknüpften Liste löschen

Das Löschen von Knoten aus einer einfach verknüpften Liste erfordert die Aktualisierung der Referenzen benachbarter Knoten. Hier ist ein Beispiel für das Löschen eines Knotens mit einem bestimmten Wert:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                break
            current = current.next

Suchen in einer einfach verknüpften Liste

Die Suche nach einem bestimmten Wert in einer einfach verknüpften Liste erfordert das Durchlaufen der Liste, bis der Wert gefunden oder das Ende der Liste erreicht wird. Hier ist ein Beispiel für die Suche nach einem Wert:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Umkehren einer einfach verknüpften Liste

Das Umkehren einer einfach verknüpften Liste erfordert die Aktualisierung der Referenzen jedes Knotens, um auf den vorherigen Knoten zu verweisen. Hier ist ein Beispiel für die Umkehrung einer einfach verknüpften Liste:

def reverse(self):
    previous = None
    current = self.head
    while current:
        next_node = current.next
        current.next = previous
        previous = current
        current = next_node
    self.head = previous

Doppelt verknüpfte Liste

Eine doppelt verknüpfte Liste ähnelt einer einfach verknüpften Liste, aber jeder Knoten enthält einen Verweis sowohl auf den nächsten als auch auf den vorherigen Knoten in der Sequenz. Dies ermöglicht eine effiziente Durchquerung in beide Richtungen. So können Sie in Python eine doppelt verknüpfte Liste erstellen:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None
        self.previous = None

class DoublyLinked List:
    def __init__(self):
        self.head = None

Erstellen einer doppelt verknüpften Liste

Um eine doppelt verknüpfte Liste zu erstellen, definieren wir eine Node-Klasse, die einen Wert, eine Referenz auf den nächsten Knoten und eine Referenz auf den vorherigen Knoten enthält. Die DoublyLinked List-Klasse dient als Container für die Knoten, wobei das Head-Attribut auf den ersten Knoten in der Liste zeigt.

Einfügen von Knoten in eine doppelt verknüpfte Liste

Das Einfügen von Knoten in eine doppelt verknüpfte Liste erfordert die Aktualisierung der Referenzen benachbarter Knoten. Hier ist ein Beispiel für das Einfügen eines Knotens am Anfang der Liste:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if self.head:
        self.head.previous = new_node
    new_node.next = self.head
    self.head = new_node

Knoten aus einer doppelt verknüpften Liste löschen

Das Löschen von Knoten aus einer doppelt verknüpften Liste erfordert die Aktualisierung der Referenzen benachbarter Knoten. Hier ist ein Beispiel für das Löschen eines Knotens mit einem bestimmten Wert:

def delete_node(self, value):
    current = self.head
    if current.value == value:
        self.head = current.next
        if self.head:
            self.head.previous = None
    else:
        while current.next:
            if current.next.value == value:
                current.next = current.next.next
                if current.next:
                    current.next.previous = current
                break
            current = current.next

Suchen in einer doppelt verknüpften Liste

Die Suche nach einem bestimmten Wert in einer doppelt verknüpften Liste erfordert das Durchlaufen der Liste in beide Richtungen, bis der Wert gefunden oder das Ende der Liste erreicht wird. Hier ist ein Beispiel für die Suche nach einem Wert:

def search(self, value):
    current = self.head
    while current:
        if current.value == value:
            return True
        current = current.next
    return False

Umkehren einer doppelt verknüpften Liste

Das Umkehren einer doppelt verknüpften Liste erfordert die Aktualisierung der Referenzen jedes Knotens, um den nächsten und den vorherigen Zeiger auszutauschen. Hier ist ein Beispiel für die Umkehrung einer doppelt verknüpften Liste:

def reverse(self):
    current = self.head
    while current:
        next_node = current.next
        current.next = current.previous
        current.previous = next_node
        if not next_node:
            self.head = current
        current = next_node

Zirkulär verkettete Liste

Eine zirkulär verknüpfte Liste ist eine Variante einer einfach verknüpften Liste, bei der der letzte Knoten auf den ersten Knoten verweist und so eine kreisförmige Struktur entsteht. Dies ermöglicht eine effiziente Durchquerung von jedem Knoten in der Liste. So können Sie eine zirkuläre verknüpfte Liste in Python erstellen:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class CircularLinked List:
    def __init__(self):
        self.head = None

Erstellen einer kreisförmigen verknüpften Liste

Um eine zirkuläre verknüpfte Liste zu erstellen, definieren wir eine Node-Klasse, die einen Wert und einen Verweis auf den nächsten Knoten enthält. Die Klasse „CircularLinked List“ dient als Container für die Knoten, wobei das Head-Attribut auf den ersten Knoten in der Liste zeigt. Zusätzlich wird die nächste Referenz des letzten Knotens auf den Kopf gesetzt, wodurch eine kreisförmige Struktur entsteht.

Einfügen von Knoten in eine kreisförmig verknüpfte Liste

Das Einfügen von Knoten in eine zirkuläre verknüpfte Liste erfordert die Aktualisierung der Referenzen benachbarter Knoten. Hier ist ein Beispiel für das Einfügen eines Knotens am Anfang der Liste:

def insert_at_beginning(self, value):
    new_node = Node(value)
    if not self.head:
        self.head = new_node
        new_node.next = self.head
    else:
        current = self.head
        while current.next != self.head:
            current = current.next
        current.next = new_node
        new_node.next = self.head
        self.head = new_node

Knoten aus einer zirkulär verknüpften Liste löschen

Das Löschen von Knoten aus einer zirkulären verknüpften Liste erfordert die Aktualisierung der Referenzen benachbarter Knoten. Hier ist ein Beispiel für das Löschen eines Knotens mit einem bestimmten Wert:

def delete_node(self, value):
    if not self.head:
        return
    current = self.head
    if current.value == value:
        while current.next != self.head:
            current = current.next
        if current == self.head:
            self.head = None
        else:
            current.next = self.head.next
            self.head = self.head.next
    else:
        previous = None
        while current.next != self.head:
            previous = current
            current = current.next
            if current.value == value:
                previous.next = current.next
                break

Suchen in einer zirkulär verknüpften Liste

Die Suche nach einem bestimmten Wert in einer kreisförmig verknüpften Liste erfordert das Durchlaufen der Liste, bis der Wert gefunden wird, oder das Durchlaufen der gesamten Liste. Hier ist ein Beispiel für die Suche nach einem Wert:

def search(self, value):
    if not self.head:
        return False
    current = self.head
    while True:
        if current.value == value:
            return True
        current = current.next
        if current == self.head:
            break
    return False

Umkehren einer zirkulär verknüpften Liste

Das Umkehren einer kreisförmigen verknüpften Liste erfordert die Aktualisierung der Referenzen jedes Knotens, um die kreisförmige Struktur umzukehren. Hier ist ein Beispiel für die Umkehrung einer zirkulären verknüpften Liste:

def reverse(self):
    if not self.head:
        return
    previous = None
    current = self.head
    next_node = current.next
    while True:
        current.next = previous
        previous = current
        current = next_node
        next_node = next_node.next
        if current == self.head:
            break
    self.head = previous

Allgemeine Operationen für verknüpfte Listen

Verknüpfte Listen unterstützen verschiedene allgemeine Operationen, die an den Elementen ausgeführt werden können. Sehen wir uns einige dieser Operationen an:

Zugreifen auf Elemente in einer verknüpften Liste

Um auf Elemente in einer verknüpften Liste zuzugreifen, können wir die Liste ausgehend vom Kopfknoten durchlaufen und zum nächsten Knoten wechseln, bis wir die gewünschte Position erreichen. Hier ist ein Beispiel für den Zugriff auf ein Element an einem bestimmten Index:

def get_element(self, index):
    current = self.head
    count = 0
    while current:
        if count == index:
            return current.value
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Elemente in einer verknüpften Liste ändern

Das Ändern von Elementen in einer verknüpften Liste umfasst das Durchlaufen der Liste, um das gewünschte Element zu finden und seinen Wert zu aktualisieren. Hier ist ein Beispiel für die Änderung eines Elements an einem bestimmten Index:

def modify_element(self, index, new_value):
    current = self.head
    count = 0
    while current:
        if count == index:
            current.value = new_value
            return
        count += 1
        current = current.next
    raise IndexError("Index out of range")

Ermitteln der Länge einer verknüpften Liste

Um die Länge einer verknüpften Liste zu ermitteln, können wir die Liste durchlaufen und die Anzahl der Knoten zählen. Hier ist ein Beispiel für die Ermittlung der Länge einer verknüpften Liste:

def get_length(self):
    current = self.head
    count = 0
    while current:
        count += 1
        current = current.next
    return count

Überprüfen, ob eine verknüpfte Liste leer ist

Um zu überprüfen, ob eine verknüpfte Liste leer ist, können wir einfach prüfen, ob der Kopfknoten None ist. Hier ist ein Beispiel für die Überprüfung, ob eine verknüpfte Liste leer ist:

def is_empty(self):
    return self.head is None

Verkettete Listen verketten

Um zwei verknüpfte Listen zu verketten, können wir die erste Liste durchlaufen, um den letzten Knoten zu finden und seinen nächsten Verweis auf den Kopf der zweiten Liste zu aktualisieren. Hier ist ein Beispiel für die Verkettung zweier verknüpfter Listen:

def concatenate(self, other_list):
    if not self.head:
        self.head = other_list.head
    else:
        current = self.head
        while current.next:
            current = current.next
        current.next = other_list.head

Verknüpfte Liste vs. Array

Verknüpfte Listen und Arrays sind häufig verwendete Datenstrukturen, weisen jedoch unterschiedliche Eigenschaften auf, die sie für unterschiedliche Szenarien geeignet machen. Vergleichen wir verknüpfte Listen und Arrays im Hinblick auf Speichereffizienz, Einfügungs- und Löscheffizienz sowie Direktzugriffseffizienz.

Speichereffizienz

Verknüpfte Listen sind speichereffizienter als Arrays, da sie keine zusammenhängende Speicherzuweisung erfordern. Jeder Knoten in einer verknüpften Liste muss nur den Wert und einen Verweis auf den nächsten Knoten speichern, während Arrays allen Elementen Speicher zuweisen müssen, auch wenn sie nicht verwendet werden.

Effizienz beim Einfügen und Löschen

Verknüpfte Listen zeichnen sich durch Einfüge- und Löschvorgänge aus, insbesondere wenn Elemente häufig in der Mitte der Liste hinzugefügt oder daraus entfernt werden. Das Einfügen oder Löschen eines Elements in einer verknüpften Liste erfordert lediglich die Aktualisierung der Referenzen benachbarter Knoten, während bei Arrays möglicherweise das Verschieben von Elementen erforderlich ist, um die Änderung aufzunehmen.

Direktzugriffseffizienz

Arrays ermöglichen einen effizienten Direktzugriff auf Elemente basierend auf ihren Indizes, da sie eine direkte Speicheradressierung ermöglichen. Im Gegensatz dazu erfordern verknüpfte Listen das Durchlaufen der Liste von Anfang an, um auf ein Element an einem bestimmten Index zuzugreifen, was zu einer langsameren Leistung bei Direktzugriffsvorgängen führt.

Auswahl der richtigen Datenstruktur

Die Wahl zwischen verknüpften Listen und Arrays hängt von den spezifischen Anforderungen der Anwendung ab. Wenn häufige Änderungen und dynamische Größenänderungen zu erwarten sind, sind verknüpfte Listen die bessere Wahl. Wenn hingegen Direktzugriff und Speichereffizienz entscheidend sind, sind Arrays besser geeignet.

Anwendungen für verknüpfte Listen

Nachdem wir nun ein gutes Verständnis für verknüpfte Listen und ihre Funktionsweise haben, wollen wir uns mit einigen praktischen Anwendungen befassen, bei denen verknüpfte Listen effektiv eingesetzt werden können.

Sie können sich auch bei uns anmelden Kostenlose Kurse Heute!

Implementieren von Stacks und Warteschlangen

Eine der häufigsten Anwendungen verknüpfter Listen ist die Implementierung von Stapeln und Warteschlangen. Sowohl Stapel als auch Warteschlangen sind abstrakte Datentypen, die mithilfe verknüpfter Listen einfach implementiert werden können.

Ein Stack ist eine Datenstruktur, die dem Last-In-First-Out (LIFO)-Prinzip folgt. Elemente werden am selben Ende, der sogenannten Oberseite des Stapels, hinzugefügt und entfernt. Verknüpfte Listen bieten eine effiziente Möglichkeit, Stapel zu implementieren, da wir einfach Elemente zum Kopf der Liste hinzufügen oder daraus entfernen können.

Hier ist ein Beispiel für die Implementierung eines Stapels mithilfe einer verknüpften Liste in Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Stack:
    def __init__(self):
        self.head = None

    def push(self, data):
        new_node = Node(data)
        new_node.next = self.head
        self.head = new_node

    def pop(self):
        if self.head is None:
            return None
        popped = self.head.data
        self.head = self.head.next
        return popped

Eine Warteschlange hingegen folgt dem First-In-First-Out (FIFO)-Prinzip. Elemente werden an einem Ende, der sogenannten Rückseite, hinzugefügt und am anderen Ende, der sogenannten Vorderseite, entfernt. Verknüpfte Listen können auch zur effizienten Implementierung von Warteschlangen verwendet werden.

Hier ist ein Beispiel für die Implementierung einer Warteschlange mithilfe einer verknüpften Liste in Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class Queue:
    def __init__(self):
        self.front = None
        self.rear = None

    def enqueue(self, data):
        new_node = Node(data)
        if self.rear is None:
            self.front = new_node
            self.rear = new_node
        else:
            self.rear.next = new_node
            self.rear = new_node

    def dequeue(self):
        if self.front is None:
            return None
        dequeued = self.front.data
        self.front = self.front.next
        if self.front is None:
            self.rear = None
        return dequeued

Umgang mit großen Datensätzen

Verknüpfte Listen sind auch beim Umgang mit großen Datensätzen nützlich. Im Gegensatz zu Arrays erfordern verknüpfte Listen keine zusammenhängende Speicherzuweisung. Dies bedeutet, dass verknüpfte Listen Datensätze unterschiedlicher Größe effizient verarbeiten können, ohne dass eine Größenänderung oder Neuzuordnung erforderlich ist.

Nehmen wir zum Beispiel an, wir haben einen Datensatz mit Millionen von Datensätzen und müssen Vorgänge wie Einfügen, Löschen oder Durchlaufen ausführen. Die Verwendung eines Arrays für diese Aufgabe kann ineffizient sein, da beim Einfügen oder Löschen Elemente verschoben werden müssen. Bei einer verknüpften Liste können wir jedoch Elemente einfach einfügen oder löschen, indem wir die Zeiger aktualisieren, was zu schnelleren Vorgängen führt.

Graph-Traversal-Algorithmen

Graph-Traversal-Algorithmen wie die Breitensuche (BFS) und die Tiefensuche (DFS) können auch mithilfe verknüpfter Listen implementiert werden. Beim Durchlaufen von Graphen besuchen wir jeden Scheitelpunkt oder Knoten in einem Graphen in einer bestimmten Reihenfolge.

Verknüpfte Listen können zur Darstellung der Adjazenzliste eines Diagramms verwendet werden, wobei jeder Knoten in der verknüpften Liste einen Scheitelpunkt darstellt und die angrenzenden Scheitelpunkte als Knoten der verknüpften Liste gespeichert werden. Diese Darstellung ermöglicht ein effizientes Durchlaufen und Erkunden des Diagramms.

Polynomdarstellung

Mit verknüpften Listen lassen sich Polynome effizient darstellen. In der Mathematik sind Polynome Ausdrücke, die aus Variablen und Koeffizienten bestehen. Jeder Term in einem Polynom kann als Knoten in einer verknüpften Liste dargestellt werden, in der der Koeffizient und der Exponent als Daten gespeichert werden.

Durch die Verwendung verknüpfter Listen können wir problemlos Operationen an Polynomen durchführen, beispielsweise Addition, Subtraktion und Multiplikation. Die Knoten können manipuliert werden, um diese Operationen auszuführen, was zu einer präzisen und effizienten Darstellung von Polynomen führt.

Musik- und Video-Playlists

Verknüpfte Listen werden häufig zur Implementierung von Wiedergabelisten in Musik- und Videoplayern verwendet. Jeder Song oder jedes Video kann als Knoten in einer verknüpften Liste dargestellt werden, wobei die Daten Informationen über die Mediendatei enthalten und der Zeiger auf den nächsten Song oder das nächste Video in der Playlist zeigt.

Die Verwendung verknüpfter Listen für Wiedergabelisten ermöglicht eine einfache Navigation zwischen Titeln oder Videos. Durch die Aktualisierung der Zeiger können wir ganz einfach Songs zur Playlist hinzufügen oder daraus entfernen und so für ein nahtloses Benutzererlebnis sorgen.

Zusammenfassung

Zusammenfassend lässt sich sagen, dass verknüpfte Listen vielseitige Datenstrukturen sind, die in verschiedenen Bereichen Anwendung finden. Sie können verwendet werden, um Stapel und Warteschlangen zu implementieren, große Datensätze zu verarbeiten, Diagrammdurchläufe durchzuführen, Polynome darzustellen und Wiedergabelisten zu erstellen. Verknüpfte Listen bieten effiziente Lösungen für diese Probleme, indem sie ihre dynamische Speicherzuweisung und die einfache Manipulation von Knoten nutzen.

Durch das Verständnis der Anwendungen verknüpfter Listen können wir fundierte Entscheidungen bei der Auswahl von Datenstrukturen für unsere Programme treffen. Ob es darum geht, Daten zu verwalten, Algorithmen zu implementieren oder benutzerfreundliche Schnittstellen zu erstellen, verknüpfte Listen sind ein wertvolles Werkzeug im Werkzeugkasten des Programmierers.

Wenn Sie also das nächste Mal auf ein Problem stoßen, das effizientes Einfügen, Löschen oder Durchlaufen erfordert, sollten Sie die Verwendung verknüpfter Listen in Betracht ziehen, um Ihre Lösung zu vereinfachen und Ihren Code zu optimieren.

Weitere Artikel zu Python-Listen können Sie auch hier lesen:

Häufig gestellte Fragen

F1: Was ist eine verknüpfte Liste?

A: Eine verknüpfte Liste ist eine Datenstruktur, die aus Knoten besteht, wobei jeder Knoten einen Wert und eine Referenz (oder Verknüpfung) zum nächsten Knoten in der Sequenz enthält.

F2: Welche Vorteile bietet die Verwendung verknüpfter Listen?

A: Verknüpfte Listen bieten effiziente Einfüge- und Löschvorgänge, dynamische Größenänderung und erfordern keine zusammenhängende Speicherzuweisung.

F3: Was sind die Nachteile verknüpfter Listen?

A: Bei verknüpften Listen fehlt der Direktzugriff, sodass für den Elementzugriff ein Durchlaufen erforderlich ist. Außerdem verbrauchen sie zusätzlichen Speicher zum Speichern von Referenzen, was bei kleinen Datensätzen möglicherweise ineffizient ist.

F4: Was sind die Haupttypen verknüpfter Listen in Python?

A: Die Haupttypen verknüpfter Listen sind einfach verknüpfte Listen, doppelt verknüpfte Listen und zirkulär verknüpfte Listen.

F5: In welchen Szenarien sind verknüpfte Listen speichereffizienter als Arrays?

A: Verknüpfte Listen sind speichereffizienter als Arrays, wenn es um dynamische Größenänderungen und häufige Einfügungen oder Löschungen geht, da sie keine zusammenhängende Speicherzuweisung erfordern.