Comment insérer et afficher des nœuds dans une liste python à chaînage unique ? (exemple de code)

Comment insérer et afficher des nœuds dans une liste python à chaînage unique ? L'article suivant vous aidera à comprendre ce qu'est une liste à lien unique et comment effectuer certaines opérations très basiques sur une liste à lien unique, telles que l'insertion et la sortie. J'espère qu'il vous sera utile.

Qu'est-ce qu'une liste à chaînage unique ?

Tout d'abord, avant de comprendre les listes à chaînage unique, nous devons comprendre ce qu'est un nœud.

Le nœud est l'élément constitutif de la liste chaînée, qui se compose de deux parties :

1. Partie Données : utilisée pour contenir des données

2. pointez vers le pointeur suivant vers l'emplacement du nœud.

Dans une liste à chaînage unique, la partie adresse de chaque nœud contient des informations sur l'emplacement du nœud suivant ; cela forme une série de chaînes ou de liens. Le premier nœud de la liste chaînée est suivi par le pointeur principal ; le dernier nœud pointe vers Aucun.

Regardons le diagramme suivant pour mieux comprendre cela :

Remarque : dans le diagramme ci-dessus, le dernier élément 1 pointe vers Aucun. Même si ces nœuds sont dessinés de manière contiguë les uns aux autres, ils peuvent ou non se trouver dans des emplacements de mémoire contigus.

Comment insérer et afficher des nœuds dans une liste à chaînage unique ?

1. Créez une liste à chaînage unique

Tout d'abord, vous devez créer un nœud pour créer une liste à chaînage unique. Pour ce faire, nous créons une classe Node en utilisant les propriétés data et nextNode. Comme mentionné précédemment, l'attribut data contiendra les données et nextNode pointera simplement vers le nœud suivant dans la liste chaînée. Nous définissons la valeur par défaut de nextNode sur None. Vous pouvez utiliser les méthodes getter et setter pour ce faire.

Maintenant que la classe Node a été créée, il est temps de créer la classe LinkedList. Celui-ci n'a qu'un seul attribut, la tête. Par défaut, cela indiquera « Aucun ». Si l'en-tête pointe sur "Aucun", cela signifie que la liste chaînée est vide. Pour garder une trace du nombre de nœuds dans la liste chaînée, nous pouvons ajouter un attribut size à la classe LinkedList et lui attribuer la valeur par défaut 0.

2. Insérer un nœud

C'est la méthode de la classe LinkedList. Nous pouvons insérer un nouveau nœud n'importe où dans la liste chaînée, mais pour garder le codage simple et efficace, nous ajouterons toujours de nouveaux nœuds au début de la liste chaînée, en d'autres termes, la tête pointera toujours vers le nœud le plus récemment ajouté ; .

Si nous ajoutons un nouveau nœud à la fin de la liste, nous devons effectuer un travail supplémentaire pour trouver la fin de la liste, puis l'ajouter. C'est une opération inutile. Cependant, cela peut être fait si vous conservez un autre pointeur, appelons-le pointeur de queue, pointant vers le dernier nœud.

Ci-dessous, nous présentons l'ancienne méthode, c'est-à-dire comment insérer un nœud au début de la liste chaînée.

Supposons que nous devions ajouter 7 à la liste chaînée, nous devons effectuer les étapes suivantes :

● Créer un objet nœud, où 7 représente les données, et les points de nœud suivants vers le nœud principal

Quantity　Pointez le pointeur principal vers ce nouveau nœud

Enfin, augmentez l'attribut size de 1 et renvoyez True si l'insertion est réussie. C'est une bonne habitude de cette façon ; , l'utilisateur sait ce qui s'est passé.

3. Nœud de sortie

C'est la méthode de la classe LinkedList. Pour imprimer les données dans tous les nœuds de la liste chaînée, nous devons parcourir un nœud à la fois et imprimer la partie données de chaque nœud.

Code d'implémentation :

class Node:
   def __init__(self,data,nextNode=None):
       self.data = data
       self.nextNode = nextNode
   def getData(self):
       return self.data
   def setData(self,val):
       self.data = val
   def getNextNode(self):
       return self.nextNode
   def setNextNode(self,val):
       self.nextNode = val
class LinkedList:
   def __init__(self,head = None):
       self.head = head
       self.size = 0
   def getSize(self):
       return self.size
   def addNode(self,data):
       newNode = Node(data,self.head)
       self.head = newNode
       self.size+=1
       return True
       
   def printNode(self):
       curr = self.head
       while curr:
           print(curr.data)
           curr = curr.getNextNode()
myList = LinkedList()
print("Inserting")
print(myList.addNode(5))
print(myList.addNode(15))
print(myList.addNode(25))
print("Printing")
myList.printNode()
print("Size")
print(myList.getSize())

Quels sont les avantages et les inconvénients des listes à chaînage unique ?

Avantages :

● C'est une structure de données dynamique dans laquelle l'insertion et la suppression sont simples, car nous n'avons pas besoin pour déplacer l'élément. La simple mise à jour du pointeur suivant fera l'affaire.

●Les structures de données de pile et de file d'attente peuvent être facilement implémentées à l'aide de listes chaînées.

Inconvénients

●Le pointeur suivant occupe de la mémoire supplémentaire.

● Impossible d'accéder de manière aléatoire. La liste chaînée doit être parcourue depuis le début pour atteindre un nœud spécifique.

Ce qui précède représente l’intégralité du contenu de cet article, j’espère qu’il sera utile à l’étude de chacun. Pour un contenu plus passionnant, vous pouvez prêter attention aux colonnes de didacticiels pertinentes du site Web PHP chinois ! ! !

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!