Grundlegendes zur Implementierung verknüpfter Listen in Python

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 funktioniert 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. Singly Linked List

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 technische Daten und einem 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 VerlinkteListe mit Kopf initialisiert auf Andere. Siehe den Code unten.

class LinkedList:

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

3. Wir haben Knoten funktioniert VerlinkteListe 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 VerlinkteListe 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 VerlinkteListe 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. Doubly Linked List

Eine doppelt verknüpfte Liste enthält zwei Zeiger mit dem vorheriger Knoten und dem 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.

Das vorheriger Zeiger des ersten Knotens ist null und dem 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 🙂