Structures de données et algorithmes en Java, Partie 5: Listes à double liaison

Bien que les listes à liaison simple aient de nombreuses utilisations, elles présentent également certaines restrictions. D'une part, les listes à liaison unique restreignent la traversée des nœuds à une seule direction: vous ne pouvez pas parcourir une liste à liaison unique vers l'arrière à moins que vous n'inversiez d'abord ses liens de nœuds, ce qui prend du temps. Si vous effectuez une traversée inverse et devez restaurer la traversée des nœuds dans la direction d'origine, vous devrez répéter l'inversion, ce qui prend plus de temps. Les listes à liaison unique restreignent également la suppression des nœuds. Dans ce type de liste, vous ne pouvez pas supprimer un nœud arbitraire sans accéder au prédécesseur du nœud.

Heureusement, Java propose plusieurs types de listes que vous pouvez utiliser pour rechercher et trier les données stockées dans vos programmes Java. Ce dernier didacticiel de la série Structures de données et algorithmes présente la recherche et le tri avec des listes à double lien et des listes à lien circulaire. Comme vous le verrez, ces deux catégories de structure de données s'appuient sur des listes à liaison unique pour offrir un plus large éventail de comportements de recherche et de tri dans vos programmes Java.

Listes à double lien

Une liste à double lien est une liste chaînée de nœuds où chaque nœud a une paire de champs de lien. Un champ de lien vous permet de parcourir la liste vers l'avant, tandis que l'autre nœud vous permet de parcourir la liste vers l'arrière. Pour la direction avant, une variable de référence contient une référence au premier nœud. Chaque nœud est lié au nœud suivant via le champ de lien "suivant", sauf pour le dernier nœud, dont le champ de lien "suivant" contient la référence nulle pour signifier la fin de la liste (dans le sens aller). La direction arrière fonctionne de la même manière. Une variable de référence contient une référence au dernier nœud de la direction avant, que vous interprétez comme le premier nœud. Chaque nœud est lié au nœud précédent via le champ de lien «précédent». Le "précédent" du premier nœudLe champ de lien contient null pour signifier la fin de la liste.

Essayez de penser à une liste à double liaison comme une paire de listes à liaison unique, chacune interconnectant les mêmes nœuds. Le diagramme de la figure 1 montre des topForwardlistes à topBackwardliaison unique référencées et référencées.

Opérations CRUD dans des listes à double lien

La création, l'insertion et la suppression de nœuds sont toutes des opérations courantes dans une liste à double lien. Ils sont similaires aux opérations que vous avez apprises pour les listes à liaison unique. (Rappelez-vous qu'une liste à double liaison est juste une paire de listes à liaison unique qui interconnectent les mêmes nœuds.) Le pseudo-code suivant illustre la création et l'insertion de nœuds dans la liste à double liaison illustrée à la figure 1. Le pseudo-code montre également le nœud effacement:

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next DECLARE Node prev END DECLARE DECLARE Node topForward DECLARE Node temp DECLARE Node topBackward topForward = NEW Node topForward.name = "A" temp = NEW Node temp.name = "B" topBackward = NEW Node topBackward.name = "C" // Create forward singly-linked list topForward.next = temp temp.next = topBackward topBackward.next = NULL // Create backward singly-linked list topBackward.prev = temp temp.prev = topForward topForward.prev = NULL // Delete Node B. temp.prev.next = temp.next; // Bypass Node B in the forward singly-linked list. temp.next.prev = temp.prev; // Bypass Node B in the backward singly-linked list. END 

Exemple d'application: CRUD dans une liste à double lien

L'exemple d'application Java DLLDemomontre comment créer, insérer et supprimer des nœuds dans une liste à double lien. Le code source de l'application est affiché dans le listing 1.

Listing 1. Une application Java démontrant CRUD dans une liste à double lien

 public final class DLLDemo { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Reference node B. temp = topForward.next; // Delete node B. temp.prev.next = temp.next; temp.next.prev = temp.prev; // Dump forward singly-linked list. System.out.print("Forward singly-linked list (after deletion): "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list (after deletion): "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } } 

Compilez le listing 4 comme suit:

 javac DLLDemo.java 

Exécutez l'application résultante comme suit:

 java DLLDemo 

Vous devez observer la sortie suivante:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list (after deletion): AC Backward singly-linked list (after deletion): CA 

Lecture aléatoire dans des listes à double lien

Le Java Collections Framework comprend une Collectionsclasse de méthodes utilitaires, qui fait partie du java.utilpackage. Cette classe comprend une void shuffle(List list)méthode qui « permute de manière aléatoire la liste spécifiée en utilisant une source par défaut de caractère aléatoire ». Par exemple, vous pouvez utiliser cette méthode pour mélanger un jeu de cartes exprimé sous la forme d'une liste à double lien (la java.util.LinkedListclasse est un exemple). Dans le pseudocode ci-dessous, vous pouvez voir comment l' algorithme Shuffle peut mélanger une liste doublement liée:

 DECLARE RANDOM rnd = new RANDOM DECLARE INTEGER i FOR i = 3 DOWNTO 2 swap(topForward, i - 1, rnd.nextInt(i)) END FOR FUNCTION swap(Node top, int i, int j) DECLARE Node nodei, nodej DECLARE INTEGER k // Locate ith node. Node nodei = top FOR k = 0 TO i - 1 nodei = nodei.next END FOR // Locate jth node. Node nodej = top FOR k = 0 TO i - 1 nodej = nodej.next END FOR // Perform the swap. DECLARE STRING namei = nodei.name DECLARE STRING namej = nodej.name nodej.name = namei nodei.name = namej END FUNCTION END 

L'algorithme Shuffle obtient une source de caractère aléatoire puis parcourt la liste en arrière, du dernier nœud au second. Il échange à plusieurs reprises un nœud sélectionné au hasard (qui est en fait juste le champ de nom) dans la «position actuelle». Les nœuds sont sélectionnés au hasard dans la partie de la liste qui va du premier nœud à la position actuelle, incluse. Notez que cet algorithme est approximativement extrait du void shuffle(List list)code source de.

Le pseudo-code de l'algorithme Shuffle est paresseux car il se concentre uniquement sur la liste à liaison unique qui traverse l'avant. C'est une décision de conception raisonnable, mais nous en payons le prix en termes de complexité temporelle. La complexité temporelle est O ( n 2). Tout d'abord, nous avons la boucle O ( n ) qui appelle swap(). Deuxièmement, à l'intérieur swap(), nous avons les deux boucles O ( n ) séquentielles . Rappelez-vous la règle suivante de la partie 1:

 If f1(n) = O(g(n)) and f2(n) = O(h(n)) then (a) f1(n)+f2(n) = max(O(g(n)), O(h(n))) (b) f1(n)*f2(n) = O(g(n)*h(n)). 

La partie (a) traite des algorithmes séquentiels. Ici, nous avons deux boucles O ( n ). Selon la règle, la complexité temporelle résultante serait O ( n ). La partie (b) traite des algorithmes imbriqués. Dans ce cas, nous avons O ( n ) multiplié par O ( n ), ce qui donne O ( n 2).

Notez que la complexité spatiale de Shuffle est O (1), résultant des variables d'assistance qui sont déclarées.

Exemple d'application: lecture aléatoire dans une liste à double lien

L' Shuffleapplication du listing 2 est une démonstration de l'algorithme Shuffle.

Listing 2. L'algorithme Shuffle en Java

 import java.util.Random; public final class Shuffle { private static class Node { String name; Node next; Node prev; } public static void main(String[] args) { // Build a doubly-linked list. Node topForward = new Node(); topForward.name = "A"; Node temp = new Node(); temp.name = "B"; Node topBackward = new Node(); topBackward.name = "C"; topForward.next = temp; temp.next = topBackward; topBackward.next = null; topBackward.prev = temp; temp.prev = topForward; topForward.prev = null; // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); // Shuffle list. Random rnd = new Random(); for (int i = 3; i > 1; i--) swap(topForward, i - 1, rnd.nextInt(i)); // Dump forward singly-linked list. System.out.print("Forward singly-linked list: "); temp = topForward; while (temp != null) { System.out.print(temp.name); temp = temp.next; } System.out.println(); // Dump backward singly-linked list. System.out.print("Backward singly-linked list: "); temp = topBackward; while (temp != null) { System.out.print(temp.name); temp = temp.prev; } System.out.println(); } public static void swap(Node top, int i, int j) { // Locate ith node. Node nodei = top; for (int k = 0; k < i; k++) nodei = nodei.next; // Locate jth node. Node nodej = top; for (int k = 0; k < j; k++) nodej = nodej.next; String namei = nodei.name; String namej = nodej.name; nodej.name = namei; nodei.name = namej; } } 

Compilez le listing 5 comme suit:

 javac Shuffle.java 

Exécutez l'application résultante comme suit:

 java Shuffle 

Vous devez observer la sortie suivante d'une exécution:

 Forward singly-linked list: ABC Backward singly-linked list: CBA Forward singly-linked list: BAC Backward singly-linked list: CAB 

Listes liées circulaires

Le champ de lien dans le dernier nœud d'une liste à liaison unique contient un lien nul. Cela est également vrai dans une liste à double liaison, qui contient les champs de lien dans les derniers nœuds des listes à liaison simple vers l'avant et vers l'arrière. Supposons au contraire que les derniers nœuds contiennent des liens vers les premiers nœuds. Dans cette situation, vous vous retrouveriez avec une liste circulaire , illustrée à la figure 2.

Les listes à liaison circulaire, également appelées tampons circulaires ou files d'attente circulaires , ont de nombreuses utilisations. Par exemple, ils sont utilisés par les gestionnaires d'interruptions du système d'exploitation pour mettre en mémoire tampon les frappes. Les applications multimédias utilisent des listes à liens circulaires pour mettre en mémoire tampon les données (par exemple, mettre en mémoire tampon les données écrites sur une carte son). Cette technique est également utilisée par la famille d'algorithmes de compression de données sans perte LZ77.

Listes liées et tableaux

Tout au long de cette série sur les structures de données et les algorithmes, nous avons examiné les forces et les faiblesses des différentes structures de données. Puisque nous nous sommes concentrés sur les tableaux et les listes liées, vous pourriez avoir des questions sur ces types en particulier. Quels avantages et inconvénients les listes chaînées et les tableaux offrent-ils? Quand utilisez-vous une liste liée et quand utilisez-vous un tableau? Les structures de données des deux catégories peuvent-elles être intégrées dans une structure de données hybride utile? Je vais essayer de répondre à ces questions ci-dessous.

Les listes liées offrent les avantages suivants par rapport aux tableaux:

  • Ils ne nécessitent pas de mémoire supplémentaire pour prendre en charge l'extension. En revanche, les baies nécessitent une mémoire supplémentaire lorsqu'une extension est nécessaire. (Une fois que tous les éléments contiennent des éléments de données, aucun nouvel élément de données ne peut être ajouté à un tableau.)
  • Ils offrent une insertion / suppression de nœuds plus rapide que les opérations équivalentes basées sur des tableaux. Seuls les liens doivent être mis à jour après avoir identifié la position d'insertion / suppression. Du point de vue d'un tableau, l'insertion d'éléments de données nécessite le déplacement de tous les autres éléments de données pour créer un élément vide. De même, la suppression d'un élément de données existant nécessite le déplacement de tous les autres éléments de données pour supprimer un élément vide. Tout mouvement d'élément de données prend du temps.

En revanche, les tableaux offrent les avantages suivants par rapport aux listes liées:

  • Les éléments de tableau occupent moins de mémoire que les nœuds car les éléments ne nécessitent pas de champs de lien.
  • Les tableaux offrent un accès plus rapide aux éléments de données, via des index basés sur des nombres entiers.