Comprendre l'implémentation des listes liées en Python

Les structures de données jouent un rôle clé dans le monde de la programmation. Ils nous aident à organiser nos données de manière à pouvoir être utilisées efficacement.

Dans ce tutoriel, nous allons en apprendre davantage sur le liste à lien unique et liste à double lien.

Une liste chaînée est une structure de données linéaire. Il ne stocke pas les données dans des emplacements de mémoire contigus comme des tableaux. Et chaque élément lié est appelé un nœud et ils sont connectés en utilisant le Pointeurs. La première nœud dans la liste chaînée s'appelle le front.

La taille de la liste chaînée est dynamique. Ainsi, nous pouvons avoir autant de nœuds que nous le souhaitons, à moins que le stockage ne soit disponible dans l'appareil.

Il existe deux types de listes liées. Voyons le tutoriel détaillé à leur sujet un par un.

#1. Singly Linked List

Une liste liée individuellement contient un pointeur unique reliée à la nœud suivant dans la liste chaînée. Nous devons stocker les données et le pointeur pour chaque nœud de la liste chaînée.

Le dernier nœud de la liste liée contient nul comme pointeur suivant pour représenter la fin de la liste chaînée.

Vous pouvez voir l'illustration d'un lien ci-dessous.

Maintenant, nous avons une compréhension complète d'une seule liste chaînée. Voyons les étapes pour l'implémenter en Python.

Implémentation de liste à lien unique

1. La première étape consiste à créer le nœud pour le liste liée.

Comment le créer?

In Python, nous pouvons facilement créer le nœud utilisant l' classe. La classe contient données et aiguille pour le nœud suivant.

Regardez le code du nœud.

class Node:

	def __init__(self, data):
		## data of the node
		self.data = data

		## next pointer
		self.next = None

Nous pouvons créer le nœud avec n'importe quel type de données en utilisant la classe ci-dessus. Nous le verrons dans un instant.

Maintenant, nous avons le nœud avec nous. Ensuite, nous devons créer une liste liée avec plusieurs nœuds. Créons une autre classe pour une liste liée.

2. Créez une classe appelée Liste Liée avec tête initialisée à Aucun. Voir le code ci-dessous.

class LinkedList:

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

3. Nous avons Nœud et Liste Liée cours avec nous. Comment insérer un nouveau nœud dans la liste chaînée? Une réponse simple pourrait être d'utiliser une méthode dans le Liste Liée classe. Ouais, ce serait bien. Écrivons une méthode pour insérer un nouveau nœud dans la liste chaînée.

Pour insérer un nouveau nœud dans la liste chaînée, nous devons suivre certaines étapes.

Voyons-les.

• Vérifiez si la tête est vide ou non.
• Si la tête est vide, attribuez le nouveau nœud à la tête.
• Si l'en-tête n'est pas vide, récupérez le dernier nœud de la liste chaînée.
• Assignez le nouveau nœud au dernier pointeur de nœud suivant.

Voyons le code pour insérer un nouveau nœud dans la liste chaînée.

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

Hourra! nous avons terminé la méthode pour insérer un nouveau nœud dans la liste chaînée. Comment pouvons-nous accéder aux données des nœuds à partir de la liste chaînée?

Pour accéder aux données de la liste liée, nous devons parcourir le lien en utilisant le pointeur suivant comme nous le faisons pour obtenir le dernier nœud de la méthode d'insertion. Écrivons une méthode dans le Liste Liée class pour imprimer toutes les données des nœuds dans la liste liée.

4. Suivez les étapes ci-dessous pour imprimer toutes les données des nœuds dans la liste liée.

• Initialiser une variable avec front.
• Écrivez une boucle qui itère jusqu'à ce que nous atteignions la fin de la liste chaînée.
  • Imprimez les données du nœud.
  • Déplacer le pointeur suivant

Voyons le 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')

Phew! nous avons terminé la création du lien avec les méthodes nécessaires. Testons la liste liée en l'instanciant avec des données.

Nous pouvons créer le nœud avec Noeud (1) code. Voyons le code complet de l'implémentation de la liste liée avec l'exemple d'utilisation.

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()

Exécutez le programme ci-dessus pour obtenir le résultat suivant.

1->2->3->4->5->6->7->Null

Voilà pour la liste chaînée. Maintenant, vous savez comment implémenter une liste à lien unique. Vous pouvez facilement implémenter la liste à double lien avec la connaissance de la liste à lien unique. Passons à la section suivante du didacticiel.

#2. Doubly Linked List

Une liste à double lien contient deux pointeurs reliée à la nœud précédent les nouveautés nœud suivant dans la liste chaînée. Nous devons stocker les données et deux pointeurs pour chaque nœud de la liste chaînée.

La pointeur précédent du premier nœud est nul les nouveautés pointeur suivant du dernier nœud est nul pour représenter la fin de la liste chaînée des deux côtés.

Vous pouvez voir l'illustration d'un lien ci-dessous.

La liste à liaison double comporte également des étapes similaires à celles de la liste à liaison unique en cours de mise en œuvre. Encore une fois, expliquer les mêmes choses sera ennuyeux pour vous. Parcourez le code à chaque étape et vous le comprendrez très rapidement. Allons-y.

Implémentation de liste doublement liée

1. Création d'un nœud pour la liste doublement liée avec le pointeur de nœud précédent, les données et le pointeur de nœud suivant.

class Node:

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

		## data of the node
		self.data = data

		## next pointer
		self.next = None

2. Classe de liste double chaînée.

class LinkedList:

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

3. Une méthode pour insérer un nouveau nœud dans la liste doublement liée.

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. Une méthode pour afficher les données de liste à double liaison.

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()

Nous avons vu le code de la liste à double chaînage. Et il n'y a pas de code pour l'utilisation de la classe de liste à double lien. C'est pour toi. Utilisez la classe de liste à double lien similaire à la liste à lien unique. Amusez-vous bien 🙂

Conclusion

Vous pouvez trouver de nombreux problèmes basés sur des listes chaînées. Mais, vous devez connaître l'implémentation de base du lien que vous avez appris dans ce tutoriel. J'espère que vous avez passé un bon moment à apprendre le nouveau concept.

Codage heureux 🙂