Implémentation Java Circular Linked List

1. Introduction

Dans ce didacticiel, nous examinerons l'implémentation d'une liste chaînée circulaire en Java.

2. Liste circulaire liée

Une liste liée circulaire est une variante d'une liste liée dans laquelle le dernier nœud pointe vers le premier nœud, complétant un cercle complet de nœuds . En d'autres termes, cette variante de la liste chaînée n'a pas d' élément nul à la fin.

Avec ce simple changement, nous bénéficions de certains avantages:

  • Tout nœud de la liste liée circulaire peut être un point de départ
  • Par conséquent, toute la liste peut être parcourue à partir de n'importe quel nœud
  • Étant donné que le dernier nœud de la liste liée circulaire a le pointeur vers le premier nœud, il est facile d'effectuer des opérations de mise en file d'attente et de retrait de la file d'attente

Dans l'ensemble, cela est très utile dans la mise en œuvre de la structure de données de file d'attente.

En termes de performances, c'est la même chose que les autres implémentations de liste chaînée, sauf pour une chose: le passage du dernier nœud au nœud principal peut être effectué en temps constant . Avec les listes chaînées conventionnelles, il s'agit d'une opération linéaire.

3. Implémentation en Java

Commençons par créer une classe Node auxiliaire qui stockera les valeurs int et un pointeur vers le nœud suivant :

class Node { int value; Node nextNode; public Node(int value) { this.value = value; } }

Créons maintenant les premier et dernier nœuds de la liste chaînée circulaire, généralement appelés tête et queue:

public class CircularLinkedList { private Node head = null; private Node tail = null; // .... }

Dans les sous-sections suivantes, nous examinerons les opérations les plus courantes que nous pouvons effectuer sur une liste liée circulaire.

3.1. Insertion d'éléments

La première opération que nous allons couvrir est l'insertion de nouveaux nœuds. Lors de l'insertion d'un nouvel élément, nous devrons gérer deux cas:

  • La tête noeud est nulle , qui est qu'il n'y a pas d' éléments déjà ajoutés. Dans ce cas, nous allons créer le nouveau nœud que nous ajoutons à la fois en tête et en queue de la liste car il n'y a qu'un seul nœud
  • La tête noeud est non nul , autrement dit, il y a un ou plusieurs éléments déjà ajoutés à la liste. Dans ce cas, la queue existante doit pointer vers le nouveau nœud et le nœud nouvellement ajouté deviendra la queue

Dans les deux cas ci-dessus, le nextNode pour la queue pointera vers la tête

Créons une méthode addNode qui prend la valeur à insérer comme paramètre:

public void addNode(int value) { Node newNode = new Node(value); if (head == null) { head = newNode; } else { tail.nextNode = newNode; } tail = newNode; tail.nextNode = head; }

Nous pouvons maintenant ajouter quelques nombres à notre liste chaînée circulaire:

private CircularLinkedList createCircularLinkedList() { CircularLinkedList cll = new CircularLinkedList(); cll.addNode(13); cll.addNode(7); cll.addNode(24); cll.addNode(1); cll.addNode(8); cll.addNode(37); cll.addNode(46); return cll; }

3.2. Trouver un élément

La prochaine opération que nous examinerons consiste à rechercher si un élément est présent dans la liste.

Pour cela, nous allons fixer un nœud dans la liste (généralement la tête ) en tant que nœud actuel et parcourir la liste entière en utilisant le nœud suivant de ce nœud , jusqu'à ce que nous trouvions l'élément requis.

Ajoutons une nouvelle méthode containsNode qui prend la searchValue comme paramètre:

public boolean containsNode(int searchValue) { Node currentNode = head; if (head == null) { return false; } else { do { if (currentNode.value == searchValue) { return true; } currentNode = currentNode.nextNode; } while (currentNode != head); return false; } }

Maintenant, ajoutons quelques tests pour vérifier que la liste créée ci-dessus contient les éléments que nous avons ajoutés et pas de nouveaux:

@Test public void givenACircularLinkedList_WhenAddingElements_ThenListContainsThoseElements() { CircularLinkedList cll = createCircularLinkedList(); assertTrue(cll.containsNode(8)); assertTrue(cll.containsNode(37)); } @Test public void givenACircularLinkedList_WhenLookingForNonExistingElement_ThenReturnsFalse() { CircularLinkedList cll = createCircularLinkedList(); assertFalse(cll.containsNode(11)); }

3.3. Supprimer un élément

Ensuite, nous examinerons l'opération de suppression. Semblable à l'insertion, nous avons quelques cas (à l'exclusion du cas où la liste elle-même est vide) que nous devons examiner.

  • L'élément à supprimer est la tête elle - même . Dans ce cas, nous devons mettre à jour la tête en tant que nœud suivant de la tête actuelle , et le nœud suivant de la queue en tant que nouvelle tête
  • L'élément à supprimer est tout élément autre que la tête . Dans ce cas, il suffit de mettre à jour le nœud suivant du nœud précédent en tant que nœud suivant du nœud à supprimer

Nous allons maintenant ajouter une nouvelle méthode deleteNode qui prend le valueToDelete comme paramètre:

public void deleteNode(int valueToDelete) { Node currentNode = head; if (head != null) { if (currentNode.value == valueToDelete) { head = head.nextNode; tail.nextNode = head; } else { do { Node nextNode = currentNode.nextNode; if (nextNode.value == valueToDelete) { currentNode.nextNode = nextNode.nextNode; break; } currentNode = currentNode.nextNode; } while (currentNode != head); } } }

Ajoutons maintenant un test simple pour vérifier que la suppression fonctionne comme prévu pour tous les cas:

@Test public void givenACircularLinkedList_WhenDeletingElements_ThenListDoesNotContainThoseElements() { CircularLinkedList cll = createCircularLinkedList(); assertTrue(cll.containsNode(13)); cll.deleteNode(13); assertFalse(cll.containsNode(13)); assertTrue(cll.containsNode(1)); cll.deleteNode(1); assertFalse(cll.containsNode(1)); assertTrue(cll.containsNode(46)); cll.deleteNode(46); assertFalse(cll.containsNode(46)); }

3.4. Traverser la liste

Nous allons jeter un oeil à la traversée de notre liste chaînée circulaire dans cette dernière section . Similaire aux opérations de recherche et de suppression, pour la traversée, nous fixons le currentNode en tant que head et parcourons la liste entière en utilisant le nextNode de ce nœud.

Ajoutons une nouvelle méthode traverseList qui imprime les éléments ajoutés à la liste:

public void traverseList() { Node currentNode = head; if (head != null) { do { LOGGER.info(currentNode.value + " "); currentNode = currentNode.nextNode; } while (currentNode != head); } } 

Comme nous pouvons le voir, dans l'exemple ci-dessus, lors du parcours, nous imprimons simplement la valeur de chacun des nœuds, jusqu'à ce que nous revenions au nœud principal.

4. Conclusion

Dans ce didacticiel, nous avons vu comment implémenter une liste chaînée circulaire en Java et exploré certaines des opérations les plus courantes.

Tout d'abord, nous avons appris ce qu'est exactement une liste chaînée circulaire comprenant certaines des caractéristiques et des différences les plus courantes avec une liste chaînée conventionnelle. Ensuite, nous avons vu comment insérer, rechercher, supprimer et parcourir des éléments dans notre implémentation de liste liée circulaire.

Comme d'habitude, tous les exemples utilisés dans cet article sont disponibles à l'adresse over sur GitHub.