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 = e3

Traverser 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
Wed

Insertion 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
Wed

Insertion à 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
Thu

Insertion 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
Thu

Supprimer 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