Structures de données et algorithmes en Java, Partie 4: Listes liées individuellement

Comme les tableaux, qui ont été introduits dans la partie 3 de cette série de didacticiels, les listes liées sont une catégorie de structure de données fondamentale sur laquelle des structures de données plus complexes peuvent être basées. Contrairement à une séquence d'éléments, cependant, une liste chaînée est une séquence de nœuds, où chaque nœud est lié au nœud précédent et suivant de la séquence. Rappelez-vous qu'un nœud est un objet créé à partir d'une classe auto-référentielle et qu'une classe auto-référentielle a au moins un champ dont le type de référence est le nom de la classe. Les nœuds d'une liste liée sont liés via une référence de nœud. Voici un exemple:

 class Employee { private int empno; private String name; private double salary; public Employee next; // Other members. }

Dans cet exemple, Employeeest une classe auto-référentielle car son nextchamp est de type Employee. Ce champ est un exemple de champ lien car il peut stocker une référence à un autre objet de sa classe - dans ce cas un autre Employeeobjet.

Ce didacticiel présente les tenants et les aboutissants des listes liées individuellement dans la programmation Java. Vous apprendrez les opérations permettant de créer une liste liée à une seule liaison, d'insérer des nœuds dans une liste à liaison unique, de supprimer des nœuds d'une liste à liaison unique, de concaténer une liste à liaison unique en une autre liste à liaison unique et d'inverser une liste à liaison unique. Nous explorerons également les algorithmes les plus couramment utilisés pour trier les listes liées individuellement, et conclurons avec un exemple illustrant l'algorithme de tri par insertion.

télécharger Obtenez le code Téléchargez les trois exemples d'applications pour cet article. Créé par Jeff Friesen pour JavaWorld.

Qu'est-ce qu'une liste chaînée unique?

Une liste liée unique est une liste liée de nœuds où chaque nœud a un seul champ de lien. Dans cette structure de données, une variable de référence contient une référence au premier nœud (ou supérieur); chaque nœud (à l'exception du dernier nœud ou du nœud inférieur) est lié au suivant; et le champ de lien du dernier nœud contient la référence nulle pour signifier la fin de la liste. Bien que la variable de référence soit généralement nommée top, vous pouvez choisir le nom de votre choix.

La figure 1 présente une liste à lien unique avec trois nœuds.

Vous trouverez ci-dessous le pseudocode pour une liste liée individuellement.

 DECLARE CLASS Node DECLARE STRING name DECLARE Node next END DECLARE DECLARE Node top = NULL 

Nodeest une classe auto-référentielle avec un namechamp de données et un nextchamp de lien. topest une variable de référence de type Nodequi contient une référence au premier Nodeobjet d'une liste liée individuellement. Comme la liste n'existe pas encore, topla valeur initiale de est NULL.

Création d'une liste chaînée unique en Java

Vous créez une liste liée individuellement en attachant un seul Nodeobjet. Le pseudocode suivant crée un Nodeobjet, assigne sa référence à top, initialise son champ de données et l'assigne NULLà son champ de lien:

 top = NEW Node top.name = "A" top.next = NULL 

La figure 2 montre la liste initiale à liaison unique qui émerge de ce pseudo-code.

Cette opération a une complexité temporelle de O (1) - constante. Rappelez-vous que O (1) se prononce "Big Oh of 1." (Voir la partie 1 pour un rappel de la façon dont les mesures de complexité temporelle et spatiale sont utilisées pour évaluer les structures de données.)

Insertion de nœuds dans une liste liée individuellement

L'insertion d'un nœud dans une liste liée individuellement est un peu plus compliquée que la création d'une liste liée individuellement car il y a trois cas à considérer:

  • Insertion avant le premier nœud.
  • Insertion après le dernier nœud.
  • Insertion entre deux nœuds.

Insertion avant le premier nœud

Un nouveau nœud est inséré avant le premier nœud en affectant la référence du nœud supérieur au champ de lien du nouveau nœud et en attribuant la référence du nouveau nœud à la topvariable. Cette opération est illustrée par le pseudocode suivant:

 DECLARE Node temp temp = NEW Node temp.name = "B" temp.next = top top = temp 

La Nodeliste de deux résultants apparaît dans la figure 3.

Cette opération a une complexité temporelle de O (1).

Insertion après le dernier nœud

Un nouveau nœud est inséré après le dernier nœud en attribuant null au champ de lien du nouveau nœud, en parcourant la liste liée individuellement pour trouver le dernier nœud et en attribuant la référence du nouveau nœud au champ de lien du dernier nœud, comme le montre le pseudo-code suivant:

 temp = NEW Node temp.name = "C" temp.next = NULL DECLARE Node temp2 temp2 = top // We assume top (and temp2) are not NULL // because of the previous pseudocode. WHILE temp2.next NE NULL temp2 = temp2.next END WHILE // temp2 now references the last node. temp2.next = temp 

La figure 4 révèle la liste après l'insertion de NodeC après NodeA.

Cette opération a une complexité temporelle de O ( n ) - linéaire. Sa complexité temporelle pourrait être améliorée à O (1) en conservant une référence au dernier nœud. Dans ce cas, il ne serait pas nécessaire de rechercher le dernier nœud.

Insertion entre deux nœuds

L'insertion d'un nœud entre deux nœuds est le cas le plus complexe. Vous insérez un nouveau nœud entre deux nœuds en parcourant la liste pour trouver le nœud qui précède le nouveau nœud, en attribuant la référence dans le champ de lien du nœud trouvé au champ de lien du nouveau nœud et en attribuant la référence du nouveau nœud au lien du nœud trouvé champ. Le pseudocode suivant illustre ces tâches:

 temp = NEW Node temp.name = "D" temp2 = top // We assume that the newly created Node inserts after Node // A and that Node A exists. In the real world, there is no // guarantee that any Node exists, so we would need to check // for temp2 containing NULL in both the WHILE loop's header // and after the WHILE loop completes. WHILE temp2.name NE "A" temp2 = temp2.next END WHILE // temp2 now references Node A. temp.next = temp2.next temp2.next = temp 

La figure 5 présente la liste suite à l'insertion de NodeD entre Nodes A et C.

Cette opération a une complexité temporelle de O ( n ).

Suppression de nœuds d'une liste liée individuellement

La suppression d'un nœud d'une liste liée individuellement est également un peu plus compliquée que la création d'une liste liée individuellement. Cependant, il n'y a que deux cas à considérer:

  • Suppression du premier nœud.
  • Suppression de tout nœud sauf le premier nœud.

Deletion of the first node

Deleting the first node involves assigning the link in the first node's link field to the variable that references the first node, but only when there is a first node:

 IF top NE NULL THEN top = top.next; // Reference the second Node (or NULL when there's only one Node). END IF 

Figure 6 presents before and after views of a list where the first Node has been deleted. Node B disappears and Node A becomes the first Node.

This operation has a time complexity of O(1).

Deletion of any node but the first node

Deleting any node but the first node involves locating the node that precedes the node to be deleted and assigning the reference in the node-to-be-deleted's link field to the preceding node's link field. Consider the following pseudocode:

 IF top NE NULL THEN temp = top WHILE temp.name NE "A" temp = temp.next END WHILE // We assume that temp references Node A. temp.next = temp.next.next // Node D no longer exists. END IF 

Figure 7 presents before and after views of a list where an intermediate Node is deleted. Node D disappears.

This operation has a time complexity of O(n).

Example #1: Create, insert, and delete in a singly linked list

I've created a Java application named SLLDemo that demonstrates how to create, insert, and delete nodes in a singly linked list. Listing 1 presents this application's source code.

Listing 1. Java application demo for singly linked lists (SSLDemo.java, version 1)

 public final class SLLDemo { private static class Node { String name; Node next; } public static void main(String[] args) { Node top = null; // 1. The singly linked list does not exist. top = new Node(); top.name = "A"; top.next = null; dump("Case 1", top); // 2. The singly linked list exists and the node must be inserted // before the first node. Node temp; temp = new Node(); temp.name = "B"; temp.next = top; top = temp; dump("Case 2", top); // 3. The singly linked list exists and the node must be inserted // after the last node. temp = new Node(); temp.name = "C"; temp.next = null; Node temp2; temp2 = top; while (temp2.next != null) temp2 = temp2.next; temp2.next = temp; dump("Case 3", top); // 4. The singly linked list exists and the node must be inserted // between two nodes. temp = new Node(); temp.name = "D"; temp2 = top; while (temp2.name.equals("A") == false) temp2 = temp2.next; temp.next = temp2.next; temp2.next = temp; dump("Case 4", top); // 5. Delete the first node. top = top.next; dump("After first node deletion", top); // 5.1 Restore node B. temp = new Node(); temp.name = "B"; temp.next = top; top = temp; // 6. Delete any node but the first node. temp = top; while (temp.name.equals("A") == false) temp = temp.next; temp.next = temp.next.next; dump("After D node deletion", top); } private static void dump(String msg, Node topNode) { System.out.print(msg + " "); while (topNode != null) { System.out.print(topNode.name + " "); topNode = topNode.next; } System.out.println(); } } 

Compile Listing 1 as follows:

 javac SLLDemo.java 

Run the resulting application as follows:

 java SLLDemo 

You should observe the following output:

 Case 1 A Case 2 B A Case 3 B A C Case 4 B A D C After first node deletion A D C After D node deletion B A C 

Concatenating singly linked lists

You might occasionally need to concatenate a singly linked list to another singly linked list. For example, suppose you have a list of words that start with letters A through M and another list of words starting with letters N through Z, and you want to combine these lists into a single list. The following pseudocode describes an algorithm for concatenating one singly linked list to another:

 DECLARE Node top1 = NULL DECLARE Node top2 = NULL // Assume code that creates top1-referenced singly linked list. // Assume code that creates top2-referenced singly linked list. // Concatenate top2-referenced list to top1-referenced list. IF top1 EQ NULL top1 = top2 END END IF // Locate final Node in top1-referenced list. DECLARE Node temp = top1 WHILE temp.next NE NULL temp = temp.next END WHILE // Concatenate top2 to top1. temp.next = top2 END 

In the trivial case, there is no top1-referenced list, and so top1 is assigned top2's value, which would be NULL if there was no top2-referenced list.

This operation has a time complexity of O(1) in the trivial case and a time complexity of O(n) otherwise. However, if you maintain a reference to the last node, there's no need to search the list for this node; the time complexity changes to O(1).

Inverting a singly linked list

Another useful operation on a singly linked list is inversion, which reverses the list's links to let you traverse its nodes in the opposite direction. The following pseudocode reverses the top1-referenced list's links:

 DECLARE Node p = top1 // Top of original singly linked list. DECLARE Node q = NULL // Top of reversed singly linked list. DECLARE Node r // Temporary Node reference variable. WHILE p NE NULL // For each Node in original singly linked list ... r = q // Save future successor Node's reference. q = p // Reference future predecessor Node. p = p.next // Reference next Node in original singly linked list. q.next = r // Link future predecessor Node to future successor Node. END WHILE top1 = q // Make top1 reference first Node in reversed singly linked list. END 

This operation has a time complexity of O(n).

Example #2: Concatenating and inverting a singly linked list

J'ai créé une deuxième version de l' SLLDemoapplication Java qui démontre la concaténation et l'inversion. Le listing 2 présente le code source de cette application.