Implementierung einer einfach verknüpften Python-Liste

Erfahren Sie, wie Sie eine einfach verknüpfte Liste in Python implementieren. Entdecken Sie die dynamische Speicherzuweisung, Knotenoperationen, Einfügung, Durchquerung und Löschung.

Versuchen Sie es im Editor

Übersicht

Eine verknüpfte Liste ist eine lineare Datenstruktur, bei der Elemente nicht an zusammenhängenden Speicherorten gespeichert werden. Stattdessen ist jedes Element (Knoten genannt) ein separates Objekt, das einen Verweis auf den nächsten Knoten in der Sequenz enthält.

Der Hauptvorteil einer verknüpften Liste gegenüber einem herkömmlichen Array ist ihre dynamische Größenanpassung und die Möglichkeit, Elemente zu Beginn in konstanter O(1)-Zeit einzufügen oder zu löschen. Der Zugriff auf Elemente über den Index erfordert jedoch eine lineare Durchquerung, die O(n) Zeit benötigt.

In Python implementieren wir eine verknüpfte Liste, indem wir eine Node-Klasse zum Speichern der Daten und des Referenzzeigers sowie eine LinkedList-Klasse zum Verwalten des Kopfknotens, Einfügungen am Kopf oder Ende und Löschungen definieren.

Code- und Ausführungsausgabe

Implementierung einer einfach verknüpften Liste in Python, die die Knotenerstellung, das Anhängen und das Durchlaufen von Listen veranschaulicht.

linked_list.py

Versuchen Sie es im Editor

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

class LinkedList:
    def __init__(self):
        self.head = None
        
    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node
        
    def delete(self, key):
        curr = self.head
        if curr and curr.data == key:
            self.head = curr.next
            curr = None
            return
        prev = None
        while curr and curr.data != key:
            prev = curr
            curr = curr.next
        if not curr:
            return
        prev.next = curr.next
        curr = None
        
    def display(self):
        elements = []
        curr = self.head
        while curr:
            elements.append(str(curr.data))
            curr = curr.next
        print(" -> ".join(elements) + " -> None")

# Instantiate and build the linked list
llist = LinkedList()
llist.append("Node A")
llist.append("Node B")
llist.append("Node C")
print("Initial Linked List:")
llist.display()

print("Deleting 'Node B':")
llist.delete("Node B")
llist.display()

Terminal-Ausgabe

Initial Linked List:
Node A -> Node B -> Node C -> None
Deleting 'Node B':
Node A -> Node C -> None

Schrittweise Umsetzung

Implementierung der Undo-Redo-Funktionalität in Texteditoren
Aufbau komplexer Datenstrukturen wie Diagramme, Stapel und Warteschlangen
Verwalten von Listen, bei denen die Einfügungs- und Löschhäufigkeit die Suchaktionen übersteigt

Häufig gestellte Fragen

Was ist der Unterschied zwischen einfach und doppelt verknüpften Listen?

In einer einfach verknüpften Liste zeigt jeder Knoten nur auf den nächsten Knoten. In einer doppelt verknüpften Liste enthält jeder Knoten Verweise sowohl auf den nächsten als auch auf den vorherigen Knoten, was eine bidirektionale Durchquerung auf Kosten von zusätzlichem Speicher ermöglicht.

Warum verfügt Python nicht über eine integrierte LinkedList-Klasse?

Python-Arrays (Listen) werden als dynamische Arrays implementiert. Aufgrund der Speicherverwaltung von Python und derCPython-Optimierungen sind Standardlisten für die meisten Aufgaben äußerst schnell und effizient, wodurch der praktische Bedarf an einer integrierten verknüpften Liste verringert wird.