Liste chaînée en Python

  2. HowTo
  3. Mode d'emploi Python
  4. Liste chaînée en Python
Aditya Raj 30 janvier 2023
Python Python Data Structure
  1. Qu’est-ce qu’une liste chaînée en Python
  2. Comment créer une liste chaînée en Python
  3. Imprimer tous les éléments d’une liste chaînée en Python
  4. Insérer un élément dans une liste liée en Python
  5. Supprimer un élément de la liste liée en Python
  6. Compter le nombre d’éléments dans une liste chaînée en Python
  7. Mettre à jour un nœud dans la liste liée en Python
  8. Pourquoi utiliser une liste chaînée en Python
  9. Liste liée d’implémentation complète en Python
  10. Conclusion
Liste chaînée en Python

Python nous fournit diverses structures de données intégrées.

Cependant, chaque structure de données a ses restrictions. Pour cette raison, nous avons besoin de structures de données personnalisées.

Cet article traite d’une structure de données personnalisée appelée liste liée. Nous allons également implémenter une liste chaînée en Python et effectuer diverses opérations sur la liste chaînée.

Qu’est-ce qu’une liste chaînée en Python

Comme son nom l’indique, une liste chaînée est une structure de données qui contient des éléments reliés par un lien.

Une liste chaînée est créée à l’aide d’objets appelés nœuds. Chaque nœud contient deux attributs, l’un pour stocker les données et l’autre pour se connecter au nœud suivant dans la liste chaînée.

Vous pouvez comprendre la structure d’un nœud à l’aide de la figure suivante.

Noeud en Python

Ici,

  • Un Node est un objet qui contient les attributs data et next.
  • L’attribut data stocke les données.
  • L’attribut next fait référence au nœud suivant dans la liste chaînée.

Comme le montre l’image suivante, nous pouvons connecter différents nœuds pour créer une liste chaînée.

Liste chaînée en Python

Ici,

  • Nous avons créé une liste chaînée composée de quatre nœuds.
  • Le premier nœud contient le nombre 10, le deuxième nœud contient 20, le troisième nœud contient 30 et le dernier nœud contient 40.
  • Nous avons également créé une variable Head qui fait référence au premier nœud. Nous ne gardons que la variable Head dans un objet de liste chaînée. Les données de tous les autres nœuds sont obtenues en parcourant la liste chaînée à partir du premier nœud référencé par Head.
  • L’attribut next du dernier nœud fait référence à un objet None. L’attribut next du dernier nœud d’une liste chaînée fera toujours référence à l’objet None.
  • Si une liste chaînée est vide, la variable Head fera référence à l’objet None.

Nous comprenons maintenant la structure de base d’une liste chaînée. Implémentons une liste chaînée en Python.

Comment créer une liste chaînée en Python

Comme les nœuds sont les blocs de construction d’une liste chaînée, nous allons d’abord créer un nœud. Pour cela, nous allons définir une classe Node avec les attributs data et next comme indiqué ci-dessous.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


myNode = Node(10)
print("The data in the node is:", myNode.data)
print("The next attribute in the node is:", myNode.next)

Production :

The data in the node is: 10
The next attribute in the node is: None

Dans l’exemple ci-dessus, vous pouvez observer que l’attribut next du Node fait référence à None par défaut. Lorsque nous l’insérons dans une liste chaînée, nous attribuons l’attribut next aux nœuds de la liste chaînée, comme nous le verrons plus loin.

Il faut créer un objet avec l’attribut Head pour créer une liste chaînée. Nous pouvons définir la classe LinkedList comme indiqué ci-dessous.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None


myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4

print("The elements in the linked list are:")
print(myLinkedList.Head.data, end=" ")
print(myLinkedList.Head.next.data, end=" ")
print(myLinkedList.Head.next.next.data, end=" ")
print(myLinkedList.Head.next.next.next.data)

Production :

The linked list is:
10 20 30 40

Dans l’exemple ci-dessus, nous avons créé une liste chaînée.

Après cela, nous avons créé manuellement les nœuds à l’aide des données fournies, les avons ajoutés un par un à la liste liée et les avons imprimés. Plus tard, nous apprendrons à insérer des éléments dans une liste chaînée en utilisant la boucle while de Python.

Voyons maintenant comment nous pouvons imprimer tous les éléments d’une liste chaînée sans accéder manuellement à tous les nœuds.

Imprimer tous les éléments d’une liste chaînée en Python

Nous allons utiliser une boucle while pour imprimer tous les éléments de la liste chaînée.

En partant du pointeur Head, nous allons d’abord imprimer les données du nœud courant en utilisant l’attribut data du nœud. Après cela, nous passerons au nœud suivant en utilisant le pointeur next.

Nous suivrons ce processus jusqu’à ce que nous atteignions la fin de la liste chaînée (c’est-à-dire que l’attribut next d’un nœud se trouve être None). Comme indiqué ci-dessous, vous pouvez implémenter toute la logique dans la méthode printList().

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next


myLinkedList = LinkedList()
myNode1 = Node(10)
myNode2 = Node(20)
myNode3 = Node(30)
myNode4 = Node(40)
myLinkedList.Head = myNode1
myNode1.next = myNode2
myNode2.next = myNode3
myNode3.next = myNode4

print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
10 20 30 40

Insérer un élément dans une liste liée en Python

Il existe quatre situations lors de l’insertion d’un élément dans une liste chaînée.

  1. La liste chaînée peut être vide avant l’insertion.
  2. Nous devons insérer un élément au début d’une liste chaînée non vide.
  3. Nous devons insérer un élément à la fin d’une liste chaînée.
  4. Nous devons insérer un élément à une position donnée dans la liste chaînée.

Voyons comment insérer un élément dans la liste chaînée dans toutes les situations.

Insérer un élément dans une liste chaînée vide

Pour insérer un élément dans une liste chaînée vide, nous allons définir une méthode insertIntoEmptyList() qui accepte l’élément comme argument d’entrée et ajoute un nœud contenant l’élément d’entrée dans la liste chaînée.

Pour cela, nous allons créer un nœud dans la insertIntoEmptyList() avec l’élément d’entrée comme data. Après avoir créé le nœud, nous assignerons le nœud à l’attribut Head.

De cette manière, le nouveau nœud deviendra le premier nœud de la liste chaînée. Le procédé peut être mis en œuvre comme suit.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertIntoEmptyList(self, element):
        newNode = Node(element)
        self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
10

Insérer un élément au début d’une liste chaînée

Pour insérer un élément au début d’une liste non vide, nous allons définir une méthode insertAtBeginning() qui prend un élément en entrée et l’ajoute au début de la liste chaînée. Dans la méthode insertAtBeginning(), nous allons d’abord créer un nœud avec l’élément d’entrée comme donnée.

Après cela, nous pointerons l’attribut next du nœud nouvellement créé vers le nœud où pointe l’attribut Head de la liste chaînée. Ensuite, nous allons attribuer le nœud nouvellement créé à l’attribut Head.

De cette manière, le nouveau nœud sera inséré au début de la liste chaînée.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertIntoEmptyList(self, element):
        newNode = Node(element)
        self.Head = newNode

    def insertAtBeginning(self, element):
        newNode = Node(element)
        newNode.next = self.Head
        self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertIntoEmptyList(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
30 20 10

Comme indiqué ci-dessous, nous pouvons combiner les méthodes ci-dessus pour créer une seule méthode pour insérer un élément au début d’une liste chaînée.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertAtBeginning(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = self.Head
            self.Head = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtBeginning(10)
myLinkedList.insertAtBeginning(20)
myLinkedList.insertAtBeginning(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
30 20 10

Nous avons fusionné la méthode insertIntoEmptyList() dans la méthode insertAtBeginning() car l’insertion dans une liste chaînée vide signifie essentiellement que nous insérons un élément au début de la liste chaînée.

Insérer un élément à la fin d’une liste chaînée

L’insertion d’un élément à la fin d’une liste vide est similaire à l’insertion de l’élément au début de la liste chaînée.

Pour insérer un élément à la fin d’une liste chaînée, nous allons d’abord vérifier si la liste chaînée est vide. Si la liste chaînée s’avère vide, nous pouvons simplement affecter un nœud contenant le nouvel élément à l’attribut Head comme nous l’avons fait dans la méthode insertAtBeginning().

Sinon, nous parcourrons la liste chaînée jusqu’à la fin en utilisant une boucle while. Nous allons commencer par le Head et continuer à passer au nœud suivant en utilisant l’attribut next des nœuds jusqu’à ce que nous trouvions que l’attribut next du nœud pointe vers None.

Une fois que nous atteignons un nœud dont l’attribut next pointe vers None, nous sommes au dernier nœud. Maintenant, nous allons créer un nouveau nœud en utilisant les données d’entrée et affecter ce nœud à l’attribut suivant du dernier nœud de la liste chaînée.

De cette façon, le nouvel élément sera inséré à la fin de la liste chaînée. Vous pouvez implémenter toute cette logique dans la méthode insertAtEnd() comme suit.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next

    def insertAtEnd(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            current = self.Head
            while current.next is not None:
                current = current.next
            newNode = Node(element)
            current.next = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtEnd(10)
myLinkedList.insertAtEnd(20)
myLinkedList.insertAtEnd(30)
print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
10 20 30

Insérer un élément à une position donnée dans la liste chaînée

Nous allons utiliser une variable compteur et une boucle while pour insérer un élément à une position donnée dans la liste chaînée.

Nous allons commencer par le pointeur Head et continuer à passer au nœud suivant en utilisant la boucle while. A chaque itération, nous allons également incrémenter la variable compteur.

Une fois que nous atteignons le nœud avant la position donnée, nous quittons la boucle while. De plus, nous quitterons la boucle si nous atteignons la fin de la liste chaînée. Sinon, le programme rencontrera une erreur.

Après cela, si nous sommes toujours à la Head, nous devons ajouter l’élément à la première position de la liste chaînée ; nous assignerons le nœud à la position donnée au pointeur next contenant le nouvel élément nœud. Ensuite, nous assignerons le nœud du nouvel élément au Head de la liste chaînée.

Si nous n’avons pas à insérer l’élément en 1ère position, nous assignerons le nœud à la position donnée au pointeur next du nœud contenant le nouvel élément. Ensuite, nous assignerons le nouveau nœud à l’attribut next du nœud à position-1.

De cette façon, le nouvel élément sera inséré à la position donnée. Comme indiqué ci-dessous, vous pouvez implémenter toute la logique dans la méthode insertAtPosition().

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(20, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(30, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
10 
The elements in the linked list are:
10 20 
The elements in the linked list are:
10 20 30 
The elements in the linked list are:
10 40 20 30

Supprimer un élément de la liste liée en Python

Il peut y avoir trois situations lorsque nous essayons de supprimer un élément d’une liste chaînée.

  1. Nous devons supprimer le premier élément de la liste chaînée.
  2. Nous devons supprimer le dernier élément de la liste liée.
  3. Nous devons supprimer l’élément à n’importe quelle position dans la liste liée.

Examinons tous ces cas un par un.

Supprimer le premier élément d’une liste chaînée

Pour supprimer le premier élément d’une liste chaînée, nous allons d’abord vérifier si la liste chaînée est vide ou non.

Pour cela, nous allons vérifier si le Head de la liste chaînée pointe vers None. Si oui, nous informerons l’utilisateur que la liste chaînée est vide et que nous n’avons aucun élément à supprimer.

Sinon, nous affecterons le premier nœud à une variable temporaire. Après cela, nous attribuerons le deuxième nœud de la liste chaînée à l’attribut Head.

Ensuite, nous supprimerons le premier nœud stocké dans la variable temporaire à l’aide de l’instruction del. Comme indiqué ci-dessous, vous pouvez implémenter toute la logique dans la méthode deleteFromBeginning().

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromBeginning(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            node = self.Head
            self.Head = self.Head.next
            del node


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromBeginning()
print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
40 20 30 
The elements in the linked list are:
20 30

Supprimer le dernier élément d’une liste chaînée

Pour supprimer le dernier élément d’une liste chaînée, nous allons d’abord vérifier si la liste chaînée est vide ou non.

Pour cela, nous allons vérifier si le Head de la liste chaînée pointe vers None. Si oui, nous informerons l’utilisateur que la liste chaînée est vide et que nous n’avons aucun élément à supprimer.

S’il y a des éléments présents dans la liste, nous suivrons le processus suivant.

  1. Affectez le premier nœud à une variable current.
  2. Initialiser une variable previous à None.
  3. Parcourez la liste chaînée à l’aide d’une boucle while, affectez le nœud de la variable current à la variable previous, et avancez la variable current au nœud suivant jusqu’à ce que la variable current atteigne le dernier nœud . Dans ce cas, l’attribut next du nœud affecté à current devient None.
  4. Une fois que la variable courante atteint le dernier nœud, nous assignerons None à l’attribut next de la variable précédent et supprimerons le nœud attribué à la variable current.

Nous pouvons supprimer le dernier élément d’une liste chaînée en exécutant les étapes ci-dessus. Comme indiqué ci-dessous, vous pouvez implémenter toute la logique dans la méthode deleteFromLast().

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromLast(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            while current.next is not None:
                previous = current
                current = current.next
            previous.next = None
            del current


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteFromLast()
print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 20 
The elements in the linked list are:
10 40

Supprimer l’élément à n’importe quelle position dans la liste liée

Pour supprimer un élément à une position donnée dans la liste chaînée, nous allons d’abord vérifier si la liste chaînée est vide ou non.

Pour cela, nous allons vérifier si le Head de la liste chaînée pointe vers None. Si oui, nous informerons l’utilisateur que la liste chaînée est vide et que nous n’avons aucun élément à supprimer.

S’il y a des éléments présents dans la liste liée et que nous devons supprimer un élément à une autre position, nous suivrons les étapes suivantes.

  1. Affectez le premier nœud à une variable current.
  2. Initialiser une variable previous à None.
  3. Initialiser une variable count à 1.
  4. Parcourez la liste liée à l’aide d’une boucle while, incrémentez count à chaque itération, affectez le nœud de la variable current à previous, et avancez la variable current au nœud suivant jusqu’à ce que le count variable a la position de l’élément à supprimer ou on arrive à la fin de la liste chaînée. À ce stade, la variable courant fera référence au nœud qui doit être supprimé.
  5. Une fois que le nombre devient égal à la position de l’élément à supprimer, il peut y avoir deux situations.
  6. Si nous sommes toujours à la Head, à la 1ère position, nous affecterons le nœud référencé par l’attribut next de la variable courante à l’attribut Head. Après cela, nous supprimerons la variable current.
  7. Si nous ne sommes pas à la 1ère position, nous affecterons le nœud suivant de la variable courante à l’attribut suivant du nœud affecté à la variable previous. Nous allons supprimer le nœud affecté à la variable current. De cette façon, l’élément à la position donnée sera supprimé.

Nous pouvons implémenter la logique ci-dessus dans la méthode deleteAtPosition() décrite ci-dessous.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteAtPosition(self, position):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            count = 1
            while current.next is not None and count < position:
                previous = current
                current = current.next
                count += 1
            if current == self.Head:
                self.Head = current.next
                del current
            else:
                previous.next = current.next
                del current


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(1)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.deleteAtPosition(2)
print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
40 20 30 
The elements in the linked list are:
40 30

Compter le nombre d’éléments dans une liste chaînée en Python

Pour compter le nombre d’éléments dans une liste chaînée, on va simplement initialiser une variable count à 0.

Après cela, nous partirons de Head et passerons au nœud suivant en utilisant une boucle while jusqu’à ce que nous atteignions la fin de la liste chaînée. A chaque itération de la boucle while, on incrémentera le count de 1.

Après avoir exécuté la boucle while, nous aurons le nombre d’éléments de la liste chaînée dans la variable count. Vous pouvez implémenter cette logique comme indiqué dans la méthode countElements() ci-dessous.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def countElements(self):
        count = 0
        current = self.Head
        while current is not None:
            count += 1
            current = current.next
        print("Number of elements in the linked list are:", count)


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.countElements()

Production :

The elements in the linked list are:
10 40 20 30 
Number of elements in the linked list are: 4

Mettre à jour un nœud dans la liste liée en Python

Il peut y avoir deux situations pour mettre à jour la valeur dans un nœud de la liste chaînée.

  1. Nous devons remplacer une valeur.
  2. Nous devons attribuer une nouvelle valeur à l’élément à n’importe quelle position donnée dans la liste chaînée.

Remplacer une valeur dans la liste liée

Pour remplacer une valeur dans la liste chaînée, nous allons commencer par le premier nœud et parcourir la liste chaînée à l’aide d’une boucle while.

On va vérifier si le nœud current contient la valeur à remplacer à chaque nœud. Si oui, nous remplacerons la valeur du nœud actuel par la nouvelle valeur.

De cette façon, nous pouvons mettre à jour la première occurrence de n’importe quel élément dans la liste liée comme indiqué dans la méthode replaceElement().

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def replaceElement(self, old_element, new_element):
        current = self.Head
        while current is not None:
            if current.data == old_element:
                current.data = new_element
                break
            current = current.next


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(30, 100)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.replaceElement(20, 150)
print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 20 100 
The elements in the linked list are:
10 40 150 100

Mettre à jour l’élément à une position donnée dans la liste chaînée

Pour mettre à jour l’élément à une position donnée dans la liste chaînée, nous allons d’abord vérifier si la liste chaînée est vide. Si oui, il peut y avoir deux situations.

Si la liste chaînée est vide et que nous devons mettre à jour un élément autre que la première position, nous informerons l’utilisateur que cela ne peut pas être fait.

Si la liste chaînée est vide et que nous devons mettre à jour l’élément à la première position, nous allons créer un nouveau nœud avec l’élément donné et attribuer le nœud au Head de la liste chaînée. Sinon, on initialisera une variable counter à 1.

Après cela, nous allons parcourir la liste chaînée en utilisant une boucle while. A chaque itération de la boucle while, nous allons passer au nœud suivant dans la liste chaînée, incrémenter la variable counter de 1, et vérifier si nous avons atteint la position de l’élément qui doit être mis à jour.

Si nous atteignons la position qui doit être mise à jour, nous mettrons à jour la valeur dans le nœud actuel de la liste liée et en informerons l’utilisateur.

Si nous ne pouvons pas atteindre la position qui doit être mise à jour et que la boucle while se termine, nous informerons l’utilisateur qu’il n’y a pas assez d’éléments et nous ne pouvons pas mettre à jour la valeur. Cette logique peut être implémentée comme indiqué ci-dessous dans la méthode updateAtPosition().

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def updateAtPosition(self, new_element, position):
        if self.Head is None and position != 1:
            print("No element to update in the linked list.")
            return
        elif self.Head is None and position == 1:
            newNode = Node(new_element)
            self.Head = newNode
            return
        count = 1
        current = self.Head
        while current.next is not None and count < position:
            count += 1
            current = current.next
        if count == position:
            current.data = new_element
        elif current.next is None:
            print("Not enough elements in the linked list.")


myLinkedList = LinkedList()
myLinkedList.insertAtPosition(10, 1)
myLinkedList.insertAtPosition(20, 2)
myLinkedList.insertAtPosition(30, 3)
myLinkedList.insertAtPosition(40, 2)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(100, 3)
print("The elements in the linked list are:")
myLinkedList.printList()
myLinkedList.updateAtPosition(150, 12)
print("The elements in the linked list are:")
myLinkedList.printList()

Production :

The elements in the linked list are:
10 40 20 30 
The elements in the linked list are:
10 40 100 30 
Not enough elements in the linked list.
The elements in the linked list are:
10 40 100 30

Pourquoi utiliser une liste chaînée en Python

  • Si vous n’avez pas besoin d’un accès aléatoire aux éléments, les listes chaînées peuvent être une meilleure alternative. Vous devez utiliser des listes liées au lieu de listes normales en Python lorsque nous avons des millions d’éléments à stocker et que nous n’avons pas besoin d’un accès aléatoire.
  • La taille réelle des listes est très grande par rapport au nombre d’éléments qu’elles contiennent. La taille réelle d’une liste est d’environ 1,5 fois le nombre d’éléments qu’elle contient. Cela garantit que nous avons suffisamment de mémoire pour insérer des éléments dans la liste. Cependant, une liste chaînée ne nécessite pas d’espaces supplémentaires.
  • Lorsque nous insérons un élément dans la liste chaînée, seul le stockage est nécessaire. Les listes nécessitent également un emplacement mémoire contigu. Au contraire, les nœuds d’une liste chaînée peuvent être présents à n’importe quel endroit de la mémoire physique. Ils sont reliés par des références.
  • Vous pouvez implémenter efficacement les structures de données de pile et de file d’attente à l’aide de listes chaînées. D’autre part, la mise en place d’une file d’attente à l’aide d’une liste est coûteuse en complexité temporelle.

Liste liée d’implémentation complète en Python

Voici le code d’exécution complet pour implémenter une liste chaînée en Python avec toutes les méthodes décrites dans cet article.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class LinkedList:
    def __init__(self):
        self.Head = None

    def printList(self):
        current = self.Head
        while current is not None:
            print(current.data, end=" ")
            current = current.next
        print("")

    def insertAtBeginning(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = self.Head
            self.Head = newNode

    def insertAtEnd(self, element):
        if self.Head is None:
            newNode = Node(element)
            self.Head = newNode
        else:
            current = self.Head
            while current.next is not None:
                current = current.next
            newNode = Node(element)
            current.next = newNode

    def insertAtPosition(self, element, position):
        counter = 1
        current = self.Head
        while counter < position - 1 and current is not None:
            counter += 1
            current = current.next
        if position == 1:
            newNode = Node(element)
            newNode.next = current
            self.Head = newNode
        else:
            newNode = Node(element)
            newNode.next = current.next
            current.next = newNode

    def deleteFromBeginning(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            node = self.Head
            self.Head = self.Head.next
            del node

    def deleteFromLast(self):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            while current.next is not None:
                previous = current
                current = current.next
            previous.next = None
            del current

    def deleteAtPosition(self, position):
        if self.Head is None:
            print("The linked list empty. Cannot delete an element.")
            return
        else:
            current = self.Head
            previous = None
            count = 1
            while current.next is not None and count < position:
                previous = current
                current = current.next
                count += 1
            if current == self.Head:
                self.Head = current.next
                del current
            else:
                previous.next = current.next
                del current

    def countElements(self):
        count = 0
        current = self.Head
        while current is not None:
            count += 1
            current = current.next
        print("Number of elements in the linked list are:", count)

    def replaceElement(self, old_element, new_element):
        current = self.Head
        while current is not None:
            if current.data == old_element:
                current.data = new_element
                break
            current = current.next

    def updateAtPosition(self, new_element, position):
        if self.Head is None and position != 1:
            print("No element to update in the linked list.")
            return
        elif self.Head is None and position == 1:
            newNode = Node(new_element)
            self.Head = newNode
            return
        count = 1
        current = self.Head
        while current.next is not None and count < position:
            count += 1
            current = current.next
        if count == position:
            current.data = new_element
        elif current.next is None:
            print("Not enough elements in the linked list.")

Conclusion

Dans cet article, nous avons discuté de la structure de données de la liste chaînée et de son implémentation en Python. Nous avons également implémenté les méthodes pour diverses opérations dans une liste chaînée.

Dans cet article, nous avons implémenté toutes les opérations à l’aide de méthodes. Vous pouvez également implémenter chaque opération à l’aide de fonctions qui prennent en entrée le Head de la liste chaînée et renvoient le head après avoir exécuté les opérations requises.

Cependant, cela nécessitera plus de ressources lors de l’exécution. Ainsi, je vous suggère d’utiliser l’approche utilisée dans cet article.

Auteur: Aditya Raj
Aditya Raj avatar Aditya Raj avatar

Aditya Raj is a highly skilled technical professional with a background in IT and business, holding an Integrated B.Tech (IT) and MBA (IT) from the Indian Institute of Information Technology Allahabad. With a solid foundation in data analytics, programming languages (C, Java, Python), and software environments, Aditya has excelled in various roles. He has significant experience as a Technical Content Writer for Python on multiple platforms and has interned in data analytics at Apollo Clinics. His projects demonstrate a keen interest in cutting-edge technology and problem-solving, showcasing his proficiency in areas like data mining and software development. Aditya's achievements include securing a top position in a project demonstration competition and gaining certifications in Python, SQL, and digital marketing fundamentals.

GitHub

Article connexe - Python Data Structure