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.

def search(self, value):
    # Start the search from the head of the linked list
    current = self.head
    # Traverse the linked list
    while current:
        # Check if the value of the current node matches the target value
        if current.data == value:
            # Return the node if found
            return current
        # Move to the next node
        current = current.next
    # Return None if the value is not found in the linked list
    return None

def insert(self, value):
    # Create a new node with the given value
    new_node = ListNode(value)
    # Check if the linked list is empty
    if not self.head:
        # If the linked list is empty, set the new node as the head
        self.head = new_node
    else:
        # If the linked list is not empty, insert the new node at the beginning
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node

def delete(self, value):
    # Start the search from the head of the linked list
    current = self.head
    # Traverse the linked list
    while current:
        # Check if the value of the current node matches the target value
        if current.data == value:
            # Update the pointers of the surrounding nodes to skip the current node
            if current.prev:
                current.prev.next = current.next
            if current.next:
                current.next.prev = current.prev
            # Update the head pointer if the current node is the head
            if current == self.head:
                self.head = current.next
            # Exit the method after deleting the node
            return
        # Move to the next node
        current = current.next

Tout était clair ?

Merci pour vos commentaires !

Section 2. Chapitre 7

Demandez à l'IA

Posez n'importe quelle question ou essayez l'une des questions suggérées pour commencer notre discussion

Contenu du cours

Aperçu des Algorithmes et des Structures de Données

1. Introduction à ADS

2. Liste et Tableau

3. Structures de Données Avancées

Piles Files d'Attente Défi : Utiliser la Pile pour Trouver un Palindrome Table de Hachage Défi : Créer une Table de Hachage avec des Clés de Chaîne

4. Graphes

Qu'est-ce Qu'un Graphe Implémentation de Graphe Défi : Algorithmes de Parcours de Graphe Abr Parcours BST Défi : Arbres Équilibrés

Liste Doublement Chaînée


              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))

def search(self, value):
    # Start the search from the head of the linked list
    current = self.head
    # Traverse the linked list
    while current:
        # Check if the value of the current node matches the target value
        if current.data == value:
            # Return the node if found
            return current
        # Move to the next node
        current = current.next
    # Return None if the value is not found in the linked list
    return None

def insert(self, value):
    # Create a new node with the given value
    new_node = ListNode(value)
    # Check if the linked list is empty
    if not self.head:
        # If the linked list is empty, set the new node as the head
        self.head = new_node
    else:
        # If the linked list is not empty, insert the new node at the beginning
        new_node.next = self.head
        self.head.prev = new_node
        self.head = new_node

def delete(self, value):
    # Start the search from the head of the linked list
    current = self.head
    # Traverse the linked list
    while current:
        # Check if the value of the current node matches the target value
        if current.data == value:
            # Update the pointers of the surrounding nodes to skip the current node
            if current.prev:
                current.prev.next = current.next
            if current.next:
                current.next.prev = current.prev
            # Update the head pointer if the current node is the head
            if current == self.head:
                self.head = current.next
            # Exit the method after deleting the node
            return
        # Move to the next node
        current = current.next

Tout était clair ?

Merci pour vos commentaires !

Section 2. Chapitre 7