Liste Java doublement liée

Java Doublement Linked List est un type de liste liée où chaque nœud, en dehors du stockage des données, possède deux liens. Le premier lien pointe vers le nœud précédent et l’autre lien pointe vers le nœud suivant de la liste. La liste doublement chaînée, également abrégée en DLL, ressemble beaucoup à une liste chaînée unique. Les deux listes liées contiennent un pointeur vers le nœud suivant et un champ de données pour représenter la valeur réelle à stocker dans le nœud. La principale différence est que la DLL contient un pointeur vers le nœud précédent dans la liste, c'est-à-dire que les nœuds de la DLL connaissent à la fois le nœud précédent et le nœud suivant. Dans cet article, nous examinerons la liste doublement liée en Java, explorerons quelques exemples et connaîtrons son implémentation.

PUBLICITÉ Cours populaire dans cette catégorie MAÎTRISÉE JAVA - Spécialisation | 78 séries de cours | 15 tests simulés

Commencez votre cours de développement de logiciels libres

Développement Web, langages de programmation, tests de logiciels et autres

Syntaxe

Il n'y a pas de syntaxe particulière pour la liste doublement chaînée en Java, mais nous verrons Comment déclarer la liste doublement chaînée en Java. Avant d'examiner une déclaration de liste doublement chaînée, voyons le concept derrière la mise en œuvre de la liste doublement chaînée.

Nœud dans la liste à double lien :

Prev Node

Data

Next Node

Nœud précédent Données Nœud suivant

Ici, Prev Node et Next Node sont respectivement des pointeurs vers les éléments précédents et suivants du nœud. « Données » est l'élément réel où les données sont stockées.

Vous trouverez ci-dessous quelques-uns des termes importants que nous devons comprendre,

• Précédent : Chaque lien de la liste chaînée a un lien vers le nœud précédent appelé Précédent.
• Suivant : Chaque lien de la liste chaînée a un lien vers le nœud suivant appelé Suivant
• Lien : Chaque lien d'une liste chaînée peut stocker des données, appelées élément.
• Lien Liste : Elle contient le lien de connexion au premier lien et au dernier lien.

Algorithme

• Définissez une classe Node qui représente un nœud dans la liste chaînée. Il doit avoir 3 propriétés, à savoir le nœud précédent, les données et le nœud suivant
• Définissez une autre classe pour créer une liste doublement liée avec deux nœuds, c'est-à-dire tête et queue. Initialement, ces valeurs seront nulles.
• Créer une fonction pour ajouter des nœuds dans la liste chaînée,
• Il vérifiera d'abord si la tête est nulle, puis insérera le nœud comme tête.
• La tête et la queue pointeront alors vers le nouveau nœud.
• Si la queue n'est pas nulle, le nouveau nœud sera inséré en fin de liste de telle manière que le pointeur du nouveau nœud pointe vers la queue.
• Ainsi, le nouveau nœud deviendra une nouvelle queue.

Déclaration de nœud pour une liste doublement liée en Java :

class Node {
public int data;
public Node prev;
public Node next;
public void displayData() {
//content of the function}
}

Comme nous pouvons le voir, il existe une déclaration supplémentaire ou une référence (Node prev) dans le cas d'une liste doublement chaînée.

Opérations de base de la liste doublement chaînée

Vous trouverez ci-dessous les opérations de base disponibles pour la liste doublement liée,

• Insertion : Ajout d'un élément en début de liste chaînée
• Suppression :Suppression d'un élément en début de liste chaînée
• Insérer après : Ajout d'un élément après un élément de liste chaînée
• Insérer le dernier : Ajout d'un élément à la fin de la liste chaînée
• Supprimer le dernier : Supprimer un élément à la fin de la liste chaînée
• Supprimer : Supprimer un élément de la liste chaînée à l'aide d'une clé.
• Afficher vers l'avant : Afficher la liste complète de manière avant
• Afficher en arrière : Afficher la liste complète en arrière

Exemples de liste Java doublement liée

Vous trouverez ci-dessous les différents exemples de liste doublement chaînée Java :

Exemple n°1 : Déclaration de nœud et ajout de nœuds à afficher

Code :

public class DLL {
class Node{
public int data;
public Node prevNode;
public Node nextNode;
public Node(int data) {
this.data = data;
}
}
Node headNode, tailNode = null;
public void addDLLNode(int data) {
Node newDLLNode = new Node(data);
if(headNode == null) {
headNode = tailNode = newDLLNode;
headNode.prevNode = null;
tailNode.nextNode = null;
}
else {
tailNode.nextNode = newDLLNode;
newDLLNode.prevNode = tailNode;
tailNode = newDLLNode;
tailNode.nextNode = null;
}
}
public void displayNode() {
Node currentNode = headNode;
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
System.out.println("Nodes in Doubly Linked List: ");
while(currentNode != null) {
System.out.print(currentNode.data + " ");
currentNode = currentNode.nextNode;
}
}
public static void main(String[] args) {
DLL dLinkedList = new DLL();
dLinkedList.addDLLNode(9);
dLinkedList.addDLLNode(7);
dLinkedList.addDLLNode(5);
dLinkedList.addDLLNode(3);
dLinkedList.addDLLNode(1);
dLinkedList.addDLLNode(3);
dLinkedList.addDLLNode(5);
dLinkedList.addDLLNode(7);
dLinkedList.displayNode();
}
}

Sortie :

Nous créons donc ici une classe Node pour déclarer une liste doublement liée et afficher les valeurs de la DLL.

Exemple n°2 : Supprimer au début de la liste chaînée et afficher

Code :

public class DLL {
class Node{
public int data;
public Node prevNode;
public Node nextNode;
public Node(int data) {
this.data = data;
}
}
public void displayNode() {
Node tempNode = headNode;
while (tempNode != null) {
System.out.print(tempNode.data + "–>");
tempNode = tempNode.nextNode;
}
System.out.println("END");
}
Node headNode, tailNode = null;
public void addNode(int data) {
Node newNode = new Node(data);
if(headNode == null) {
headNode = tailNode = newNode;
headNode.prevNode = null;
tailNode.nextNode = null;
}
else {
tailNode.nextNode = newNode;
newNode.prevNode = tailNode;
tailNode = newNode;
tailNode.nextNode = null;
}
}
public void deleteInitialNode() {
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
else {
if(headNode != tailNode) {
headNode = headNode.nextNode;
}
else {
headNode = tailNode = null;
}
}
}
void printNode() {
Node currNode = headNode;
if(headNode == null) {
System.out.println("Doubly Linked List is empty");
return;
}
while(currNode != null)
{
System.out.print(currNode.data + " ");
currNode = currNode.nextNode;
}
System.out.println();
}
public static void main(String[] args) {
DLL doublyLL = new DLL();
doublyLL.addNode(3);
doublyLL.addNode(5);
doublyLL.addNode(7);
doublyLL.addNode(9);
doublyLL.addNode(11);
System.out.println("Doubly linked list: ");
doublyLL.printNode();
doublyLL.addNode(15);
doublyLL.addNode(17);
doublyLL.addNode(19);
doublyLL.deleteInitialNode();
doublyLL.addNode(21);
System.out.println("Doubly Linked List after deleting at the beginning: ");
doublyLL.printNode();
}
}

Sortie :

Donc ici, le nœud est supprimé au début de la liste chaînée, c'est-à-dire que le nœud 3 est supprimé/supprimé.

Les DLL peuvent être parcourues dans les sens avant et arrière. L'opération de suppression dans la DLL peut être plus efficace si le pointeur de nœud à supprimer est fourni. Chaque nœud de la DLL nécessite un espace supplémentaire pour le pointeur précédent. Toutes les opérations nécessitent un pointeur supplémentaire pour être maintenues.

Avec cela, nous conclurons notre sujet « Liste Java doublement liée ». Nous avons vu ce qu'est Java Doublement Linked List et comment est-il implémenté dans la programmation Java avec quelques exemples. Nous avons également vu l'algorithme pour liste doublement chaînée et avons répertorié quelques opérations applicables aux DLL. Nous avons implémenté les premières opérations d'insertion et de suppression. De même, il existe d'autres opérations également disponibles sur lesquelles vous pouvez travailler.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!