Datenstrukturen sind von zentraler Bedeutung in der Welt der Programmierung. Sie ermöglichen es uns, Daten so zu organisieren, dass sie effizient verarbeitet werden können.
In dieser Anleitung werden wir uns mit der einfach verketteten Liste und der doppelt verketteten Liste beschäftigen.
Eine verkettete Liste ist eine lineare Datenstruktur. Im Gegensatz zu Arrays werden Daten nicht in aufeinanderfolgenden Speicherbereichen abgelegt. Stattdessen wird jedes Element als Knoten bezeichnet, und diese Knoten sind durch Zeiger miteinander verbunden. Der erste Knoten in der Liste wird als Kopf bezeichnet.
Die Größe einer verketteten Liste ist dynamisch, was bedeutet, dass wir beliebig viele Knoten hinzufügen können, solange der Speicher des Geräts dies zulässt.
Es gibt zwei Haupttypen von verketteten Listen. Lassen Sie uns diese nacheinander genauer betrachten.
Einfach verkettete Liste
Eine einfach verkettete Liste verwendet einen einzigen Zeiger, der auf den nächsten Knoten in der Liste verweist. Jeder Knoten enthält also die Daten und einen Zeiger zum nächsten Knoten.
Der letzte Knoten in einer einfach verketteten Liste hat einen Null-Zeiger als Nachfolger, um das Ende der Liste zu kennzeichnen.
Sie können sich die Darstellung einer solchen Verknüpfung unten ansehen.
Nachdem wir nun ein gutes Verständnis von einfach verketteten Listen haben, schauen wir uns an, wie man sie in Python implementiert.
Implementierung einer einfach verketteten Liste
1. Der erste Schritt ist die Erstellung der Knotenstruktur für die Liste.
Wie geht das?
In Python können wir einen Knoten mit Hilfe einer Klasse definieren. Diese Klasse speichert die Daten und den Zeiger auf den nächsten Knoten.
Hier ist der Code für den Knoten:
class Node:
def __init__(self, data):
## Daten des Knotens
self.data = data
## Zeiger auf den nächsten Knoten
self.next = None
Mit dieser Klasse können wir Knoten mit beliebigen Datentypen erstellen. Das werden wir gleich sehen.
Jetzt, da wir die Knotenstruktur haben, brauchen wir eine Möglichkeit, eine verkettete Liste aus mehreren Knoten zu erstellen. Dazu erstellen wir eine weitere Klasse für die gesamte Liste.
2. Erstellen Sie eine Klasse namens LinkedList, in der der Kopf (head) standardmäßig auf None gesetzt ist. Siehe den Code unten:
class LinkedList:
def __init__(self):
## Initialisierung des Kopfes mit None
self.head = None
3. Nun haben wir sowohl die Node- als auch die LinkedList-Klasse. Wie fügen wir nun einen neuen Knoten in die Liste ein? Eine einfache Möglichkeit wäre, eine Methode in der LinkedList-Klasse zu verwenden. Ja, das ist eine gute Idee. Schreiben wir also eine Methode, um einen neuen Knoten in die Liste einzufügen.
Um einen neuen Knoten in die Liste einzufügen, müssen wir folgende Schritte befolgen:
Schauen wir sie uns an:
- Überprüfen, ob der Kopf leer ist (also die Liste).
- Wenn der Kopf leer ist, weisen Sie den neuen Knoten dem Kopf zu.
- Wenn der Kopf nicht leer ist, suchen Sie den letzten Knoten der Liste.
- Weisen Sie den neuen Knoten dem next-Zeiger des letzten Knotens zu.
Hier ist der Code zum Einfügen eines neuen Knotens in die verkettete Liste:
class LinkedList:
####
def insert(self, new_node):
## Überprüfen, ob der Kopf leer ist
if self.head:
## Suche nach dem letzten Knoten
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## Zuweisen des neuen Knotens zum next-Zeiger des letzten Knotens
last_node.next = new_node
else:
## Der Kopf ist leer
## Zuweisen des Knotens zum Kopf
self.head = new_node
Super! Wir haben die Methode zum Einfügen eines neuen Knotens in die Liste fertiggestellt. Wie können wir nun auf die Daten der Knoten in der Liste zugreifen?
Um auf die Daten zuzugreifen, müssen wir der Verkettung durch die next-Zeiger folgen, so wie wir es getan haben, um den letzten Knoten in der Einfügemethode zu finden. Schreiben wir also eine Methode in der LinkedList-Klasse, um alle Knotendaten der Liste auszugeben.
4. Hier sind die Schritte zum Anzeigen aller Knotendaten der Liste:
- Initialisieren Sie eine Variable mit dem Kopf.
- Schreiben Sie eine Schleife, die so lange ausgeführt wird, bis das Ende der Liste erreicht ist.
- Geben Sie die Knotendaten aus.
- Gehen Sie zum nächsten Zeiger.
Hier ist der Code:
class LinkedList:
####
def display(self):
## Variable für die Iteration
temp_node = self.head
## Iterieren, bis das Ende der Liste erreicht ist
while temp_node != None:
## Ausgeben der Knotendaten
print(temp_node.data, end='->')
## Weitergehen zum nächsten Knoten
temp_node = temp_node.next
print('Null')
Puh! Wir haben die Liste mit den benötigten Methoden erstellt. Testen wir nun die Liste, indem wir sie mit einigen Daten instanziieren.
Wir können einen Knoten mit dem Code Node(1) erstellen. Hier ist der vollständige Code der Implementierung der Liste zusammen mit einem Beispiel:
class Node:
def __init__(self, data):
## Daten des Knotens
self.data = data
## Zeiger auf den nächsten Knoten
self.next = None
class LinkedList:
def __init__(self):
## Initialisierung des Kopfes mit None
self.head = None
def insert(self, new_node):
## Überprüfen, ob der Kopf leer ist
if self.head:
## Suche nach dem letzten Knoten
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## Zuweisen des neuen Knotens zum next-Zeiger des letzten Knotens
last_node.next = new_node
else:
## Der Kopf ist leer
## Zuweisen des Knotens zum Kopf
self.head = new_node
def display(self):
## Variable für die Iteration
temp_node = self.head
## Iterieren, bis das Ende der Liste erreicht ist
while temp_node != None:
## Ausgeben der Knotendaten
print(temp_node.data, end='->')
## Weitergehen zum nächsten Knoten
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## Instanziieren der Liste
linked_list = LinkedList()
## Einfügen von Daten in die Liste
linked_list.insert(Node(1))
linked_list.insert(Node(2))
linked_list.insert(Node(3))
linked_list.insert(Node(4))
linked_list.insert(Node(5))
linked_list.insert(Node(6))
linked_list.insert(Node(7))
## Ausgeben der Liste
linked_list.display()
Führen Sie das obige Programm aus, um folgende Ausgabe zu erhalten:
1->2->3->4->5->6->7->Null
Das war es mit der einfach verketteten Liste. Jetzt wissen Sie, wie man eine solche Liste implementiert. Mit diesem Wissen können Sie die doppelt verkettete Liste leicht implementieren. Gehen wir nun zum nächsten Abschnitt dieser Anleitung.
Doppelt verkettete Liste
Eine doppelt verkettete Liste verwendet zwei Zeiger: einen, der auf den vorherigen Knoten und einen, der auf den nächsten Knoten in der Liste zeigt. Jeder Knoten enthält also die Daten sowie zwei Zeiger.
Der previous-Zeiger des ersten Knotens und der next-Zeiger des letzten Knotens sind jeweils null, um die Enden der Liste zu markieren.
Sie können sich die Darstellung einer solchen Verknüpfung unten ansehen.
Die Implementierung einer doppelt verketteten Liste ähnelt der einer einfach verketteten Liste. Die wiederholte Erklärung wäre wahrscheinlich langweilig für Sie. Gehen Sie stattdessen einfach den Code Schritt für Schritt durch, und Sie werden es schnell verstehen. Los geht’s!
Implementierung einer doppelt verketteten Liste
1. Erstellen einer Knotenstruktur für die doppelt verkettete Liste, die einen Zeiger zum vorherigen Knoten, die Daten und einen Zeiger zum nächsten Knoten enthält.
class Node:
def __init__(self, data):
## Zeiger zum vorherigen Knoten
self.prev = None
## Daten des Knotens
self.data = data
## Zeiger zum nächsten Knoten
self.next = None
2. Klasse für die doppelt verkettete Liste.
class LinkedList:
def __init__(self):
## Initialisierung des Kopfes mit None
self.head = None
3. Eine Methode zum Einfügen eines neuen Knotens in die doppelt verkettete Liste.
class LinkedList:
####
def insert(self, new_node):
## Überprüfen, ob der Kopf leer ist
if self.head:
## Suchen nach dem letzten Knoten
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## Zuweisen des letzten Knotens zum previous-Zeiger des neuen Knotens
new_node.prev = last_node
## Zuweisen des neuen Knotens zum next-Zeiger des letzten Knotens
last_node.next = new_node
4. Eine Methode zum Ausgeben der Daten der doppelt verketteten Liste.
class LinkedList:
####
def display(self):
## Ausgeben der Daten in normaler Reihenfolge
print("Normale Reihenfolge: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## Ausgeben der Daten in umgekehrter Reihenfolge mit dem previous-Zeiger
print("Umgekehrte Reihenfolge: ", end='')
## Suchen nach dem letzten Knoten
last_node = self.head
while last_node.next != None:
last_node = last_node.next
temp_node = last_node
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.prev
print()
Wir haben den Code für die doppelt verkettete Liste gesehen. Es gibt keinen Code zur Verwendung der Klasse für die doppelt verkettete Liste – das ist Ihre Aufgabe! Verwenden Sie die Klasse für die doppelt verkettete Liste auf ähnliche Weise wie die einfach verkettete Liste. Viel Spaß dabei! 🙂
Fazit
Es gibt viele Probleme, die man mithilfe von verketteten Listen lösen kann. Sie müssen jedoch die grundlegende Implementierung, die wir in dieser Anleitung besprochen haben, beherrschen. Ich hoffe, Sie haben beim Lernen dieses neuen Konzepts viel Spaß gehabt.
Viel Spaß beim Programmieren! 🙂