Share
La première structure de données que nous examinerons est la liste chaînée, et avec raison. En plus d’être une structure presque omniprésente utilisée dans tout, des systèmes d’exploitation aux jeux vidéo, c’est aussi un bloc de construction avec lequel de nombreuses autres structures de données peuvent être créées..
De manière très générale, le but d'une liste chaînée est de fournir un mécanisme cohérent pour stocker et accéder à une quantité arbitraire de données. Comme son nom l'indique, il le fait en liant les données dans une liste..
Avant de plonger dans ce que cela signifie, commençons par examiner le mode de stockage des données dans un tableau..
Données entières stockées dans un tableau Comme le montre la figure, les données de la matrice sont stockées sous la forme d'un bloc de mémoire alloué de manière contiguë et segmenté de manière logique. Les données stockées dans le tableau sont placées dans l’un de ces segments et référencées via son emplacement, ou index, dans le tableau..
C'est un bon moyen de stocker des données. La plupart des langages de programmation facilitent l’allocation de tableaux et leur fonctionnement. Le stockage de données contiguë offre des avantages en termes de performances (notamment la localisation des données), il est simple d'effectuer une itération sur les données et d'accéder directement aux données par index (accès aléatoire) en temps constant..
Il arrive cependant qu'un tableau ne soit pas la solution idéale.
Considérons un programme avec les exigences suivantes:
Accentsconagua
NextValue méthode) jusqu'à ce que le nombre 0xFFFF soit rencontré.ProcessItems méthode.Comme les exigences indiquent que plusieurs valeurs doivent être transmises à la ProcessItems En un seul appel, une solution évidente consisterait à utiliser un tableau d’entiers. Par exemple:
void LoadData () // Supposons que 20 suffise pour contenir les valeurs. int [] valeurs = new int [20]; pour (int i = 0; i < values.Length; i++) if (values[i] == 0xFFFF) break; values[i] = NextValue(); ProcessItems(values); void ProcessItems(int[] values) //… Process data.
Cette solution présente plusieurs problèmes, mais le plus criant est visible lorsque plus de 20 valeurs sont lues. Comme le programme est maintenant, les valeurs de 21 à n sont simplement ignorées. Cela pourrait être atténué en affectant plus de 20 valeurs, peut-être 200 ou 2000. Peut-être que la taille pourrait être configurée par l'utilisateur, ou peut-être que si le tableau était plein, un tableau plus grand pourrait être alloué et toutes les données existantes copiées dans celui-ci. En fin de compte, ces solutions créent de la complexité et gaspillent de la mémoire.
Ce dont nous avons besoin, c'est d'une collection qui nous permette d'ajouter un nombre arbitraire de valeurs entières, puis d'énumérer ces entiers dans l'ordre dans lequel ils ont été ajoutés. La collection ne doit pas avoir une taille maximale fixe et l'indexation à accès aléatoire n'est pas nécessaire. Nous avons besoin d'une liste chaînée.
Avant de poursuivre et de découvrir comment la structure de données de la liste chaînée est conçue et implémentée, voyons un aperçu de ce à quoi notre solution ultime pourrait ressembler.
static void LoadItems () Liste LinkedList = new LinkedList (); while (true) int value = NextValue (); if (valeur! = 0xFFFF) list.Add (valeur); else pause; ProcessItems (list); static void ProcessItems (liste LinkedList) //… Données de processus.
Notez que tous les problèmes liés à la solution de tableau n'existent plus. Il n'y a plus aucun problème avec le tableau qui n'est pas assez grand ou qui alloue plus que nécessaire.
Vous remarquerez également que cette solution informe certaines des décisions de conception que nous prendrons plus tard, à savoir que LinkedList classe accepte un argument de type générique et implémente le IEnumerable interface.
La classe de nœud est au cœur de la structure de données de la liste liée. Un nœud est un conteneur qui permet de stocker des données et de se connecter à d'autres nœuds..
Un nœud de liste lié contient des données et une propriété pointant sur le nœud suivant Dans sa forme la plus simple, une classe Node contenant des entiers pourrait ressembler à ceci:
Classe publique Node public int Value get; ensemble; public Node Next get; ensemble;
Avec cela, nous pouvons maintenant créer une liste chaînée très primitive. Dans l'exemple suivant, nous allons allouer trois nœuds (premier, deuxième et dernier), puis les lier ensemble dans une liste..
// + ----- + ------ + // | 3 | null + // + ----- + ------ + Noeud en premier = nouveau Noeud Valeur = 3; // + ----- + ------ + + ----- + ------ + // | 3 | null + | 5 | null + // + ----- + ------ + + ----- + ------ + Noeud au milieu = nouveau Noeud Valeur = 5; // + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + // + ----- + ------ + + ----- + ------ + first.Next = middle; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | null + | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + Node last = new Noeud valeur = 7; // + ----- + ------ + + ----- + ------ + + ----- + ------ + // | 3 | * --- + ---> | 5 | * --- + -> | 7 | null + // + ----- + ------ + + ----- + ------ + + ----- + ------ + middle.Next = dernier;
Nous avons maintenant une liste chaînée qui commence par le noeud premier et se termine par le noeud dernier. le Suivant La propriété du dernier noeud pointe sur null, qui est l'indicateur de fin de liste. Avec cette liste, nous pouvons effectuer certaines opérations de base. Par exemple, la valeur de chaque noeud Les données propriété:
void statique privé PrintList (noeud Noeud) while (noeud! = null) Console.WriteLine (noeud.Value); noeud = noeud.Suivant;
le PrintList Cette méthode itère sur chaque nœud de la liste, affiche la valeur du nœud actuel, puis passe au nœud pointé par le Suivant propriété.
Maintenant que nous comprenons à quoi pourrait ressembler un nœud de liste chaînée, examinons la LinkedListNode classe.
Classe publique LinkedListNode /// /// Construit un nouveau nœud avec la valeur spécifiée. /// public LinkedListNode (valeur T) Valeur = valeur; /// /// La valeur du noeud. /// valeur T publique get; ensemble interne; /// /// Le prochain noeud de la liste liée (null si dernier noeud). /// public LinkedListNode Next get; ensemble interne;
Avant de mettre en œuvre notre LinkedList classe, nous devons réfléchir à ce que nous aimerions pouvoir faire avec la liste.
Nous avons déjà constaté que la collection devait prendre en charge des données fortement typées. Nous souhaitons donc créer une interface générique..
Puisque nous utilisons le framework .NET pour implémenter la liste, il est logique que nous souhaitions que cette classe puisse agir comme les autres types de collection intégrés. Le moyen le plus simple de le faire est de mettre en œuvre le ICollection interface. Remarquez que je choisis ICollection et pas IListe. C'est parce que le IListe interface ajoute la possibilité d'accéder aux valeurs par index. Bien que l’indexation directe soit généralement utile, elle ne peut pas être mise en œuvre efficacement dans une liste chaînée..
En tenant compte de ces exigences, nous pouvons créer un stub de classe de base, puis compléter le reste de la section avec ces méthodes..
Classe publique LinkedList: System.Collections.Generic.ICollection public void Ajouter (élément T) jeter un nouveau System.NotImplementedException (); public void Clear () jeter un nouveau System.NotImplementedException (); public bool Contains (T item) lance new System.NotImplementedException (); public void CopyTo (T [] tableau, int tableauIndex) jeter nouvelle System.NotImplementedException (); public int Count get; ensemble privé; public bool IsReadOnly get lance new System.NotImplementedException (); public bool Remove (élément T) jette new System.NotImplementedException (); public System.Collections.Generic.IEnumerator GetEnumerator () jette new System.NotImplementedException (); System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator () jette new System.NotImplementedException ();
| Comportement | Ajoute la valeur fournie à la fin de la liste liée. |
| Performance | O (1) |
L'ajout d'un élément à une liste chaînée implique trois étapes:
LinkedListNode exemple.Suivant propriété du dernier noeud du nouveau noeud.La clé est de savoir quel nœud est le dernier nœud de la liste. Nous pouvons le savoir de deux manières. La première consiste à suivre le premier nœud (le nœud «tête») et à parcourir la liste jusqu'à ce que nous ayons trouvé le dernier nœud. Cette approche ne nécessite pas de garder trace du dernier nœud, ce qui enregistre une mémoire de référence (quelle que soit la taille du pointeur de votre plate-forme), mais nécessite que nous fassions un parcours de la liste chaque fois qu'un nœud est ajouté. Cela ferait Ajouter une opération O (n).
La deuxième approche nécessite de garder trace du dernier nœud (le nœud «queue») de la liste et lorsque nous ajoutons le nouveau nœud, nous accédons simplement à notre référence stockée. C'est un algorithme O (1) et donc l'approche privilégiée.
La première chose à faire est d’ajouter deux champs privés à la liste. LinkedList classe: références aux premier (tête) et dernier (queue) nœuds.
private LinkedListNode _head; LinkedListNode privé _tail;
Ensuite, nous devons ajouter la méthode qui effectue les trois étapes.
public void Add (valeur T) LinkedListNode node = new LinkedListNode (valeur); if (_head == null) _head = noeud; _tail = noeud; else _tail.Next = noeud; _tail = noeud; Count ++;
Tout d'abord, il alloue le nouveau LinkedListNode exemple. Ensuite, il vérifie si la liste est vide. Si la liste est vide, le nouveau noeud est ajouté simplement en affectant le _tête et _queue références au nouveau noeud. Le nouveau nœud est maintenant à la fois le premier et le dernier nœud de la liste. Si la liste n'est pas vide, le nœud est ajouté à la fin de la liste et le _queue la référence est mise à jour pour pointer vers la nouvelle extrémité de la liste.
le Compter la propriété est incrémentée lorsqu’un nœud est ajouté pour assurer la ICollection. Compter propriété renvoie la valeur exacte.
| Comportement | Supprime le premier nœud de la liste dont la valeur est égale à la valeur fournie. La méthode renvoie true si une valeur a été supprimée. Sinon, il retourne faux. |
| Performance | Sur) |
Avant de parler du Retirer algorithme, jetons un coup d'oeil à ce qu'il essaie d'accomplir. Dans la figure suivante, il y a quatre nœuds dans une liste. Nous voulons supprimer le nœud avec la valeur trois.
Une liste chaînée avec quatre valeurs Lorsque la suppression est terminée, la liste sera modifiée de sorte que le Suivant propriété sur le noeud avec la valeur deux points sur le noeud avec la valeur quatre.
La liste liée avec le noeud 3 supprimé L'algorithme de base pour la suppression de nœud est le suivant:
Comme toujours, le diable est dans les détails. Il y a quelques cas auxquels nous devons penser lors de la suppression d'un nœud:
_tête et _queue champs à nul._tête champ pour pointer vers le nouveau noeud principal._queue champ pour référencer l'avant-dernier nœud de la liste et définir son Suivant propriété à nul.public bool Remove (élément T) LinkedListNode previous = null; LinkedListNode current = _head; // 1: Liste vide: ne rien faire. // 2: nœud unique: Previous est null. // 3: Plusieurs nœuds: // a: Le nœud à supprimer est le premier nœud. // b: le nœud à supprimer est le milieu ou le dernier. while (current! = null) if (current.Value.Equals (item)) // C'est un nœud au milieu ou à la fin. if (précédent! = null) // Cas 3b. // Avant: Head -> 3 -> 5 -> null // Après: Head -> 3 ------> null previous.Next = current.Next; // C'était la fin, alors mettez à jour _tail. if (current.Next == null) _tail = previous; else // Cas 2 ou 3a. // Avant: Head -> 3 -> 5 // Après: Head ------> 5 // Head -> 3 -> null // Head ------> null _head = _head.Next; // La liste est-elle maintenant vide? if (_head == null) _tail = null; Compter--; retourne vrai; précédent = courant; current = current.Next; return false;
le Compter la propriété est décrémentée lorsqu’un nœud est supprimé pour assurer la ICollection. Compter propriété renvoie la valeur exacte.
| Comportement | Renvoie une valeur booléenne indiquant si la valeur fournie existe dans la liste liée.. |
| Performance | Sur) |
le Contient la méthode est assez simple. Il examine tous les nœuds de la liste, du premier au dernier, et renvoie true dès qu'un nœud correspondant au paramètre est trouvé. Si la fin de la liste est atteinte et que le noeud n'est pas trouvé, la méthode retourne faux.
public bool Contient (élément T) LinkedListNode current = _head; while (current! = null) if (current.Value.Equals (item)) return true; current = current.Next; return false;
| Comportement | Renvoie une instance IEnumerator qui permet d'énumérer les valeurs de la liste liée du premier au dernier.. |
| Performance | Le renvoi de l'instance de l'énumérateur est une opération O (1). L'énumération de chaque élément est une opération O (n). |
GetEnumerator est implémenté en énumérant la liste du premier au dernier nœud et utilise le C # rendement mot clé pour retourner la valeur du noeud actuel à l'appelant.
Notez que LinkedList implémente le comportement d’itération dans le IEnumerable version de la méthode GetEnumerator et adopte ce comportement dans la version IEnumerable.
IEnumerator IEnumerable.GetEnumerator () LinkedListNode current = _head; while (current! = null) return return current.Value; current = current.Next; IEnumerator IEnumerable.GetEnumerator () return ((IEnumerable) this) .GetEnumerator ();
| Comportement | Supprime tous les éléments de la liste. |
| Performance | O (1) |
le Clair méthode définit simplement la _tête et _queue champs à null pour effacer la liste. Parce que .NET est un langage mal ordonné, il n’est pas nécessaire de supprimer explicitement les nœuds. C’est la responsabilité de l’appelant, et non de la liste chaînée, de s’assurer que si les nœuds contiennent IDisposable références ils sont correctement éliminés.
public void Clear () _head = null; _tail = null; Compter = 0;
| Comportement | Copie le contenu de la liste liée du début à la fin dans le tableau fourni, en commençant à l'index de tableau spécifié. |
| Performance | Sur) |
le Copier La méthode itère simplement sur les éléments de la liste et utilise une simple affectation pour copier les éléments dans le tableau. L'appelant a la responsabilité de s'assurer que le tableau cible contient l'espace libre approprié pour accueillir tous les éléments de la liste..
public void CopyTo (T [] tableau, int tableauIndex) LinkedListNode current = _head; while (current! = null) array [arrayIndex ++] = current.Value; current = current.Next;
| Comportement | Retourne un entier indiquant le nombre d'éléments actuellement dans la liste. Lorsque la liste est vide, la valeur renvoyée est 0. |
| Performance | O (1) |
Compter est simplement une propriété implémentée automatiquement avec un getter public et un setter privé. Le vrai comportement se passe dans le Ajouter, Retirer, et Clair les méthodes.
public int Count get; ensemble privé;
| Comportement | Retourne false si la liste n'est pas en lecture seule. |
| Performance | O (1) |
public bool IsReadOnly get return false;
La classe LinkedList que nous venons de créer s'appelle une liste chaînée unique. Cela signifie qu'il n'existe qu'un seul lien unidirectionnel entre un nœud et le nœud suivant dans la liste. Il existe une variante commune de la liste chaînée qui permet à l'appelant d'accéder à la liste des deux côtés. Cette variation est connue sous le nom de liste doublement liée.
Pour créer une liste doublement chaînée, nous devons d’abord modifier notre classe LinkedListNode afin d’avoir une nouvelle propriété nommée Précédent. Previous agira comme Next, seul il pointera sur le noeud précédent dans la liste.
Une liste doublement liée utilisant une propriété de noeud précédent Les sections suivantes décrivent uniquement les changements entre la liste à liens simples et la nouvelle liste à liens doubles.
Le seul changement qui sera apporté à la LinkedListNode la classe est l'ajout d'une nouvelle propriété nommée précédent qui pointe vers le précédent LinkedListNode dans la liste liée, ou retourne nul si c'est le premier noeud de la liste.
Classe publique LinkedListNode /// /// Construit un nouveau nœud avec la valeur spécifiée. /// /// public LinkedListNode (valeur T) Valeur = valeur; /// /// La valeur du noeud. /// valeur T publique get; ensemble interne; /// /// Le prochain noeud de la liste liée (null si dernier noeud). /// public LinkedListNode Next get; ensemble interne; /// /// Le noeud précédent dans la liste liée (null si premier noeud). /// public LinkedListNode Previous get; ensemble interne;
Alors que la liste à liens simples n’ajoute que des noeuds à la fin de la liste, la liste à liens doubles permet d’ajouter des noeuds au début et à la fin de la liste à AddFirst et Ajouter le dernier, respectivement. le ICollection. Ajouter la méthode sera reportée à la Ajouter le dernier méthode permettant de conserver la compatibilité avec le liste classe.
| Comportement | Ajoute la valeur fournie au début de la liste. |
| Performance | O (1) |
Lors de l'ajout d'un nœud au début de la liste, les actions sont très similaires à l'ajout à une liste chaînée..
Suivant propriété du nouveau noeud sur l'ancien noeud principal.précédent propriété de l'ancien noeud principal au nouveau noeud._queue champ (si nécessaire) et incrémentation Compter.public void AddFirst (valeur T) LinkedListNode node = new LinkedListNode (value); // Sauvegarde le nœud principal pour ne pas le perdre. LinkedListNode temp = _head; // Pointez la tête sur le nouveau noeud. _head = noeud; // Insère le reste de la liste derrière la tête. _head.Next = temp; if (Count == 0) // Si la liste était vide, alors la tête et la queue devraient // toutes deux pointer vers le nouveau nœud. _tail = _head; else // Avant: tête -------> 5 <-> 7 -> null // Après: tête -> 3 <-> 5 <-> 7 -> null temp.Previous = _head; Count ++;
| Comportement | Ajoute la valeur fournie à la fin de la liste. |
| Performance | O (1) |
Ajouter un nœud à la fin de la liste est encore plus facile que d'en ajouter un au début.
Le nouveau noeud est simplement ajouté à la fin de la liste, mettant à jour l’état de _queue et _tête selon le cas, et Compter est incrémenté.
Void public AddLast (valeur T) noeud LinkedListNode = new LinkedListNode (valeur); if (Count == 0) _head = noeud; else _tail.Next = noeud; // Avant: Tête -> 3 <-> 5 -> null // After: Head -> 3 <-> 5 <-> 7 -> null // 7.Previous = 5 node.Previous = _tail; _tail = noeud; Comptez ++;
Et comme mentionné précédemment, ICollection.Ajouter va maintenant simplement appeler Ajouter le dernier.
public void Add (valeur T) AddLast (valeur);
Comme Ajouter, la Retirer Cette méthode sera étendue pour prendre en charge la suppression des nœuds du début ou de la fin de la liste. le ICollection.La méthode de suppression continuera à supprimer les éléments depuis le début, le seul changement étant de mettre à jour le précédent propriété.
| Comportement | Supprime la première valeur de la liste. Si la liste est vide, aucune action n'est entreprise. Renvoie true si une valeur a été supprimée. Sinon, il retourne faux. |
| Performance | O (1) |
RemoveFirst met à jour la liste en définissant celle de la liste liée tête propriété au deuxième noeud de la liste et en mettant à jour son précédent propriété à nul. Cela supprime toutes les références au nœud principal précédent et le supprime de la liste. Si la liste ne contenait qu'un seul singleton ou était vide, la liste sera vide (le tête et queue les propriétés seront nul).
public void RemoveFirst () if (Count! = 0) // Avant: Tête -> 3 <-> 5 // Après: Head -------> 5 // Head -> 3 -> null // Head ------> null _head = _head.Next; Compter--; if (Count == 0) _tail = null; else // 5.Previous avait 3 ans; maintenant c'est nul. _head.Previous = null;
| Comportement | Supprime le dernier nœud de la liste. Si la liste est vide, aucune action n'est effectuée. Renvoie true si une valeur a été supprimée. Sinon, il retourne faux. |
| Performance | O (1) |
SupprimerLast fonctionne en définissant la liste queue propriété d'être le noeud précédant le noeud de queue actuel. Cela supprime le dernier nœud de la liste. Si la liste était vide ou ne comportait qu'un seul nœud, lorsque la méthode renvoie le tête et queue propriétés, ils seront tous deux nul.
public void RemoveLast () if (Count! = 0) if (Count == 1) _head = null; _tail = null; else // Avant: tête -> 3 -> 5 -> 7 // queue = 7 // après: tête -> 3 -> 5 -> null // queue = 5 // nul out 5's Next propriété. _tail.Previous.Next = null; _tail = _tail.Previous; Compter--;
| Comportement | Supprime le premier nœud de la liste dont la valeur est égale à la valeur fournie. La méthode renvoie true si une valeur a été supprimée. Sinon, il retourne faux. |
| Performance | Sur) |
le ICollection. Retirer La méthode est presque identique à la version liée uniquement, sauf que la précédent La propriété est maintenant mise à jour pendant l'opération de suppression. Pour éviter le code répété, la méthode appelle RemoveFirst lorsqu'il est déterminé que le nœud en cours de suppression est le premier nœud de la liste.
public bool Remove (élément T) LinkedListNode previous = null; LinkedListNode current = _head; // 1: Liste vide: ne rien faire. // 2: nœud unique: Previous est null. // 3: Plusieurs nœuds: // a: Le nœud à supprimer est le premier nœud. // b: le nœud à supprimer est le milieu ou le dernier. while (current! = null) // Head -> 3 -> 5 -> 7 -> null // Head -> 3 ------> 7 -> null if (current.Value.Equals (item) ) // C'est un nœud au milieu ou à la fin. if (précédent! = null) // Cas 3b. previous.Next = current.Next; // C'était la fin, alors mettez à jour _tail. if (current.Next == null) _tail = previous; else // Avant: Tête -> 3 <-> 5 <-> 7 -> null // After: Head -> 3 <-------> 7 -> null // previous = 3 // current = 5 // current.Next = 7 // Donc… 7.Previous = 3 current.Next.Previous = previous; Compter--; else // Cas 2 ou 3a. RemoveFirst (); return true; précédent = courant; current = current.Next; return false;
Nous pouvons ajouter des nœuds au début et à la fin de la liste. Et alors? Pourquoi on s'en soucie? En l'état actuel des choses, le double lien liste la classe n'est pas plus puissante que la liste à lien unique. Mais avec une seule modification mineure, nous pouvons ouvrir toutes sortes de comportements possibles. En exposant le tête et queue propriétés en tant que propriétés publiques en lecture seule, le consommateur de liste liée sera en mesure d'implémenter toutes sortes de nouveaux comportements.
public LinkedListNode Head get return _head; public LinkedListNode Tail get return _tail;
Avec ce simple changement, nous pouvons énumérer la liste manuellement, ce qui nous permet d’effectuer une énumération inverse (en tête à tête) et une recherche..
Par exemple, l’exemple de code suivant montre comment utiliser les éléments de la liste. Queue et précédent propriétés pour énumérer la liste en sens inverse et effectuer un traitement sur chaque nœud.
public void ProcessListBackwards () Liste LinkedList = new LinkedList (); PopulateList (liste); LinkedListNode current = list.Tail; while (current! = null) ProcessNode (current); current = current.Previous;
De plus, le double lien liste classe nous permet de créer facilement la Deque class, qui est elle-même un bloc de construction pour les autres classes. Nous discuterons de cette classe plus tard dans une autre section.
