Linked lists

En bref

Résumé de l’article

Le but principal d’une structure de données est de stocker des valeurs et de maintenir une certaine organisation entre elles. Parmi les différentes stratégies pour cela, la liste chaînée est une solution assez générique.

La plupart des langages de haut niveau (comme Python ou Java) fournissent au moins une implémentation (optimisée) de ce type de structure de données. Ainsi, en général, il ne faut jamais réinventer la roue et utiliser les implémentations existantes. Cependant, à des fins pédagogiques, il est intéressant d’implémenter une structure de données à partir de zéro, comme nous le ferons dans cet article.

Dans ce cours, nous nous concentrerons sur les listes doublement chaînées. Deux points d’entrée pour accéder aux valeurs stockées sont maintenus, un vers la dernière valeur ajoutée et un vers la première valeur ajoutée. De plus, il est possible de se déplacer d’un élément de la liste vers ses éléments précédents et suivants.

Pour illustrer l’utilité d’une telle structure de données, considérez que vous souhaitez stocker une collection d’images dans votre programme pour construire un navigateur d’images. Les listes doublement chaînées sont particulièrement pertinentes dans ce cas, offrant la possibilité de commencer la navigation à partir de la première ou de la dernière image, et aussi de naviguer en avant et en arrière.

Points clés

• Les listes doublement chaînées sont des structures de données offrant un accès aux premiers et derniers éléments ajoutés.

• Depuis chaque élément de la liste, on peut accéder à ses éléments précédents et suivants.

Contenu de l’article

1 — Qu’est-ce qu’une liste doublement chaînée ?

Une liste doublement chaînée est une structure de données où les valeurs stockées sont enchaînées. Chaque valeur stockée est liée à ses valeurs précédentes et suivantes. Comme illustré dans la figure suivante, deux points d’entrée sont fournis : un vers la tête de la liste et un vers sa queue.

2 — Primitives

Les opérations pour manipuler les données stockées dans une liste doublement chaînée sont les suivantes :

• initialize – Initialise une liste vide.
• insert_at_beginning – Ajoute un élément au début de la liste.
• insert_at_end – Ajoute un élément à la fin de la liste.
• pop_from_beginning – Renvoie et supprime l’élément en tête de la liste.
• pop_from_tail – Renvoie et supprime l’élément en queue de la liste.
• is_empty – Renvoie true si la liste ne contient aucune donnée.

Une implémentation possible de ces primitives pour gérer une liste doublement chaînée est proposée ci-dessous. La liste et ses éléments (valeurs + liens vers les éléments précédents et suivants) sont matérialisés au moyen de dictionnaires (voir cette courte introduction aux dictionnaires).

2.1 — Initialisation de la liste doublement chaînée et d’un élément de la liste

Dans l’implémentation proposée, l’initialisation d’une liste doublement chaînée consiste à définir un dictionnaire ayant deux clés nommées head et tail. Une telle liste contient des “éléments”, qui sont des dictionnaires contenant trois clés : data, prev et next.

Définissons quelques fonctions :

"""
    This module provides functions to manipulate a doubly-linked list.
    The list is represented as a dictionary with 'head' and 'tail' keys pointing to the first and last elements, respectively.
    Each element is also represented as a dictionary with 'data', 'prev', and 'next' keys.
"""

# Needed imports
from typing import Any, Dict, Optional

# Create your own custom type
Element = Dict[str, Any]



def create_element (data: Any) -> Element:

    """
        Creates a new element with the given data.
        In:
            * data: The data to store in the element.
        Out:
            * A dictionary representing the new element.
    """

    # Return the new element
    return {'data': data, 'prev': None, 'next': None}



def initialize () -> Dict[str, Optional[Element]]:

    """
        Initializes an empty doubly-linked list.
        In:
            * None.
        Out:
            * A dictionary representing the doubly-linked list, with 'head' and 'tail' keys.
    """

    # Initialize the default pointers
    return {'head': None, 'tail': None}



def is_empty (dll: Dict[str, Optional[Element]]) -> bool:

    """
        Checks if the doubly-linked list is empty.
        In:
            * dll: The doubly-linked list.
        Out:
            * True if the list is empty, False otherwise.
    """

    # Check if the head pointer is uninitialized
    return dll['head'] is None

/**
 * This class provides methods to manipulate a doubly-linked list.
 * The list is represented with a head and tail pointing to the first and last nodes, respectively.
 * Each node is represented with data, prev, and next fields.
 */

 import java.util.Optional;

 class DoublyLinkedList {
     // Define the Node structure
     static class Node {
         int data;
         Node prev;
         Node next;
 
         Node(int data) {
             this.data = data;
             this.prev = null;
             this.next = null;
         }
     }
 
     private Node head;
     private Node tail;
 
     // Initialise the list
     public DoublyLinkedList() {
         this.head = null;
         this.tail = null;
     }

    /**
     * Check if the list is empty.
     *
     * @return true if the list is empty, false otherwise.
     */
    public boolean isEmpty() {
        return head == null;
    }
     //Continuation here
     //...
 }

Déterminer si une liste est vide revient simplement à vérifier que la tête n’est pas liée à un élément.

2.2 — Ajout de données dans la liste

Lorsqu’il s’agit d’insérer un nouvel élément dans une liste, plusieurs stratégies peuvent être envisagées. Il est d’abord considéré ici qu’un nouvel élément peut être ajouté en tête ou en queue de la liste.

Le point crucial ici est de maintenir les liens entre les éléments ainsi que les références à la tête et à la queue de la liste.

Complétons le code ci-dessus avec les deux options :

def insert_at_beginning (dll: Dict[str, Optional[Element]], data: Any) -> None:
    
    """
        Insert a new element with the given data at the beginning of the list.
        In:
            * dll:  The doubly-linked list.
            * data: The data to store in the new element.
        Out:
            * None.
    """

    # Create the element to store
    new_element = create_element(data)

    # Adapt the pointers
    if dll['head'] is None:
        dll['head'] = new_element
        dll['tail'] = new_element
    else:
        new_element['next'] = dll['head']
        dll['head']['prev'] = new_element
        dll['head'] = new_element



def insert_at_end (dll: Dict[str, Optional[Element]], data: Any) -> None:
    
    """
        Insert a new element with the given data at the end of the list.
        In:
            * dll:  The doubly-linked list.
            * data: The data to store in the new element.
        Out:
            * None.
    """

    # Create the element to store
    new_element = create_element(data)

    # Adapt the pointers
    if dll['tail'] is None:
        dll['head'] = new_element
        dll['tail'] = new_element
    else:
        new_element['prev'] = dll['tail']
        dll['tail']['next'] = new_element
        dll['tail'] = new_element

    /**
      * Insert a new node with the given data at the beginning of the list.
      *
      * @param data The data to store in the new node.
      */
     public void insertAtBeginning(int data) {
         Node newNode = new Node(data);
         if (head == null) {
             head = tail = newNode;
         } else {
             newNode.next = head;
             head.prev = newNode;
             head = newNode;
         }
     }
 
     /**
      * Insert a new node with the given data at the end of the list.
      *
      * @param data The data to store in the new node.
      */
     public void insertAtEnd(int data) {
         Node newNode = new Node(data);
         if (tail == null) {
             head = tail = newNode;
         } else {
             newNode.prev = tail;
             tail.next = newNode;
             tail = newNode;
         }
     }

2.3 — Suppression de données dans la liste

Comme pour l’insertion de nouveaux éléments, retirer l’élément en tête ou en queue nécessite de faire attention à maintenir un accès au contenu restant de la liste. En pratique, l’élément à retirer de la liste est toujours stocké en mémoire, seules les références des éléments adjacents sont mises à jour.

Ajoutons les fonctions de suppression dans notre code :

def pop_from_beginning (dll: Dict[str, Optional[Element]]) -> Any:
    
    """
        Removes and returns the data of the element at the beginning of the list.
        In:
            * dll: The doubly-linked list.
        Out:
            * The data of the element removed from the beginning of the list.
    """

    # Verify it is not empty
    if is_empty(dll):
        return None
    
    # Extract the data
    data = dll['head']['data']

    # Adapt the pointers
    if dll['head'] == dll['tail']:
        dll['head'] = None
        dll['tail'] = None
    else:
        dll['head'] = dll['head']['next']
        dll['head']['prev'] = None
    
    # Return the data
    return data



def pop_from_end (dll: Dict[str, Optional[Element]]) -> Any:

    """
        Removes and returns the data of the element at the end of the list.
        In:
            * dll: The doubly-linked list.
        Out:
            * The data of the element removed from the end of the list.
    """

    # Verify it is not empty
    if is_empty(dll):
        return None

    # Extract the data
    data = dll['tail']['data']

    # Adapt the pointers
    if dll['head'] == dll['tail']:
        dll['head'] = None
        dll['tail'] = None
    else:
        dll['tail'] = dll['tail']['prev']
        dll['tail']['next'] = None

    # Return the data
    return data

  /**
     * Remove and return the data from the node at the head of the list.
     *
     * @return The data from the node at the head of the list, or -1 if the list is empty.
     */
    public int popFromHead() {
        if (head == null) {
            throw new RuntimeException("Empty list");//notion of Exception seen in prog session 
        }
        int data = head.data;
        head = head.next;
        if (head != null) {
            head.prev = null;
        } else {
            tail = null;
        }
        return data;
    }

    /**
     * Remove and return the data from the node at the tail of the list.
     *
     * @return The data from the node at the tail of the list, or -1 if the list is empty.
     */
    public int popFromTail() {
        if (tail == null) {
            throw new RuntimeException("Empty list");
        }
        int data = tail.data;
        tail = tail.prev;
        if (tail != null) {
            tail.next = null;
        } else {
            head = null;
        }
        return data;
    }

Pour aller plus loin

3 — Pointeurs

Les structures de données dynamiques, telles que les listes, piles, files, arbres, etc., reposent sur des liens entre leurs éléments. Ces liens sont appelés “références” et correspondent concrètement à des adresses mémoire indiquant où les données (c’est-à-dire les éléments) sont stockées en mémoire principale.

Une référence est une valeur spécifique qui peut être assignée à une variable et qui correspond à une adresse en mémoire principale. Les langages comme C ou C++ impliquent explicitement ce type de données, alors que c’est transparent en Python et Java. Ce type de données est appelé un “pointeur”.

Pour aller plus loin

• Pointer (computer programming).

  La page Wikipédia sur les pointeurs en programmation informatique.

• Linked lists.

  Un tutoriel sur les listes chaînées en C.