Question 160

Comment réaliser et utiliser une liste liée (ou liste chaînée) ?

Les listes liées (aussi appelées listes chaînées) sont une alternative aux vecteurs. Leur avantage est de permettre de manière rapide et flexible l'insertion et la suppression d'éléments. L'accès à un élément de position donnée de la liste est au contraire plus lent. Il arrive souvent que l'accès aux éléments soient réalisés à l'aide de clés constituées de chaînes de caractères, auquel cas une table de hachage permet un accès suffisamment rapide.

Structure d'une liste liée

Dans une liste liée, un élément possède un référent vers l'élément suivant. Ceci nécessite donc une structure de données contenant la donnée à stocker ainsi que le référent. Par abus de langage, aussi bien la donnée que la structure sont appelées éléments, la listé liée proprement dite étant l'ensemble de fonctions permettant de parcourir et de modifier de telles structures.

Ce système de référents permet, à partir de la connaissance du premier élément de la liste, aussi appelé élément de tête, d'accéder, de proche en proche, à l'élément voulu. Le fait de devoir accéder à chacun des éléments explique la lenteur relative en accès de cette structure de données. Il est tout aussi possible d'expliquer pourquoi l'insertion d'élément est plus rapide que dans le cas d'un tableau ayant une taille égale au nombre d'éléments contenus. Pour la liste liée l'insertion consiste en l'allocation de mémoire, uniquement pour l'élément inséré, et du chaînage des référents. Dans le cas du tableau, il est nécessaire de réallouer de l'espace pour l'entièreté des éléments et ensuite de copier les éléments existants vers le nouveau tableau, à l'endroit voulu. Des considérations similaires s'appliquent pour la suppression, ou l'ajout en fin de liste d'un élément.

Comme pour de nombreuses structures de données, il est souvent utile de connaître le nombre d'éléments stockés. Il s'agit soit de parcourir l'entièreté de la liste en comptant les éléments, ou plus simplement de maintenir une variable de comptage des éléments.

Variantes

Nous exposons ici deux variantes classiques de la liste liée, a titre purement informatif.

  • La liste doublement liée est une liste pour laquelle chaque élément est lié non seulement à l'élément suivant, mais aussi à l'élément précédent. Ceci facilite certaines opérations de parcours de la liste et améliore la performance de certains accès.
  • La liste liée circulaire est une liste pour laquelle le dernier élément est lié au premier. Ceci offre des facilités lorsqu'un traitement sur tous les éléments est nécessaire, mais que l'on ne souhaite pas forcément terminer le traitement d'un élément avant de passer au suivant. Le traitement de chaque élément sera ainsi effectué en plusieurs passes, parcourant les éléments de proche en proche, puisque tout élément possède un élément suivant. Une liste doublement liée et circulaire est aussi possible.

Réalisation

Sous Visual Basic, la manière la plus courante d'utiliser une liste liée, est d'utiliser un objet Collection. C'est très généralement la méthode à préférer, la mise en oeuvre de cette solution étant simple et l'accès rapide par table de hachage étant implémenté. Néanmoins, pour l'exercice, voici une implémentation possible d'une liste liée en Visual Basic.

Nous implémentons une liste liée classique, possédant les méthodes suivantes où nous choisissons que Data sera un Long. Il est bien entendu possible d'implémenter la même structure pour stocker tout autre type de données ; Notamment, l'objet Collection offre l'accès à des Variant, afin de s'affranchir du type de donnée.

  • Current : Détermine la valeur de l'élément courant
  • Insert(Data) : Ajoute un élément (Data) à la position courante
  • Remove : Supprime l'élément courant
  • MoveFirst : Se déplace vers le premier élément de la liste
  • MoveNext : Se déplace vers l'élément suivant celui courant. Retourne un booléen indiquant si un tel élément était présent.
  • MoveLast : Se déplace à la fin de la liste, après le dernier élément.

Les points importants afin de comprendre l'implémentation sont les suivants

  • la présence de la classe permettant le stockage d'un élément
  • les méthodes de parcours (MoveFirst, MoveNext, MoveLast) permettent de définir l'élément courant
  • Les méthodes Insert et Remove réalisent le chaînage des éléments de manière appropriée

Le module de classe ListNode décrit un élément (ou noeud) dans la liste :

Option Explicit

Private m_Data As Long
Private m_Next As ListNode

'Données correspondant au noeud
Public Property Get Data() As Long
    Data = m_Data
End Property

Public Property Let Data(Value As Long)
    m_Data = Value
End Property

'Noeud suivant dans la liste
Public Property Get NextNode() As ListNode
    Set NextNode = m_Next
End Property

Public Property Set NextNode(Value As ListNode)
    Set m_Next = Value
End Property

Le module de classe suivant décrit un les méthodes d'accès à la liste proprement dite :

Option Explicit

Private m_Head As ListNode
Private m_Previous As ListNode
Private m_Current As ListNode
Private m_Count As Long

Public Sub Insert(Value As Long)
    Dim LinkSave As ListNode
    
    'Si aucune donnée n'est déjà présente, crée une tête de liste
    If (m_Count = 0) Then
        Set m_Head = New ListNode
        m_Head.Data = Value
        Set m_Current = m_Head
    Else
        'Si l'utilisateur veut changer la tête de liste
        If m_Current Is m_Head Then
            'Crée le nouveau noeud et effectue le chainage
            Set LinkSave = m_Head
            Set m_Head = New ListNode
            m_Head.Data = Value
            Set m_Head.NextNode = LinkSave
            Set m_Current = m_Head
            
        'Si on est pas en dehors de la liste
        ElseIf Not m_Previous Is Nothing Then
            'Crée le nouveau noeud et effectue le chainage
            Set m_Previous.NextNode = New ListNode
            m_Previous.NextNode.Data = Value
            Set m_Previous.NextNode.NextNode = m_Current
            Set m_Current = m_Previous.NextNode
        End If
    End If
    
    m_Count = m_Count + 1
End Sub

Public Sub Remove()
    'S'il est possible de supprimer des noeuds
    If m_Count <> 0 Then
        'Si l'utilisateur désire supprimer la tête, celle-ci devient le second élément
        If m_Current Is m_Head Then
            Set m_Head = m_Head.NextNode
            Set m_Current = m_Head
        'Si l'utilisateur tente de supprimer un autre noeud, effectue le chaînage approprié
        ElseIf Not m_Current Is Nothing Then
            Set m_Previous.NextNode = m_Current.NextNode
            Set m_Current = m_Previous.NextNode
        End If
        
        m_Count = m_Count - 1
    End If
End Sub

'Déplacement l'élément courant en début de liste
Public Sub MoveFirst()
    Set m_Current = m_Head
    Set m_Previous = Nothing
End Sub

'Déplacement l'élément courant vers le suivant
Public Function MoveNext() As Boolean
    MoveNext = False
    
    If Not m_Current Is Nothing Then
        Set m_Previous = m_Current
        Set m_Current = m_Current.NextNode
    'Si aucun élément n'est sélectionné, reviens au début
    ElseIf m_Previous Is Nothing And m_Current Is Nothing Then
        MoveFirst
    End If
    
    MoveNext = Not (m_Current Is Nothing)
End Function

Public Sub MoveLast()
    While (MoveNext)
    Wend
End Sub

Public Property Get Count() As Long
    Count = m_Count
End Property

Public Property Get IsEmpty() As Boolean
    IsEmpty = (m_Count = 0)
End Property

Public Function Current() As Long
    If Not m_Current Is Nothing Then
        Current = m_Current.Data
    End If
End Function

La fonction suivante présente un exemple d'utilisation :

Public Sub Test()
    Dim a As New LinkedList

    a.Insert 1 '1
    a.MoveNext
    a.Insert 2 '1 2
    a.MoveNext
    a.Insert 5 '1 2 5
    a.Remove   '1 2
    a.Insert 4 '1 2 4
    a.Insert 3 '1 2 3 4
    
    'Enumère les éléments et les affiche
    a.MoveFirst
    Do
        Debug.Print a.Current '1 2 3 4
    Loop While a.MoveNext
    Debug.Print a.IsEmpty 'False
    
    'Parcours les éléments et les supprime jusqu'à ce qu'il n'y en ait plus
    a.MoveFirst
    Do
        Debug.Print a.Current '1 2 3 4
        a.Remove
    Loop While Not a.IsEmpty
    Debug.Print a.IsEmpty 'true
End Sub

Simplifier l'utilisation

La plupart des frameworks modernes proposent une implémentation générique des listes où des méthodes permettant d'ajouter des éléments directement en fin de liste (Add), d'ajouter des éléments en milieu de liste (Insert), de supprimer des éléments dans la liste (Remove), et de récupérer la valeur d'un élément dans la liste (Item), sur base uniquement de la position de l'élément et non de l'élément courant. La position du premier élément est alors couramment définie comme étant 1 et non 0.

L'objet Collection, par exemple, opte pour cette approche. L'avantage est que l'utilisation d'un tel objet est plus intuitive, au détriment des performances, les (nombreux) mouvements du pointeur courant étant invisibles à l'utilisateur.

Sur base de l'implémentation précédente, nous vous proposons aussi un objet offrant un accès simplifié. Il est possible de réaliser une implémentation beaucoup plus directe et/ou performantes de telles méthodes, néanmoins le principe reste semblable : il est nécessaire de se déplacer jusqu'à l'élément voulu, puis d'effectuer l'opération souhaitée sur la liste.

Les méthodes suivantes sont implémentées, toujours pour Data de type Long :

  • Add(Data) : Ajoute la valeur Data en fin de liste
  • Insert(Data, Index) : Ajoute la valeur Data à la position Index
  • Remove (Index) : Supprime la valeur à la position Index
  • Clear : Supprime toutes les valeurs contenues dans la liste
  • Item(Index) : Retrouve la valeur à la position Index
  • Count : Détermine la position dans la liste

Les points importants de cette implémentation sont les suivants :

  • Chaque fonction qui nécessite une référence à un élément de position donnée fait appel à la méthode ListGoto. Ceci permet de définir la position du pointeur courant à Index.
  • Les opérations sur les noeuds proprement dit sont effectuées par la classe sous-jacente, dont l'implémentation a été proposée ci-dessus.

Option Explicit

Private mLinkedList As LinkedList

Private Sub Class_Initialize()
    Set mLinkedList = New LinkedList
End Sub

Private Sub Class_Terminate()
    Set mLinkedList = Nothing
End Sub

'Ajoute une valeur en fin de liste
Public Sub Add(Value As Long)
    mLinkedList.MoveLast
    mLinkedList.Insert Value
End Sub

'Ajoute une valeur à une position donnée
Public Sub Insert(Value As Long, Index As Long)
    ListGoto Index
    mLinkedList.Insert Value
End Sub

'Supprime la valeur a une position donnée
Public Sub Remove(Index As Long)
    ListGoto Index
    mLinkedList.Remove
End Sub

Public Sub Clear()
    While (LinkedList_Count <> 0)
        Remove 1
    Wend
End Sub

'Retrouve la valeur a une position donnée
Public Function Item(Index As Long) As Long
    ListGoto Index
    Item = mLinkedList.Current
End Function

Public Property Get Count() As Long
    Count = mLinkedList.Count
End Property

'Déplace l'élément courant à la position Index dans la liste
Public Sub ListGoto(Index As Long)
    Dim i As Long
    
    'Vérifie que l'Index donné correspond à un élément dans la liste
    If Index < 1 Or Index > mLinkedList.Count Then
        Err.Raise 9 'Subscript out of range
    End If
    
    'Effectue un parcours complet jusqu'à l'élément voulu
    mLinkedList.MoveFirst
    
    For i = 1 To Index - 1
        mLinkedList.MoveNext
    Next i
End Sub

La fonction suivante présente un exemple d'utilisation :

Public Sub Test2()
    Dim hla As New LinkedListHL
    Dim i As Long

    hla.Add 10       '10
    hla.Add 20       '10 20
    hla.Add 30       '10 20 30
    hla.Insert 15, 2 '10 15 20 30
    hla.Remove 4     '10 15 20
    
    For i = 1 To hla.Count
        Debug.Print hla.Item(i) '10 15 20
    Next i
End Sub

Voir aussi :

Date de publication : 13 septembre 2007
Dernière modification : 13 septembre 2007
Rubriques : Structures de données
Mots-clés : liste, liée, chainée, structure, donnée, dynamique, élément, index