Datenstrukturen spielen in der Programmierwelt eine Schlüsselrolle. Sie helfen uns, unsere Daten so zu organisieren, dass sie effizient genutzt werden können.
In diesem Tutorial lernen wir die einfach verknüpfte Liste und die doppelt verknüpfte Liste kennen.
Eine verkettete Liste ist eine lineare Datenstruktur. Es speichert die Daten nicht in zusammenhängenden Speicherorten wie Arrays. Und jedes Element in linked wird als Knoten bezeichnet und sie werden mit den Zeigern verbunden. Der erste Knoten in der verknüpften Liste wird Kopf genannt.
Die Größe der verknüpften Liste ist dynamisch. Wir können also beliebig viele Knoten haben, es sei denn, der Speicher ist im Gerät verfügbar.
Es gibt zwei Arten von verknüpften Listen. Sehen wir uns das detaillierte Tutorial nacheinander an.
Inhaltsverzeichnis
#1. Einfach verkettete Liste
Eine einfach verknüpfte Liste enthält einen einzelnen Zeiger, der mit dem nächsten Knoten in der verknüpften Liste verbunden ist. Wir müssen die Daten und den Zeiger für jeden Knoten in der verknüpften Liste speichern.
Der letzte Knoten in der verknüpften Liste enthält null als nächsten Zeiger, um das Ende der verknüpften Liste darzustellen.
Sie können die Abbildung eines Links unten sehen.
Jetzt haben wir ein vollständiges Verständnis einer einfach verknüpften Liste. Sehen wir uns die Schritte zur Implementierung in Python an.
Einfach verknüpfte Listenimplementierung
1. Der erste Schritt besteht darin, den Knoten für die verknüpfte Liste zu erstellen.
Wie erstelle ich es?
In Python können wir den Knoten einfach mit der Klasse erstellen. Die Klasse enthält Daten und einen Zeiger für den nächsten Knoten.
Sehen Sie sich den Code für den Knoten an.
class Node: def __init__(self, data): ## data of the node self.data = data ## next pointer self.next = None
Wir können den Knoten mit jeder Art von Daten erstellen, indem wir die obige Klasse verwenden. Wir werden es gleich sehen.
Jetzt haben wir den Knoten bei uns. Als nächstes müssen wir eine verknüpfte Liste mit mehreren Knoten erstellen. Lassen Sie uns eine weitere Klasse für eine verknüpfte Liste erstellen.
2. Erstellen Sie eine Klasse namens LinkedList, deren Kopf auf None initialisiert ist. Siehe Code unten.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Wir haben Node- und LinkedList-Klassen dabei. Wie fügen wir einen neuen Knoten in die verknüpfte Liste ein? Eine einfache Antwort könnte die Verwendung einer Methode in der LinkedList-Klasse sein. Ja, das wäre schön. Lassen Sie uns eine Methode schreiben, um einen neuen Knoten in die verknüpfte Liste einzufügen.
Um einen neuen Knoten in die verknüpfte Liste einzufügen, müssen wir bestimmte Schritte befolgen.
Lass sie uns sehen.
- Überprüfen Sie, ob der Kopf leer ist oder nicht.
- Wenn der Kopf leer ist, weisen Sie den neuen Knoten dem Kopf zu.
- Wenn der Kopf nicht leer ist, holen Sie sich den letzten Knoten der verknüpften Liste.
- Weisen Sie den neuen Knoten dem nächsten Zeiger des letzten Knotens zu.
Sehen wir uns den Code zum Einfügen eines neuen Knotens in die verknüpfte Liste an.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node != None: last_node = last_node.next ## assigning the new node to the next pointer of last node last_node.next = new_node else: ## head is empty ## assigning the node to head self.head = new_node
Hurra! Wir haben die Methode zum Einfügen eines neuen Knotens in die verknüpfte Liste abgeschlossen. Wie können wir auf die Knotendaten aus der verknüpften Liste zugreifen?
Um auf die Daten aus der verknüpften Liste zuzugreifen, müssen wir die Verknüpfung mit dem next-Zeiger durchlaufen, so wie wir es tun, um den letzten Knoten in der Einfügemethode zu erhalten. Lassen Sie uns eine Methode innerhalb der LinkedList-Klasse schreiben, um alle Knotendaten in der verknüpften Liste zu drucken.
4. Befolgen Sie die nachstehenden Schritte, um alle Knotendaten in der verknüpften Liste zu drucken.
- Initialisieren Sie eine Variable mit Kopf.
- Schreiben Sie eine Schleife, die wiederholt wird, bis wir das Ende der verknüpften Liste erreichen.
- Drucken Sie die Knotendaten.
- Bewegen Sie den nächsten Zeiger
Sehen wir uns den Code an.
class LinkedList:
####
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
Puh! Wir haben die Verknüpfung mit den erforderlichen Methoden erstellt. Lassen Sie uns die verknüpfte Liste testen, indem wir sie mit einigen Daten instanziieren.
Wir können den Knoten mit Node(1)-Code erstellen. Sehen wir uns den vollständigen Code der Implementierung der verknüpften Liste zusammen mit der Beispielverwendung an.
class Node:
def __init__(self, data):
## data of the node
self.data = data
## next pointer
self.next = None
class LinkedList:
def __init__(self):
## initializing the head with None
self.head = None
def insert(self, new_node):
## check whether the head is empty or not
if self.head:
## getting the last node
last_node = self.head
while last_node.next != None:
last_node = last_node.next
## assigning the new node to the next pointer of last node
last_node.next = new_node
else:
## head is empty
## assigning the node to head
self.head = new_node
def display(self):
## variable for iteration
temp_node = self.head
## iterating until we reach the end of the linked list
while temp_node != None:
## printing the node data
print(temp_node.data, end='->')
## moving to the next node
temp_node = temp_node.next
print('Null')
if __name__ == '__main__':
## instantiating the linked list
linked_list = LinkedList()
## inserting the data into the linked list
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))
## printing the linked list
linked_list.display()
Führen Sie das obige Programm aus, um das folgende Ergebnis zu erhalten.
1->2->3->4->5->6->7->Null
Das war’s für die verknüpfte Liste. Jetzt wissen Sie, wie Sie eine einfach verknüpfte Liste implementieren. Sie können die doppelt verkettete Liste mit der Kenntnis der einfach verketteten Liste leicht implementieren. Lassen Sie uns in den nächsten Abschnitt des Tutorials eintauchen.
#2. Doppelt verkettete Liste
Eine doppelt verknüpfte Liste enthält zwei Zeiger, die mit dem vorherigen Knoten und dem nächsten Knoten in der verknüpften Liste verbunden sind. Wir müssen die Daten und zwei Zeiger für jeden Knoten in der verknüpften Liste speichern.
Der vorherige Zeiger des ersten Knotens ist null und der nächste Zeiger des letzten Knotens ist null, um das Ende der verknüpften Liste auf beiden Seiten darzustellen.
Sie können die Abbildung eines Links unten sehen.
Die doppelt verknüpfte Liste hat auch ähnliche Schritte wie die einfach verknüpfte Liste in der Implementierung. Wieder die gleichen Dinge zu erklären, wird für Sie langweilig sein. Gehen Sie den Code in jedem Schritt durch und Sie werden ihn sehr schnell verstehen. Lass uns gehen.
Implementierung von doppelt verknüpften Listen
1. Erstellen eines Knotens für die doppelt verknüpfte Liste mit dem vorherigen Knotenzeiger, den Daten und dem nächsten Knotenzeiger.
class Node: def __init__(self, data): ## previous pointer self.prev = None ## data of the node self.data = data ## next pointer self.next = None
2. Doppelt verkettete Listenklasse.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Ein Verfahren zum Einfügen eines neuen Knotens in die doppelt verknüpfte Liste.
class LinkedList: #### def insert(self, new_node): ## check whether the head is empty or not if self.head: ## getting the last node last_node = self.head while last_node.next != None: last_node = last_node.next ## assigning the last node to the previous pointer of the new node new_node.prev = last_node ## assigning the new node to the next pointer of last node last_node.next = new_node
4. Ein Verfahren zum Anzeigen der doppelt verknüpften Listendaten.
class LinkedList:
####
def display(self):
## printing the data in normal order
print("Normal Order: ", end='')
temp_node = self.head
while temp_node != None:
print(temp_node.data, end=' ')
temp_node = temp_node.next
print()
## printing the data in reverse order using previous pointer
print("Reverse Order: ", end='')
## getting the last node
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 der doppelt verknüpften Liste gesehen. Und es gibt keinen Code für die Verwendung der doppelt verknüpften Listenklasse. Das ist für dich. Verwenden Sie die doppelt verknüpfte Listenklasse ähnlich wie die einfach verknüpfte Liste. Viel Spaß 🙂
Fazit
Sie können viele Probleme anhand von verknüpften Listen finden. Sie müssen jedoch die grundlegende Implementierung von Link kennen, die Sie in diesem Tutorial gelernt haben. Ich hoffe, Sie hatten viel Spaß beim Erlernen des neuen Konzepts.
Viel Spaß beim Programmieren 🙂