Listes liées avancées

Nous avons déjà vu la liste liée dans le chapitre précédent dans laquelle il est possible de voyager uniquement vers l'avant. Dans ce chapitre, nous verrons un autre type de liste liée dans laquelle il est possible de voyager à la fois vers l'avant et vers l'arrière. Une telle liste est appelée liste doublement liée. Voici les caractéristiques de la liste doublement liée.

• Une liste à double lien contient un élément de lien appelé first et last.
• Chaque lien porte un ou plusieurs champs de données et deux champs de lien appelés next et prev.
• Chaque lien est lié à son lien suivant par son lien suivant.
• Chaque lien est lié à son lien précédent à l'aide de son lien précédent.
• Le dernier lien porte un lien comme null pour marquer la fin de la liste.

Création d'une liste doublement liée

Nous créons une liste doublement liée en utilisant la classe Node. Nous utilisons maintenant la même approche que celle utilisée dans la liste à liaison simple, mais les pointeurs head et next seront utilisés pour une affectation correcte afin de créer deux liens dans chacun des nœuds en plus des données présentes dans le nœud.

Exemple

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

class doubly_linked_list:
    def __init__(self):
        self.head = None

    # Adding data elements      
    def push(self, NewVal):
        NewNode = Node(NewVal)
        NewNode.next = self.head
        if self.head is not None:
            self.head.prev = NewNode
        self.head = NewNode

    # Print the Doubly Linked list      
    def listprint(self, node):
        while (node is not None):
            print(node.data),
            last = node
            node = node.next

dllist = doubly_linked_list()
dllist.push(12)
dllist.push(8)
dllist.push(62)
dllist.listprint(dllist.head)

Réponse