Verständnis der Implementierung von Linked Lists in Python

Datenstrukturen spielen in der Welt der Programmierung eine Schlüsselrolle. Sie helfen uns, unsere Daten so zu organisieren, dass sie effizient genutzt werden können.

In diesem Tutorium werden wir uns mit dem einfach verkettete Liste und doppelt verkettete Liste.

Eine verkettete Liste ist eine lineare Datenstruktur. Sie speichert die Daten nicht an zusammenhängenden Speicherplätzen wie Arrays. Und jedes Element in einer verknüpften Liste wird als Knoten und sie werden über die Zeiger. Die erste Knoten in der verknüpften Liste wird als Kopf.

Die Größe der verknüpften Liste ist dynamisch. Wir können also so viele Knoten haben, wie wir wollen, solange der Speicherplatz im Gerät nicht ausreicht.

Es gibt zwei Arten von verknüpften Listen. Schauen wir uns das ausführliche Tutorial über sie nacheinander an.

#1. Einzeln verknüpfte Liste

Eine einfach verkettete Liste enthält eine einzelner Zeiger verbunden mit dem nächster Knoten in der verketteten Liste. Wir müssen die Daten und 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.

Unten sehen Sie die Abbildung eines Links.

Jetzt haben wir ein umfassendes Verständnis einer einfach verketteten Liste. Schauen wir uns die Schritte an, um sie in Python zu implementieren.

Implementierung einer einfach verknüpften Liste

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

Wie erstellt man sie?

Unter Pythonkönnen wir leicht die Knoten unter Verwendung der Klasse. Die Klasse enthält Daten und eine 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 jeder Art von Daten 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. Lassen Sie uns eine weitere Klasse für eine verkettete Liste erstellen.

2. Erstellen Sie eine Klasse namens LinkedList mit Kopf initialisiert zu Keine. Siehe den nachstehenden Code.

class LinkedList:

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

3. Wir haben Knotenpunkt und LinkedList Klassen mit uns. Wie fügt man einen neuen Knoten in die verknüpfte Liste ein? Eine einfache Antwort könnte die Verwendung einer Methode in der Klasse 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 befolgen.

Zeigen Sie sie uns.

• Prüfen Sie, ob der Kopf leer ist oder nicht.
• Wenn der Kopf leer ist, wird der neue Knoten dem Kopf zugeordnet.
• Wenn der Kopf nicht leer ist, wird der letzte Knoten der verknüpften Liste ermittelt.
• Weisen Sie den neuen Knoten dem letzten Knoten next pointer 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 Daten des Knotens in der verknüpften Liste zugreifen?

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

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

• Initialisieren Sie eine Variable mit Kopf.
• Schreiben Sie eine Schleife, die so lange wiederholt wird, bis das Ende der verknüpften Liste erreicht ist.
  • Drucken Sie die Daten des Knotens.
  • Bewegen Sie den nächsten Zeiger

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

Wir können den Knoten erstellen mit Knoten(1) Code. Sehen wir uns den vollständigen Code der Implementierung der verknüpften Liste zusammen mit dem Anwendungsbeispiel 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 mit der verknüpften Liste. Jetzt wissen Sie, wie man eine einfach verkettete Liste implementiert. Mit dem Wissen über die einfach verkettete Liste können Sie leicht die doppelt verkettete Liste implementieren. Tauchen wir ein in den nächsten Abschnitt des Tutorials.

#2. Doppelt verknüpfte Liste

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

Die vorheriger Zeiger des ersten Knotens ist null und die nächster Zeiger des letzten Knotens ist null um das Ende der verketteten Liste auf beiden Seiten darzustellen.

Unten sehen Sie die Abbildung eines Links.

Die doppelt verkettete Liste hat auch ähnliche Schritte wie die einfach verkettete Liste in der Umsetzung. Nochmals 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. Los geht's.

Implementierung einer doppelt verknüpften Liste

1. Erstellen eines Knotens für die doppelt verkettete Liste mit dem Zeiger auf den vorherigen Knoten, den Daten und dem Zeiger auf den nächsten Knoten.

class Node:

	def __init__(self, data):
		## previous pointer
		self.prev = None

		## data of the node
		self.data = data

		## next pointer
		self.next = None

2. Klasse der doppelt verknüpften Listen.

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 verkettete 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 zur Anzeige der Daten der doppelt verknüpften Liste.

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 verketteten Liste gesehen. Und es gibt keinen Code für die Verwendung der doppelt verknüpften Listenklasse. Das ist für Sie. Verwenden Sie die Klasse der doppelt verketteten Liste ähnlich wie die einfach verkettete Liste. Viel Spaß 🙂 .

Schlussfolgerung

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

Prüfen Sie auch, wie Sie die Python-Index Methode, um den Index eines Elements in einer Liste zu finden.

Viel Spaß beim Codieren 😀