• Assurez la sécurité des applications de la bonne manière! Détectez, protégez, surveillez, accélérez et plus encore…
  • 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. Liste liée individuellement

    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 les liste liée.

    Comment le créer?

    In Python, nous pouvons facilement créer le nœud utilisant l' classe. La classe contient de data ainsi que d'un aiguille Pour les 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. Liste doublement liée

    Une liste à double lien contient deux pointeurs reliée à la nœud précédent et les 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 et les 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 🙂