• Erledigen Sie die Anwendungssicherheit auf die richtige Weise! Erkennen, schützen, überwachen, beschleunigen und mehr…
  • Datenstrukturen spielen eine Schlüsselrolle in der Programmierwelt. Sie helfen uns, unsere Daten so zu organisieren, dass sie effizient genutzt werden können.

    In diesem Tutorial lernen wir das kennen einfach verknüpfte Liste und doppelt verknüpfte Liste.

    Eine verknüpfte Liste ist eine lineare Datenstruktur. Die Daten werden nicht an zusammenhängenden Speicherorten wie Arrays gespeichert. Und jedes Element in verknüpft heißt a Knoten und sie sind mit dem verbunden Zeiger. Die erste Knoten in der verknüpften Liste heißt das ganzer.

    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. Schauen wir uns das ausführliche Tutorial nacheinander an.

    # 1. Einfach verknüpfte Liste

    Eine einfach verknüpfte Liste enthält a einzelner Zeiger mit dem nächster Knoten in der verknüpften Liste. 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ächster Zeiger für das Ende der verknüpften Liste.

    Sie können die Abbildung eines unten verlinkten sehen.

    Jetzt haben wir ein umfassendes Verständnis für eine einfach verknüpfte Liste. Sehen wir uns die Schritte zur Implementierung in Python an.

    Implementierung einer einfach verknüpften Liste

    1. Der erste Schritt ist das Erstellen der Knoten für die verknüpfte Liste.

    Wie erstelle ich es?

    In Pythonkönnen wir das leicht schaffen Knoten Verwendung der Klasse. Die Klasse enthält Datum sowie ein Zeiger für die nächster 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

    Mit der obigen Klasse können wir den Knoten mit jedem Datentyp erstellen. 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. Erstellen wir eine weitere Klasse für eine verknüpfte Liste.

    2. Erstellen Sie eine Klasse namens LinkedList mit Kopf initialisiert auf Keine. Siehe den Code unten.

    class LinkedList:
    
    	def __init__(self):
    		## initializing the head with None
    		self.head = None

    3. Wir haben Knoten und LinkedList Unterricht bei uns. Wie fügen wir einen neuen Knoten in die verknüpfte Liste ein? Eine einfache Antwort könnte die Verwendung einer Methode in der sein LinkedList Klasse. Ja, das wäre schön. Schreiben wir eine Methode, 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 ausführen.

    Mal sehen.

    • Überprüfen Sie, ob der Kopf leer ist oder nicht.
    • Wenn der Kopf leer ist, weisen Sie dem Kopf den neuen Knoten zu.
    • Wenn der Kopf nicht leer ist, rufen Sie den letzten Knoten der verknüpften Liste ab.
    • 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 über die verknüpfte Liste auf die Knotendaten zugreifen?

    Um auf die Daten aus der verknüpften Liste zuzugreifen, müssen wir die verknüpfte Liste mit der durchlaufen nächster Zeiger wie wir es tun, um den letzten Knoten in der Einfügemethode zu erhalten. Schreiben wir eine Methode in die LinkedList Klasse zum Drucken aller Knotendaten in der verknüpften Liste.

    4. Führen Sie die folgenden Schritte aus, um alle Knotendaten in der verknüpften Liste zu drucken.

    • Initialisieren Sie eine Variable mit ganzer.
    • Schreiben Sie eine Schleife, die iteriert, bis das Ende der verknüpften Liste erreicht ist.
      • Drucken Sie die Knotendaten.
      • Bewegen Sie den nächsten Zeiger

    Mal sehen, den Code.

    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 Erstellung der mit den erforderlichen Methoden verknüpften abgeschlossen. Testen wir die verknüpfte Liste, indem wir sie mit einigen Daten instanziieren.

    Wir können den Knoten mit erstellen Knoten (1) Code. 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 verknüpfte Liste mit dem Wissen der einfach verknüpften Liste einfach implementieren. Lassen Sie uns in den nächsten Abschnitt des Tutorials eintauchen.

    # 2. Doppelt verknüpfte Liste

    Eine doppelt verknüpfte Liste enthält zwei Zeiger mit dem vorheriger Knoten und der nächster Knoten in der verknüpften Liste. Wir müssen die Daten und zwei Zeiger für jeden Knoten in der verknüpften Liste speichern.

    Der vorheriger Zeiger des ersten Knotens ist null und der nächster Zeiger des letzten Knotens ist null zur Darstellung des Endes der verknüpften Liste auf beiden Seiten.

    Sie können die Abbildung eines unten verlinkten sehen.

    Die doppelt verknüpfte Liste hat ähnliche Schritte wie die einfach verknüpfte Liste in der Implementierung. Es wird Ihnen langweilig sein, die gleichen Dinge noch einmal zu erklären. Gehen Sie den Code in jedem Schritt durch und Sie werden ihn sehr schnell verstehen. Lass uns gehen.

    Implementierung einer doppelt verknüpften Liste

    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 verknüpfte Listenklasse.

    class LinkedList:
    
    	def __init__(self):
    		## initializing the head with None
    		self.head = None

    3. Eine Methode 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. Eine Methode 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 der einfach verknüpften Liste. Viel Spaß 🙂

    Fazit

    Sie können viele Probleme basierend auf verknüpften Listen finden. Sie müssen jedoch die grundlegende Implementierung des Links kennen, die Sie in diesem Lernprogramm gelernt haben. Ich hoffe, Sie hatten viel Spaß beim Erlernen des neuen Konzepts.

    Viel Spaß beim Codieren 🙂