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 les utiliser efficacement.
Dans ce didacticiel, nous allons en apprendre davantage sur la liste à liaison simple et la liste à liaison double.
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 à l’aide des pointeurs. Le premier nœud de la liste chaînée est appelé la tête.
La taille de la liste chaînée est dynamique. Ainsi, nous pouvons avoir n’importe quel nombre de nœuds comme 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.
Table des matières
#1. Liste liée individuellement
Une liste chaînée contient un seul pointeur connecté au 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 null comme pointeur suivant pour représenter la fin de la liste liée.
Vous pouvez voir l’illustration d’un lien ci-dessous.
Maintenant, nous avons une compréhension complète d’une liste liée individuellement. Voyons les étapes pour l’implémenter en Python.
Implémentation d’une liste chaînée unique
1. La première étape consiste à créer le nœud de la liste chaînée.
Comment le créer ?
En Python, nous pouvons facilement créer le nœud en utilisant la classe. La classe contient des données et un pointeur 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 chaînée avec plusieurs nœuds. Créons une autre classe pour une liste chaînée.
2. Créez une classe appelée LinkedList avec head initialisé à None. Voir le code ci-dessous.
class LinkedList: def __init__(self): ## initializing the head with None self.head = None
3. Nous avons des classes Node et LinkedList 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 la classe LinkedList. 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, affectez le nouveau nœud à la tête.
- Si la tête n’est pas vide, récupère le dernier nœud de la liste chaînée.
- Affectez le nouveau nœud au pointeur suivant du dernier nœud.
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 lié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 la classe LinkedList pour imprimer toutes les données de nœuds dans la liste liée.
4. Suivez les étapes ci-dessous pour imprimer toutes les données de nœuds dans la liste liée.
- Initialiser une variable avec head.
- É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 chaînée en l’instanciant avec des données.
Nous pouvons créer le nœud avec le code Node(1). Voyons le code complet de l’implémentation de la liste chaîné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
C’est tout pour la liste chaînée. Maintenant, vous savez comment implémenter une liste à liaison simple. Vous pouvez facilement implémenter la liste à double liaison avec la connaissance de la liste à liaison simple. Passons à la section suivante du didacticiel.
#2. Liste doublement chaînée
Une liste à double liaison contient deux pointeurs connectés au nœud précédent et au nœud suivant dans la liste liée. Nous devons stocker les données et deux pointeurs pour chaque nœud de la liste chaînée.
Le pointeur précédent du premier nœud est nul et le 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 à double liaison comporte également des étapes similaires à celles de la liste à liaison simple dans la mise en œuvre. Expliquer à nouveau 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 chaîné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 doublement 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 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.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 la liste doublement chaînée.
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 doublement chaînée. Et il n’y a pas de code pour l’utilisation de la classe de liste doublement liée. C’est pour toi. Utilisez la classe de liste à double liaison similaire à la liste à liaison simple. Amusez-vous 🙂
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.
Bon codage 🙂