doubly linked list java implementation code examples
Ce didacticiel explique la liste doublement liée en Java ainsi que l'implémentation de la liste double liée, le code Java de la liste circulaire doublement liée et des exemples:
La liste chaînée est une représentation séquentielle des éléments. Chaque élément de la liste liée est appelé un «nœud». Un type de liste chaînée est appelé «Liste chaînée unique».
En cela, chaque nœud contient une partie de données qui stocke les données réelles et une seconde partie qui stocke le pointeur vers le nœud suivant dans la liste. Nous avons déjà appris les détails de la liste chaînée unique dans notre tutoriel précédent.
=> Consultez TOUS les didacticiels Java ici.
Ce que vous apprendrez:
Liste doublement liée en Java
Une liste chaînée a une autre variante appelée «liste double chaînée». Une liste doublement liée a un pointeur supplémentaire connu sous le nom de pointeur précédent dans son nœud en dehors de la partie données et le pointeur suivant comme dans la liste liée individuellement.
Un nœud de la liste doublement liée ressemble à ceci:
application gratuite pour planifier des publications instagram
Ici, «Prev» et «Next» sont respectivement des pointeurs vers les éléments précédent et suivant du nœud. Les «données» sont l’élément réel qui est stocké dans le nœud.
La figure suivante montre une liste doublement liée.
Le diagramme ci-dessus montre la liste doublement liée. Il y a quatre nœuds dans cette liste. Comme vous pouvez le voir, le pointeur précédent du premier nœud et le pointeur suivant du dernier nœud sont définis sur null. Le pointeur précédent défini sur null indique qu'il s'agit du premier nœud de la liste doublement liée tandis que le pointeur suivant défini sur null indique que le nœud est le dernier nœud.
Avantages
- Comme chaque nœud a des pointeurs pointant vers les nœuds précédent et suivant, la liste doublement liée peut être parcourue facilement dans le sens avant et arrière.
- Vous pouvez ajouter rapidement le nouveau nœud simplement en changeant les pointeurs.
- De même, pour l'opération de suppression puisque nous avons des pointeurs précédents et suivants, la suppression est plus facile et nous n'avons pas besoin de parcourir toute la liste pour trouver le nœud précédent comme dans le cas de la liste liée individuellement.
Désavantages
- Puisqu'il y a un pointeur supplémentaire dans la liste doublement liée, c'est-à-dire le pointeur précédent, un espace mémoire supplémentaire est nécessaire pour stocker ce pointeur avec le pointeur et l'élément de données suivants.
- Toutes les opérations comme l'ajout, la suppression, etc. nécessitent que les pointeurs précédents et suivants soient manipulés, ce qui impose une surcharge opérationnelle.
Implémentation en Java
L'implémentation de la liste doublement liée en Java comprend la création d'une classe de liste doublement liée, la classe de nœuds et l'ajout de nœuds à la liste doublement liée
L'ajout de nouveaux nœuds se fait généralement à la fin de la liste. Le diagramme ci-dessous montre l'ajout du nouveau nœud à la fin de la liste doublement liée.
Comme le montre le diagramme ci-dessus, pour ajouter un nouveau nœud à la fin de la liste, le pointeur suivant du dernier nœud pointe maintenant vers le nouveau nœud au lieu de null. Le pointeur précédent du nouveau nœud pointe vers le dernier nœud. De plus, le pointeur suivant du nouveau nœud pointe sur null, ce qui en fait un nouveau dernier nœud.
Le programme ci-dessous montre l'implémentation Java d'une liste à double lien avec l'ajout de nouveaux nœuds à la fin de la liste.
class DoublyLinkedList { //A node class for doubly linked list class Node{ int item; Node previous; Node next; public Node(int item) { this.item = item; } } //Initially, heade and tail is set to null Node head, tail = null; //add a node to the list public void addNode(int item) { //Create a new node Node newNode = new Node(item); //if list is empty, head and tail points to newNode if(head == null) { head = tail = newNode; //head's previous will be null head.previous = null; //tail's next will be null tail.next = null; } else { //add newNode to the end of list. tail->next set to newNode tail.next = newNode; //newNode->previous set to tail newNode.previous = tail; //newNode becomes new tail tail = newNode; //tail's next point to null tail.next = null; } } //print all the nodes of doubly linked list public void printNodes() { //Node current will point to head Node current = head; if(head == null) { System.out.println('Doubly linked list is empty'); return; } System.out.println('Nodes of doubly linked list: '); while(current != null) { //Print each node and then go to next. System.out.print(current.item + ' '); current = current.next; } } } class Main{ public static void main(String[] args) { //create a DoublyLinkedList object DoublyLinkedList dl_List = new DoublyLinkedList(); //Add nodes to the list dl_List.addNode(10); dl_List.addNode(20); dl_List.addNode(30); dl_List.addNode(40); dl_List.addNode(50); //print the nodes of DoublyLinkedList dl_List.printNodes(); } }
Production:
Nœuds de la liste doublement liée:
10 20 30 40 50
Outre l'ajout d'un nouveau nœud à la fin de la liste, vous pouvez également ajouter un nouveau nœud au début de la liste ou entre la liste. Nous laissons cette implémentation au lecteur afin que les lecteurs puissent mieux comprendre les opérations.
Liste circulaire doublement liée en Java
Une liste circulaire doublement liée est l'une des structures complexes. Dans cette liste, le dernier nœud de la liste doublement liée contient l'adresse du premier nœud et le premier nœud contient l'adresse du dernier nœud. Ainsi, dans une liste circulaire doublement liée, il y a un cycle et aucun des pointeurs de nœud n'est mis à zéro.
Le diagramme suivant montre la liste circulaire doublement liée.
Comme le montre le diagramme ci-dessus, le pointeur suivant du dernier nœud pointe vers le premier nœud. Le pointeur précédent du premier nœud pointe vers le dernier nœud.
Les listes circulaires à double lien ont de larges applications dans l'industrie du logiciel. Une de ces applications est l'application musicale qui a une liste de lecture. Dans la liste de lecture, lorsque vous avez fini de jouer toutes les chansons, puis à la fin de la dernière chanson, vous revenez automatiquement à la première chanson. Cela se fait à l'aide de listes circulaires.
Avantages d'une liste circulaire double liée:
- La liste circulaire doublement liée peut être parcourue de la tête à la queue ou de la queue à la tête.
- Passer de la tête à la queue ou de la queue à la tête est efficace et ne prend qu'un temps constant O (1).
- Il peut être utilisé pour implémenter des structures de données avancées, y compris le tas de Fibonacci.
Désavantages:
- Comme chaque nœud a besoin de faire de la place pour le pointeur précédent, une mémoire supplémentaire est nécessaire.
- Nous devons traiter de nombreux pointeurs tout en effectuant des opérations sur une liste circulaire doublement liée. Si les pointeurs ne sont pas gérés correctement, l'implémentation peut être interrompue.
Le programme Java ci-dessous montre l'implémentation de la liste circulaire doublement liée.
import java.util.*; class Main{ static Node head; // Doubly linked list node definition static class Node{ int data; Node next; Node prev; }; // Function to insert node in the list static void addNode(int value) { // List is empty so create a single node furst if (head == null) { Node new_node = new Node(); new_node.data = value; new_node.next = new_node.prev = new_node; head = new_node; return; } // find last node in the list if list is not empty Node last = (head).prev; //previous of head is the last node // create a new node Node new_node = new Node(); new_node.data = value; // next of new_node will point to head since list is circular new_node.next = head; // similarly previous of head will be new_node (head).prev = new_node; // change new_node=>prev to last new_node.prev = last; // Make new node next of old last last.next = new_node; } static void printNodes() { Node temp = head; //traverse in forward direction starting from head to print the list while (temp.next != head) { System.out.printf('%d ', temp.data); temp = temp.next; } System.out.printf('%d ', temp.data); //traverse in backward direction starting from last node System.out.printf('
Circular doubly linked list travesed backward:
'); Node last = head.prev; temp = last; while (temp.prev != last) { System.out.printf('%d ', temp.data); temp = temp.prev; } System.out.printf('%d ', temp.data); } public static void main(String[] args) { //the empty list Node l_list = null; // add nodes to the list addNode(40); addNode(50); addNode(60); addNode(70); addNode(80); //print the list System.out.printf('Circular doubly linked list: '); printNodes(); } }
Production:
Liste circulaire doublement chaînée: 40 50 60 70 80
Liste circulaire à double chaînette parcourue en arrière:
80 70 60 50 40
Dans le programme ci-dessus, nous avons ajouté le nœud à la fin de la liste. Comme la liste est circulaire, lorsque le nouveau nœud est ajouté, le pointeur suivant du nouveau nœud pointera vers le premier nœud et le pointeur précédent du premier nœud pointera vers le nouveau nœud.
De même, le pointeur précédent du nouveau nœud pointera vers le dernier nœud actuel qui deviendra maintenant l'avant-dernier nœud. Nous laissons la mise en œuvre de l'ajout d'un nouveau nœud au début de la liste et entre les nœuds aux lecteurs.
Questions fréquemment posées
Q # 1) La liste doublement liée peut-elle être circulaire?
Répondre: Oui. C'est une structure de données plus complexe. Dans une liste circulaire doublement liée, le pointeur précédent du premier nœud contient l'adresse du dernier nœud et le pointeur suivant du dernier nœud contient l'adresse du premier nœud.
Q # 2) Comment créer une liste liée doublement circulaire?
Répondre: Vous pouvez créer une classe pour une liste chaînée doublement circulaire. À l'intérieur de cette classe, il y aura une classe statique pour représenter le nœud. Chaque nœud contiendra deux pointeurs - précédent et suivant et un élément de données. Ensuite, vous pouvez avoir des opérations pour ajouter des nœuds à la liste et parcourir la liste.
Q # 3) La liste doublement liée est-elle linéaire ou circulaire?
Répondre: La liste doublement chaînée est une structure linéaire mais une liste circulaire doublement chaînée dont la queue pointe vers la tête et la tête pointe vers la queue. C'est donc une liste circulaire.
Q # 4) Quelle est la différence entre la liste double chaînée et la liste chaînée circulaire?
Répondre: Une liste doublement liée a des nœuds qui conservent des informations sur ses nœuds précédents et suivants en utilisant respectivement les pointeurs précédent et suivant. De plus, le pointeur précédent du premier nœud et le pointeur suivant du dernier nœud sont définis sur null dans la liste doublement liée.
Dans la liste liée circulaire, il n'y a pas de nœuds de début ou de fin et les nœuds forment un cycle. En outre, aucun des pointeurs n'est défini sur null dans la liste liée circulaire.
Q # 5) Quels sont les avantages d'une liste doublement liée?
Répondre: Les avantages de la liste doublement liée sont:
outils d'optimisation PC gratuits windows 10
- Il peut être parcouru aussi bien en avant qu'en arrière.
- L'opération d'insertion est plus facile car nous n'avons pas besoin de parcourir toute la liste pour trouver l'élément précédent.
- La suppression est efficace car nous savons que les nœuds précédents et suivants et la manipulation sont plus faciles.
Conclusion
Dans ce didacticiel, nous avons discuté en détail de la liste double chaînée en Java. Une liste doublement liée est une structure complexe dans laquelle chaque nœud contient des pointeurs vers ses nœuds précédents et suivants. La gestion de ces liens est parfois difficile et peut conduire à une panne de code si elle n'est pas gérée correctement.
Dans l'ensemble, les opérations d'une liste à double lien sont plus efficaces car nous pouvons gagner du temps pour parcourir la liste car nous avons les pointeurs précédent et suivant.
La liste circulaire doublement liée est plus complexe et ils forment un motif circulaire avec le pointeur précédent du premier nœud pointant vers le dernier nœud et le pointeur suivant du dernier nœud pointant vers le premier nœud. Dans ce cas également, les opérations sont efficaces.
Avec cela, nous en avons terminé avec la liste chaînée en Java. Restez à l'écoute pour de nombreux autres didacticiels sur les techniques de recherche et de tri en Java.
=> Visitez ici pour la série exclusive de didacticiels de formation Java.
lecture recommandée
- Structure de données de liste doublement liée en C ++ avec illustration
- Algorithme de recherche binaire en Java - Implémentation et exemples
- Liste Java - Comment créer, initialiser et utiliser une liste en Java
- Tutoriel sur l'interface Java et la classe abstraite avec des exemples
- Méthodes de liste Java - Trier la liste, contient, ajouter une liste, supprimer une liste
- Tri par insertion en Java - Algorithme de tri par insertion et exemples
- Tutoriel JAVA pour les débutants: plus de 100 tutoriels vidéo Java pratiques
- Tri à bulles en Java - Algorithmes de tri Java et exemples de code