Kehren eine verknüpfte Liste in Python um

Eine verkettete Liste ist eine lineare Datenstruktur in der Informatik, die das Hinzufügen und Löschen von Elementen in konstanter Zeit ermöglicht. Es besteht aus Knoten.

Ein einzelner Knoten speichert einige Daten und die Adresse des nächsten Knotens. Der nächste Knoten speichert seine Daten und die Adresse des nächsten Knotens. Ein einzelner Knoten kennt nur den Knoten, auf den er zeigt. Es hat keine Informationen über die Knoten, die darauf zeigen.

Diese Struktur ermöglicht es uns, neue Knoten hinzuzufügen und vorhandene Knoten in konstanter Zeit zu löschen, wenn der Knoten davor liegt, im Gegensatz zu Arrays, bei denen wir ein Array in ein neues Array kopieren oder die Elemente eines Arrays verschieben müssen, um Platz zum Hinzufügen und Löschen zu schaffen.

In Arrays kann man mit Hilfe von Indizes in konstanter Zeit auf Elemente zugreifen. Aber bei verketteten Listen braucht es O(n) Zeit, um auf ein Element zuzugreifen, wobei n die Länge der verketteten Liste ist.

Da eine verkettete Liste in Bezug auf die Struktur (linear) einem Array ähnelt, können wir auch Operationen wie Sortieren, Filtern und Durchsuchen von verketteten Listen durchführen. Wir können Sortier- und Suchalgorithmen wie Bubble Sort, Insertion Sort, Merge Sort, Quick Sort, Selection Sort, binäre Suche und lineare Suche über verknüpfte Listen verwenden.

Dieser Artikel zeigt, wie man eine verknüpfte Liste mit Python umkehrt. Beachten Sie, dass das Code-Snippet eine Node-Klasse berücksichtigt, die einen Block einer verknüpften Liste darstellt.

Die Klasse Node soll wie folgt aussehen.

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

Kehren eine verknüpfte Liste in Python um

Sehen Sie sich den folgenden Python-Code an, um eine verknüpfte Liste in Python umzukehren.

def reverse(head: Node) -> Node:
    previous = None
    current = head
    next = None

    while current is not None:
        next = current.next
        current.next = previous
        previous = current
        current = next

    head = previous
    return head

Um den Code zu verstehen, betrachten Sie ein Beispiel für eine verknüpfte Liste, 1 -> 2 -> 3 -> 4 -> 5 -> None.

Zuerst deklarieren wir drei Variablen, previous, current und next, die auf None, den Kopf der verketteten Eingabeliste, bzw. None zeigen. Als nächstes deklarieren wir eine while-Schleife, die endet, wenn der current-Knoten auf None zeigt.

Für jede Iteration:

• Wir speichern den nächsten Knoten des current Knotens im next Knoten.
• Setzen Sie den nächsten Knoten des current Knotens auf den previous Knoten.
• Setzen Sie den previous Knoten auf den current Knoten zurück.
• Setzen Sie den current Knoten auf den next Knoten zurück.

Die folgende Tabelle stellt dar, wie sich die Werte von Variablen, nämlich previous, current und next, ändern, wenn der Algorithmus für das obige Beispiel angewendet wird.

Die obigen Tabellenzellen zeigen den Wert an, der von einem Knoten gespeichert wird.