La structure de données de la liste chaînée
Avec la leçon sur les tableaux dans les livres, allons-y et passons à l'un de ses proches parents :la liste chaînée. En ce qui concerne les structures de données, le plus grand rival du tableau est la liste chaînée. C'est parce qu'à un niveau élevé, ils fonctionnent presque de manière indiscernable. Après tout, ce ne sont que des listes unidimensionnelles. Cependant, sous le capot, ils ont des implémentations très différentes. Dans cette leçon, nous verrons exactement quelles sont ces différences et comment ces différences améliorent les performances.
Qu'est-ce qu'une liste liée ?
Comme un tableau, une liste chaînée est une liste unidimensionnelle d'éléments. La principale différence avec une liste chaînée est qu'elle ne nous oblige pas à définir une taille à l'avance. C'est parce qu'une liste liée n'est pas stockés dans des espaces contigus en mémoire. Au lieu de cela, chaque élément est stocké dans l'espace libre au moment de la création. Ce nouvel élément est alors lié à l'élément précédent via une référence d'objet. Ceci est accompli en utilisant une structure connue sous le nom de nœud.
Un nœud est un peu comme un wagon couvert dans un train. Chaque wagon couvert contient une cargaison qui est liée aux wagons couverts qui l'entourent. Dans le code, un nœud peut être défini comme suit :
public class Node {
private Node next;
private int payload;
public Node(int payload, Node next) {
this.payload = payload;
this.next = next;
}
} En règle générale, notre charge utile accepterait n'importe quel type de données, mais les types génériques sortent un peu du cadre de cette leçon. Au lieu de cela, restons-en aux nombres entiers. Ici, nous avons un nœud qui stocke un entier et des liens vers un autre nœud. Comme indiqué précédemment, la beauté de cette structure est que nous n'avons pas à nous soucier d'une taille de liste maximale. Au lieu de cela, nous pouvons continuellement ajouter des nœuds selon les besoins. Finalement, nous aboutirions à une structure qui pourrait ressembler à ceci :
Dans cet exemple, nous avons une liste qui contient trois nœuds. Le côté gauche du nœud stocke la charge utile tandis que le côté droit du nœud stocke la référence au nœud suivant.
En remarque, les listes liées peuvent également être doublement liées. En d'autres termes, chaque nœud aurait une référence au nœud suivant et au nœud précédent. La principale différence ici est que nous pourrions parcourir la liste de chaque côté.
Propriétés des listes liées
En raison de sa structure, la liste chaînée a des propriétés assez intéressantes. D'une part, nous n'avons pas l'avantage d'un accès aléatoire comme les tableaux. Si nous voulons le troisième élément d'une liste, nous devons parcourir la liste jusqu'à ce nœud. C'est parce que nous n'avons accès qu'au premier nœud d'une liste chaînée.
Cependant, nous bénéficions de quelques avantages clés. D'une part, une liste chaînée nous permet de développer notre ensemble de données pour toujours. Nous n'avons plus de restriction de taille. Au lieu de cela, nous pouvons simplement ajouter un nouveau nœud chaque fois que nous voulons faire un ajout. De même, les suppressions sont extrêmement faciles. Nous n'avons pas à déplacer les éléments. On refait simplement les liens pour éliminer l'élément que l'on souhaite supprimer. Ensuite, nous laissons le ramasseur de déchets nettoyer après nous.
Les deux avantages ci-dessus impliquent également que les listes chaînées sont compatibles avec la mémoire. Bien que chaque nœud nécessite de l'espace supplémentaire pour la référence de nœud suivante, nous n'utilisons jamais plus d'espace que nécessaire. Cependant, la structure d'une liste chaînée a tendance à stocker la localité du cache - la vitesse à laquelle nous pouvons récupérer nos données de la mémoire – car le processeur est incapable de prédire la prochaine adresse mémoire pendant le parcours.
Applications des listes liées
La puissance d'une liste chaînée vient de sa taille dynamique alors que son point crucial est son manque d'accès aléatoire. Par conséquent, les listes chaînées sont utiles lorsque nous ne savons pas quelle sera la taille de notre ensemble de données. Malheureusement, il est assez rare de voir une liste chaînée dans le code de production. Comme nous le verrons plus tard, Java prend en charge une structure de données souvent plus polyvalente et offrant de meilleures performances :la ArrayList. Cela dit, il est toujours important de comprendre le fonctionnement des listes chaînées, car elles servent généralement de base à des structures de données plus complexes telles que des piles, des files d'attente et des tables de hachage.
Syntaxe de la liste chaînée Java
Bien que Java prenne en charge les listes liées dans sa bibliothèque de collections, nous allons continuer et implémenter une liste liée ici dans le code. De cette façon, nous pouvons voir exactement comment ils fonctionnent sous le capot.
Définition de classe
Comme indiqué précédemment, un nœud est implémenté comme suit :
public class Node {
private Node next;
private int payload;
public Node(int payload, Node next) {
this.payload = payload;
this.next = next;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public int getPayload() {
return payload;
}
} Ici, nous avons défini quelques getters et setters de base pour un nœud. Maintenant, si nous voulons définir une classe enveloppant ces nœuds, nous pouvons également le faire :
public class LinkedList {
private Node head;
public Node getHead() {
return head;
}
public void addToFront(int value) {
head = new Node(value, head);
}
public Node removeFromFront() {
Node remove = head;
head = head.getNext();
return remove;
}
public Node find(int value) {
Node current = head;
while (current != null) {
if (current.getPayload == value) {
return current;
}
current = current.getNext();
}
return null;
}
} Ce wrapper de base nous permet d'obtenir le début de la liste, d'ajouter des éléments au premier plan, de supprimer des éléments du premier plan et de rechercher des éléments en fonction d'une certaine valeur. Des fonctionnalités supplémentaires peuvent être ajoutées comme nous le verrons dans les sections suivantes.
Indexation
Pour obtenir un élément particulier à un index, nous devons parcourir la liste jusqu'à cet index. Pour cette raison, l'indexation n'est pas vraiment une bonne idée. Cependant, l'extrait de code suivant y parviendra :
public int getElement(int index) {
Node current = head;
if (current == null) {
throw new IndexOutOfBoundsException();
}
int i = 0;
while (current.getNext() != null && i < index) {
current = current.getNext();
i++;
}
if (i == index) {
return current.getPayload();
} else {
throw new IndexOutOfBoundsException();
}
} Comme indiqué précédemment, nous ne pensons généralement pas aux listes chaînées en termes d'indices. Au lieu de cela, nous suivons simplement le nœud actuel pendant la traversée.
Traversée
Avec une liste chaînée, nous n'avons pas besoin de connaître la taille de la liste pour arriver à la fin. Cependant, la méthode suivante nous donnera la taille de notre liste :
public int getSize() {
Node current = head;
int size = 0;
if (head == null) {
return 0;
}
while (current != null) {
size++;
current = current.getNext();
}
return size;
} Il s'agit d'une distinction importante car les nouveaux développeurs essaieront souvent de parcourir une liste chaînée comme s'il s'agissait d'un tableau. Cette méthode getSize conduira très rapidement un parcours simple de O(N) à O(N²). La bibliothèque de listes chaînées intégrée tient compte de ce problème en gardant une trace dynamique de la taille. Au fur et à mesure que des éléments sont ajoutés et supprimés, le compteur global est ajusté.
Insertion
L'insertion générique est un processus O(1). C'est parce que l'insertion elle-même nécessite simplement une refonte des pointeurs. Le parcours est considéré comme une opération distincte que nous avons déjà qualifiée de O(N).
public void insertAfter(Node n, int value) {
n.setNext(new Node(value, n.getNext()));
} Pendant ce temps, la suppression est fondamentalement le même processus, sauf que les pointeurs sont redirigés pour ignorer le nœud supprimé. La suppression est également un processus O(1).
Résumé
C'est tout pour les listes liées! Comme d'habitude, voici une ventilation des opérations typiques et de leurs estimations Big O.
| Algorithme | Durée d'exécution |
|---|---|
| Accès | O(N) |
| Insérer | O(1) |
| Supprimer | O(1) |
| Rechercher | O(N) |
À partir de ce moment, nous commencerons à examiner des structures de données plus avancées telles que les piles, les files d'attente, les arbres et les tables de hachage. Soyez pompé! 😀
