Programme Python : ajouter des éléments à la première et à la dernière position de la liste chaînée

En Python, une liste chaînée est une structure de données linéaire composée d'une séquence de nœuds, chaque nœud contenant une valeur et une référence au nœud suivant dans la liste chaînée.

Dans cet article, nous verrons comment ajouter des éléments à la première et à la dernière position d'une liste chaînée en Python.

Liste liée en Python

Une liste chaînée est une structure de données de référence utilisée pour stocker un ensemble d'éléments. D'une certaine manière, cela ressemble à un tableau, mais dans un tableau, les données sont stockées dans des emplacements mémoire contigus, alors que dans une liste chaînée, les données ne sont pas soumises à cette condition. Cela signifie que les données ne sont pas stockées de manière séquentielle mais aléatoire en mémoire.

Cela soulève une question : comment pouvons-nous accéder aux éléments d'une liste chaînée ? La réponse est assez intuitive dans une liste chaînée, un élément pointe vers un autre jusqu'à la fin de la liste.

Le début et la fin de la liste sont considérés comme des positions spéciales. Le début de la liste s'appelle la tête, il pointe vers le premier élément, et le dernier élément est spécial dans le sens où il pointe vers NULL.

Head -> data_1 -> data_2 -> … -> data_n -> NULL

Maintenant que nous savons comment accéder au début et à la fin d'une liste chaînée, voyons comment parcourir les éléments et accéder aux données de la liste chaînée.

Parcourir une liste chaînée est très simple, nous commençons simplement par le début et accédons au nœud suivant ; nous répétons ce processus jusqu'à ce que nous trouvions un nœud dont le nœud suivant est NULL. Quant à l'accès aux données dans un nœud, nous utilisons l'opérateur fléché "->".

Head->data

Nous avons désormais toute la compréhension nécessaire pour commencer à résoudre ce problème.

Ajouter un élément au début

Pour ajouter les données au début de la liste chaînée, nous devons prendre en compte l'en-tête de la liste chaînée. Chaque fois que nous ajoutons un nœud au début de la liste chaînée, la liste chaînée sera modifiée avec le nœud nouvellement ajouté. le premier nœud/tête de liste

.

Algorithme

Étape 1 – Créez le nouveau nœud

Étape 2 - Ajouter des données au nœud nouvellement créé

Étape 3 – Mettez à jour le lien du nouveau nœud et faites-le pointer vers le nœud principal actuel

Étape 4 - Placez maintenant le pointeur de tête sur le nœud nouvellement créé

REMARQUE - L'ordre de ces étapes est très important car si vous définissez d'abord le nœud nouvellement créé comme nœud principal, nous ne pourrons pas mettre à jour le lien du nouveau nœud, qui devrait idéalement pointer vers le nœud principal précédent. .

Exemple

class Node:
   def __init__(self, data):
      self.dataPart = data
      self.nextNode = None
class LinkedList:
   def __init__(self):
      self.headNode = None
   def showList(self):
      n = self.headNode
      while n is not None:
         print(n.dataPart, end='-')
         n = n.nextNode
      print('')
   def addBeginList(self, data):
      tempNode = Node(data)
      tempNode.nextNode = self.headNode
      self.headNode = tempNode
newLinkedList = LinkedList()
print("Printing the list before adding element : ")
newLinkedList.showList()
newLinkedList.addBeginList(10)
newLinkedList.addBeginList(25)
print("Printing the elements after adding at the beginning of the list")
newLinkedList.showList()

Sortie

Printing the list before adding any element :
\
Printing the elements after adding at the beginning of the list
25-10-\

Ajouter un élément à la fin

L'ajout d'éléments à la fin est logiquement différent de l'ajout au début de la liste. Cette fois, nous devons accéder au dernier nœud de la liste au lieu du premier nœud, c'est-à-dire la tête.

Maintenant le problème est de vérifier si la liste à laquelle on veut ajouter des éléments est une liste vide ou si elle contient déjà des éléments.

Si la liste est vide alors le nouveau nœud sera le premier nœud de la liste, et dans l'autre cas, ce sera le dernier nœud. Pour cela, nous devons vérifier si le nœud principal est Aucun ou non. traité vide de tête est Aucun, et pas vide sinon

.

Algorithme

Étape 1 – Créez un nouveau nœud.

Étape 2 - Ajoutez des données à la section de données du nœud.

Étape 3 – Assurez-vous que le nœud suivant du nœud nouvellement créé pointe vers le pointeur Aucun ou Null.

Étape 4 - Si la liste est vide, utilisez le nœud nouvellement créé comme nœud principal.

Étape 5 - Sinon, parcourez jusqu'à la fin de la liste, dernier nœud.

Étape 6 – Définissez le nœud suivant du dernier nœud sur le nœud nouvellement créé.

Exemple

class Node:
   def __init__(self, data):
      self.dataPart = data
      self.nextNode = None
class LinkedList:
   def __init__(self):
      self.headNode = None
   def showList(self):
      n = self.headNode
      while n is not None:
         print(n.dataPart, end='-')
         n = n.nextNode
      print("")
   def addEndList(self, data):
      tempNode = Node(data)
      if self.headNode is None:
         self.headNode = tempNode
      else:
         n = self.headNode
         while n.nextNode is not None:
            n = n.nextNode
            n.nextNode = tempNode
newLinkedList = LinkedList()
print("Printing the list before insertion : ")
newLinkedList.showList()
newLinkedList.addEndList(25)
newLinkedList.addEndList(10)
print("Printing the list after adding elements at the end of the list : ")
newLinkedList.showList()

Sortie

Printing the list before insertion :
\
Printing the list after adding elements at the end of the list :
25-10-\

Conclusion

Dans cet article, nous avons expliqué comment utiliser les classes Python pour implémenter une

liste liée et comment ajouter des éléments à une liste liée. Nous nous sommes concentrés sur l'ajout d'éléments au début et à la fin de la liste.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!