Python - Listes liées
Une liste chaînée est une séquence d'éléments de données, qui sont connectés entre eux via des liens. Chaque élément de données contient une connexion à 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 chaînées en utilisant le concept de nœuds comme discuté dans le chapitre précédent. Nous avons déjà vu comment nous créons 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 liées individuellement. 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 chaînée est créée en utilisant la classe de nœuds 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 transmettons les valeurs appropriées à 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 parcourir la liste chaînée.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class SLinkedList:
def __init__(self):
self.headval = None
list1 = SLinkedList()
list1.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3Traverser une liste liée
Les listes chaînées isolées peuvent être parcourues uniquement dans le sens de marche à partir du premier élément de données. Nous imprimons simplement la valeur de l'élément de données suivant en attribuant 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 = None
class SLinkedList:
def __init__(self):
self.headval = None
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
# Link first Node to second node
list.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
list.listprint()Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:
Mon
Tue
WedInsertion dans une liste liée
L'insertion d'un élément dans la liste liée implique la réaffectation des pointeurs des nœuds existants au nœud nouvellement inséré. Selon que le nouvel élément de données est inséré 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 liée
Cela implique de pointer le pointeur suivant du nouveau nœud de données vers l'en-tête actuel de la liste liée. Ainsi, la tête actuelle de la liste liée devient le deuxième élément de données et le nouveau nœud devient la tête de la liste liée.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class 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 = NewNode
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
list.headval.nextval = e2
e2.nextval = e3
list.AtBegining("Sun")
list.listprint()Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:
Sun
Mon
Tue
WedInsertion à la fin de la liste liée
Cela implique de pointer le pointeur suivant du dernier nœud actuel de la liste liée vers le nouveau nœud de données. Ainsi, le dernier nœud actuel de la liste liée devient l'avant-dernier nœud de données et le nouveau nœud devient le dernier nœud de la liste liée.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class 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.nextval
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Wed")
list.headval.nextval = e2
e2.nextval = e3
list.AtEnd("Thu")
list.listprint()Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:
Mon
Tue
Wed
ThuInsertion entre deux nœuds de données
Cela implique de modifier 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 quoi le nouveau nœud sera inséré. Nous définissons donc une classe supplémentaire qui changera le pointeur suivant du nouveau nœud vers le pointeur suivant du nœud central. Attribuez ensuite le nouveau nœud au pointeur suivant du nœud du milieu.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class 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.nextval
list = SLinkedList()
list.headval = Node("Mon")
e2 = Node("Tue")
e3 = Node("Thu")
list.headval.nextval = e2
e2.nextval = e3
list.Inbetween(list.headval.nextval,"Fri")
list.listprint()Lorsque le code ci-dessus est exécuté, il produit le résultat suivant:
Mon
Tue
Fri
ThuSupprimer un élément d'une liste aimé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é. Puis 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 = None
class 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.next
llist = 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:
Thu
Wed
Mon