Python – Listes liées

Une liste liée est une séquence d’éléments de données, qui sont reliés entre eux par des liens. Chaque élément de données contient un lien vers un autre élément de données sous la forme d’un pointeur. Python n’a pas de listes liées dans sa bibliothèque standard. Nous implémentons le concept de listes liées en utilisant le concept de nœuds, comme nous l’avons vu dans le chapitre précédent. Nous avons déjà vu comment créer une classe de nœuds et comment parcourir les éléments d’un nœud. Dans ce chapitre, nous allons étudier les types de listes liées connues sous le nom de listes singulièrement liées. Dans ce type de structure de données, il n’y a qu’un seul lien entre deux éléments de données. Nous créons une telle liste et créons des méthodes supplémentaires pour insérer, mettre à jour et supprimer des éléments de la liste.

Création d’une liste liée

Une liste liée est créée en utilisant la classe Node que nous avons étudiée dans le dernier chapitre. Nous créons un objet Node et créons une autre classe pour utiliser cet objet ode. Nous passons les valeurs appropriées à travers l’objet node pour pointer vers les éléments de données suivants. Le programme ci-dessous crée la liste liée avec trois éléments de données. Dans la section suivante, nous verrons comment traverser la liste liée.

class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = Nonelist1 = SLinkedList()list1.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")# Link first Node to second nodelist1.headval.nextval = e2# Link second Node to third nodee2.nextval = e3

Traverser une liste liée

Les listes liées peuvent être traversées dans la direction forwrad en commençant par le premier élément de données. Nous imprimons simplement la valeur de l’élément de données suivant en associant le pointeur du nœud suivant à l’élément de données actuel.

class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = None def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")# Link first Node to second nodelist.headval.nextval = e2# Link second Node to third nodee2.nextval = e3list.listprint()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant :

MonTueWed

Insertion dans une liste chaînée

L’insertion d’un élément dans la liste chaînée implique la réaffectation des pointeurs des nœuds existants vers le nœud nouvellement inséré. Selon que le nouvel élément de données s’insère au début, au milieu ou à la fin de la liste chaînée, nous avons les scénarios ci-dessous.

Insertion au début de la liste chaînée

Cela implique de pointer le pointeur suivant du nouveau nœud de données vers la tête actuelle de la liste chaînée. Ainsi, la tête actuelle de la liste chaînée devient le deuxième élément de données et le nouveau nœud devient la tête de la liste chaînée.

class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = None# Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextval def AtBegining(self,newdata): NewNode = Node(newdata)# Update the new nodes next val to existing node NewNode.nextval = self.headval self.headval = NewNodelist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")list.headval.nextval = e2e2.nextval = e3list.AtBegining("Sun")list.listprint()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant :

SunMonTueWed

Insertion à la fin de la liste chaînée

Il s’agit de pointer le pointeur suivant du dernier nœud actuel de la liste chaînée vers le nouveau nœud de données. Ainsi, le dernier nœud actuel de la liste chaînée devient l’avant-dernier nœud de données et le nouveau nœud devient le dernier nœud de la liste chaînée.

class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = None# Function to add newnode def AtEnd(self, newdata): NewNode = Node(newdata) if self.headval is None: self.headval = NewNode return laste = self.headval while(laste.nextval): laste = laste.nextval laste.nextval=NewNode# Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Wed")list.headval.nextval = e2e2.nextval = e3list.AtEnd("Thu")list.listprint()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant :

MonTueWedThu

Insertion entre deux nœuds de données

Il s’agit de changer le pointeur d’un nœud spécifique pour qu’il pointe vers le nouveau nœud. Cela est possible en passant à la fois le nouveau nœud et le nœud existant après lequel le nouveau nœud sera inséré.Donc, nous définissons une classe supplémentaire qui va changer le prochain pointeur du nouveau nœud au prochain pointeur du nœud intermédiaire. Puis assigner le nouveau nœud au pointeur suivant du nœud du milieu.

class Node: def __init__(self, dataval=None): self.dataval = dataval self.nextval = Noneclass SLinkedList: def __init__(self): self.headval = None# Function to add node def Inbetween(self,middle_node,newdata): if middle_node is None: print("The mentioned node is absent") return NewNode = Node(newdata) NewNode.nextval = middle_node.nextval middle_node.nextval = NewNode# Print the linked list def listprint(self): printval = self.headval while printval is not None: print (printval.dataval) printval = printval.nextvallist = SLinkedList()list.headval = Node("Mon")e2 = Node("Tue")e3 = Node("Thu")list.headval.nextval = e2e2.nextval = e3list.Inbetween(list.headval.nextval,"Fri")list.listprint()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant :

MonTueFriThu

Suppression d’un élément d’une liste likée

Nous pouvons supprimer un nœud existant en utilisant la clé de ce nœud. Dans le programme ci-dessous, nous localisons le nœud précédent du nœud qui doit être supprimé.Ensuite, pointez le pointeur suivant de ce nœud vers le nœud suivant du nœud à supprimer.

class Node: def __init__(self, data=None): self.data = data self.next = Noneclass SLinkedList: def __init__(self): self.head = None def Atbegining(self, data_in): NewNode = Node(data_in) NewNode.next = self.head self.head = NewNode# Function to remove node def RemoveNode(self, Removekey): HeadVal = self.head if (HeadVal is not None): if (HeadVal.data == Removekey): self.head = HeadVal.next HeadVal = None return while (HeadVal is not None): if HeadVal.data == Removekey: break prev = HeadVal HeadVal = HeadVal.next if (HeadVal == None): return prev.next = HeadVal.next HeadVal = None def LListprint(self): printval = self.head while (printval): print(printval.data), printval = printval.nextllist = SLinkedList()llist.Atbegining("Mon")llist.Atbegining("Tue")llist.Atbegining("Wed")llist.Atbegining("Thu")llist.RemoveNode("Tue")llist.LListprint()

Lorsque le code ci-dessus est exécuté, il produit le résultat suivant :

ThuWedMon

.