Question 162

Comment réaliser et utiliser une liste sur base d'un tableau dynamique ?

Les tableaux de données dynamiques sont des structures de données utiles lorsqu'il est impossible de déterminer à l'avance le nombre d'éléments contenus. Un tel conteneur de données est souvent encapsulé dans une classe pour les raisons classiques de facilités de maintenance du code, réutilisabilité et masquage d'implémentation. Les termes suivants — liste non exhaustive — désignent une telle structure de données : Tableau dynamique, ArrayList — en référence aux classes du même nom présentes dans la JRE et le .Net framework, Extendable Array, Growable Array. Dans la suite de cet article nous emploierons le terme d'ArrayList. Les fonctionnalités implémentées peuvent varier fortement en fonction des besoins. En voici quelques exemples : Insertion au milieu d'une liste, suppression au milieu d'une liste, tris des éléments, pré-allocation de mémoire.

Structure d'une ArrayList

Une ArrayList est un objet effectuant des opérations sur un tableau interne et proposant au moins des accesseurs aux éléments du tableau. D'autres méthodes typiques des listes, telles que l'ajout, l'insertion et la suppression d'éléments sont généralement proposées.

L'insertion ou la suppression d'un élément dans une ArrayList est coûteuse en temps d'exécution puisque, comme pour la manipulation classique d'un tableau, certains éléments devront être déplacés. Au contraire, l'accès à un élément de position donnée reste très rapide.

Lorsque l'entière capacité du tableau est utilisée, il est nécessaire de redimensionner ce dernier. Ceci passe par la ré-allocation de suffisamment de mémoire et la copie des données précédentes. Il est important d'effectuer le moins de ré-allocations possibles, pour des raisons de performances, tout en occupant un espace mémoire raisonnable.

Variantes

Bien qu'elles puisse être implémentées sur base d'autres structures de données, les listes triées, ou sorted list, sont souvent implémentées sur base d'un tableau. Ce type de liste peut soit insèrer directement les éléments ajoutés à l'endroit approprié. Une autre manière d'aborder le problème est d'exposer une méthode supplémentaire permettant le tri des éléments contenus, à la demande.

Au contraire les listes liées, les listes basées sur des tableaux ont souvent pour premier élément celui de position 0, en référence au tableau sous-jacent. Différentes implémentations peuvent cependant changer d'indice de base.

Tout comme les listes liées, les ArrayList des frameworks modernes allouent dynamiquement la mémoire utilisée en fonction des ajouts (et éventuellement des suppressions) d'éléments. Il est néanmoins possible d'utiliser un tableau alloué statiquement pour réaliser une ArrayList. Il est alors important de prévoir un mécanisme pour avertir l'utilisateur de la classe lorsque la capacité maximale est atteinte.

Réalisation

L'implémentation proposée est volontairement simple et n'est pas conçue pour offrir les meilleures performances. Nous implémentons une ArrayList pré-allouant la mémoire par bloc de taille constante. Les méthodes suivantes, où nous choisissons Data de type Long, seront implémentées. Il est bien entendu possible d'implémenter la même structure pour stocker tout autre type de données.

• Add(Data) : Ajoute un élément (Data) en fin de liste
• Insert(Data, index) : Ajoute un élément (Data) à la position (index) indiquée
• Item(Index) : Retrouve l'élément à la position (index) donnée
• Remove(Index) : Supprime l'élément à la position (index) donnée
• Count : Détermine le nombre d'éléments dans la liste
• AllocateElements : Permet d'allouer des éléments avant ajout
• Clear : Supprime tous les éléments présents

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

• L'allocation est réalisée par Redim Preserve. Cette opération est publique, mais est appelée en privé dans toutes les méthodes qui réalisent un ajout.
• Les méthodes d'insertion et de suppression réalisent des déplacements de partie entières de tableau. Le sens de parcours pour les déplacements est différent, afin de ne pas écraser des données existantes.
• Une première allocation est réalisée à l'initialisation (à l'aide de Clear) afin faciliter la suite des opérations.

Option Explicit
Private mData() As Long
Private mLength As Long
Private Const mChunkLength As Long = 256

'Ajoute un élément au tableau, en prenant soin de faire
'les allocations par bloc nécessaires
Public Sub Add(Value As Long)
    AllocateElements 1
    
    'Prend en compte la nouvelle valeur
    mData(mLength) = Value
    mLength = mLength + 1
End Sub

Public Sub AllocateElements(ByVal Count As Long)
    'On essaye de redimensionner que s'il y a lieu de le faire
    If Count <> 0 Then
        'La place à allouer est le nombre d'éléments à ajouter diminué du nombre
        'd'éléments que l'on peut encore ajouter
        Count = Count - (UBound(mData) - mLength + 1)
        
        'S'il n'y a pas assez de place pour tout le monde
        If (Count > 0) Then
            RedimArray UBound(mData) + (Int(Count / mChunkLength) + 1) * mChunkLength
        End If
    End If
End Sub

Private Sub RedimArray(NewSize As Long)
    'Redimensionne le tableau
    If NewSize < 0 Then
        ReDim mData(0)
    Else
        ReDim Preserve mData(NewSize)
    End If
End Sub

Public Sub Insert(Value As Long, Index As Long)
    Dim i As Long
    
    If Index >= 0 And Index < mLength Then
        AllocateElements 1
        
        'Déplace tous les éléments suivant la position d'insertion
        For i = mLength - 1 To Index Step -1
            mData(i + 1) = mData(i)
        Next i
        
        'Insère le nouvel élément
        mData(Index) = Value
        mLength = mLength + 1
    End If
End Sub

Public Sub Remove(Index As Long)
    'Supprime l'élement Index du tableau.
    If Index >= 0 And Index < mLength Then
        Dim i As Long

        'Recopie tous les éléments suivants Index
        'un emplacement avant
        For i = Index + 1 To mLength - 1
            mData(i - 1) = mData(i)
        Next i

        mLength = mLength - 1
    End If
End Sub

Public Function Item(Index As Long) As Long
    Item = mData(Index)
End Function

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

Public Sub Clear()
    'Réinitialise le tableau de données
    Erase mData
    ReDim mData(mChunkLength - 1)
    mLength = 0
End Sub

Private Sub Class_Initialize()
    Clear
End Sub

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

Private Sub Test()
    Dim a As ArrayList
    Dim i As Long
    
    Set a = New ArrayList
    a.Add 10
    a.Add 20
    a.Add 40
    a.Add 30
    
    '10 20 40 30
    For i = 0 To a.Count - 1
        Debug.Print a.Item(i);
    Next i
    Debug.Print
    
    a.Insert 15, 1  '10 15 20 40 30
    a.Insert 35, 3  '10 15 20 35 40 30
    a.Remove 5      '10 15 20 35 40
    
    For i = 0 To a.Count - 1
        Debug.Print a.Item(i);
    Next i
    Debug.Print
End Sub

Voir aussi :

• Comment implémenter et utiliser les structures de données classiques ?
• Comment réaliser des allocations dynamiques ?