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éeDans 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. VariantesNous 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éalisationSous 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
Public Property Get Data() As Long
Data = m_Data
End Property
Public Property Let Data(Value As Long)
m_Data = Value
End Property
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
If (m_Count = 0) Then
Set m_Head = New ListNode
m_Head.Data = Value
Set m_Current = m_Head
Else
If m_Current Is m_Head Then
Set LinkSave = m_Head
Set m_Head = New ListNode
m_Head.Data = Value
Set m_Head.NextNode = LinkSave
Set m_Current = m_Head
ElseIf Not m_Previous Is Nothing Then
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()
If m_Count <> 0 Then
If m_Current Is m_Head Then
Set m_Head = m_Head.NextNode
Set m_Current = m_Head
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
Public Sub MoveFirst()
Set m_Current = m_Head
Set m_Previous = Nothing
End Sub
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
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
a.MoveNext
a.Insert 2
a.MoveNext
a.Insert 5
a.Remove
a.Insert 4
a.Insert 3
a.MoveFirst
Do
Debug.Print a.Current
Loop While a.MoveNext
Debug.Print a.IsEmpty
a.MoveFirst
Do
Debug.Print a.Current
a.Remove
Loop While Not a.IsEmpty
Debug.Print a.IsEmpty
End Sub Simplifier l'utilisationLa 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
Public Sub Add(Value As Long)
mLinkedList.MoveLast
mLinkedList.Insert Value
End Sub
Public Sub Insert(Value As Long, Index As Long)
ListGoto Index
mLinkedList.Insert Value
End Sub
Public Sub Remove(Index As Long)
ListGoto Index
mLinkedList.Remove
End Sub
Public Sub Clear()
While (LinkedList_Count <> 0)
Remove 1
Wend
End Sub
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
Public Sub ListGoto(Index As Long)
Dim i As Long
If Index < 1 Or Index > mLinkedList.Count Then
Err.Raise 9
End If
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
hla.Add 20
hla.Add 30
hla.Insert 15, 2
hla.Remove 4
For i = 1 To hla.Count
Debug.Print hla.Item(i)
Next i
End Sub Voir aussi : |
Top