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.

.

É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éé.

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

Copier après la connexion

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

Copier après la connexion

Conclusion

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!