Liste Doublement Chaînée

La liste chaînée est une structure de données polyvalente, exempte des "trous" inhérents aux tableaux.
Manipuler le premier élément est efficace, mais pour certains types de données abstraits comme les files d'attente, une manipulation efficace du dernier élément et un parcours bidirectionnel sont nécessaires. Les listes chaînées standard ont du mal à accéder au dernier élément, nécessitant une complexité temporelle de O(N).
Les listes doublement chaînées résolvent cette limitation et offrent des solutions à divers autres défis.


              1234567891011121314151617181920212223
            
from lolviz import *
from IPython.display import display_png

class Node:

  def __init__(self, data):
    self.value = data
    self.next = None
    self.previous = None

# Let's create some nodes
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)

# Then let's couple them into a linked list
node1.next = node2
node2.next = node3
# And don't forget to assign the reference to a previous node
node2.previous = node1
node3.previous = node2

display_png(objviz(node1))

Les nœuds de la liste doublement chaînée contiennent les références vers les éléments suivant et précédent. Par conséquent, nous pouvons accéder au premier et au dernier élément en temps constant O(1). La complexité temporelle de toutes les autres opérations pour la liste doublement chaînée est la même que pour la liste simplement chaînée.

Tout était clair ?

Merci pour vos commentaires !

Section 2. Chapitre 7