Liste chaînée inversée en Java

Une structure de données composée de nœuds où des données et un pointeur sont présents dans chaque nœud et le pointeur pointe vers le nœud suivant est appelée une liste chaînée qui est différente d'un tableau, et lorsqu'une telle liste chaînée est inversée, elle est appelée liste chaînée inversée. Dans lequel la liste est divisée en deux parties appelées le premier nœud de la liste et le reste de la liste chaînée, parmi lesquelles la fonction inverse est appelée pour le reste de la liste chaînée et le reste de la liste chaînée est lié au premier nœud , et le pointeur de tête est fixe. Dans cette rubrique, nous allons découvrir la liste chaînée inversée en Java.

Commencez votre cours de développement de logiciels libres

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

Fonctionnement de la liste chaînée inversée en Java

Une liste chaînée peut être inversée en Java à l'aide de deux algorithmes. Ce sont :

1. Algorithme itératif

Les étapes ci-dessous décrivent le fonctionnement d'un algorithme itératif :

• Trois pointeurs doivent être initialisés, appelés ptrA, ptrB et ptrC.
• Le ptrA pointe en premier lieu. C’est la tâche du ptrA. ptrB utilise ptrA comme référence pour pointer en arrière. Puisque le dernier nœud de la liste inversée est nul, initialement, ce pointeur sera également nul.
• Le ptrB pointe vers la deuxième place. C'est le pointeur principal. Le prochain des ptrB est pointé vers ptrA, et c'est ainsi que le lien existant des pointeurs est inversé.
• La troisième place est désignée par le ptrC. L'utilisation de ce pointeur est destinée à la sauvegarde pour s'assurer que la liste n'est pas perdue avant ptrB ; sinon, cela entraîne une perte de références avant ptrB.
• L'inversion de la liste chaînée commence par l'initialisation du ptrA à Null. Il doit être défini sur null car ptrA sera le nœud de queue après avoir inversé la liste chaînée.
• Le suivant de ptrB est lié à ptrA car le ptrB, qui pointe vers le premier nœud, devient le nœud de queue dans la liste inversée.
• Si la liste composée d'un seul nœud doit être inversée, suivre les deux étapes ci-dessus peut terminer la tâche.
• La référence à la liste précédant ptrB sera perdue lorsque le prochain ptrB pointera vers ptrA. Nous utiliserons donc ptrC comme sauvegarde de la liste avancée de ptrB avant de pointer les ptrB à côté de ptrA.
• Les étapes ci-dessus sont répétées jusqu'à ce que le ptrB pointe vers null, ce qui signifie que tous les nœuds de la liste d'origine sont inversés.

2. Algorithme récursif

Les étapes ci-dessous décrivent le fonctionnement d'un algorithme récursif :

• L'algorithme commence par considérer le courant du nœud à partir de la tête.
• Si le courant du nœud est nul, alors il est renvoyé.
• Si l'élément suivant du nœud actuel est nul, cela indique qu'il s'agit du dernier nœud de la liste. La tête de la liste inversée doit être le dernier nœud, et donc le dernier nœud doit être défini comme tête puis revenir.
• La liste est parcourue de manière récursive.
• Le courant est défini sur current.next.next.
• Null est défini sur current.next.

Exemples de liste chaînée inversée en Java

Voici les exemples suivants mentionnés ci-dessous

Exemple n°1

Programme Java pour inverser une liste à chaînage unique à l'aide d'un algorithme itératif

Code :

class List
{
static Node head1;
static class Node
{
int data1;
Node nex;
Node(int d1)
{
data1 = d1;
nex = null;
}
}
//The linked list is reversed using this function
Node reverselist(Node node1)
{
Node previous = null;
Node curr = node1;
Node nex = null;
while (curr != null)
{
nex = curr.nex;
curr.nex = previous;
previous = curr;
curr = nex;
}
node1 = previous;
return node1;
}
// The contents of linked list are printed
void printL(Node node1)
{
while (node1 != null)
{
System.out.print(node1.data1 + " ");
node1 = node1.nex;
}
}
public static void main(String[] args)
{
//The values to be inserted in the list before reversing are given here
List l = new List();
l.head1 = new Node(30);
l.head1.nex = new Node(40);
l.head1.nex.nex = new Node(50);
l.head1.nex.nex.nex = new Node(60);
System.out.println("The items in the linked list that needs to be reversed are");
l.printL(head1);
//Function to reverse the list is called here
head1 = l.reverselist(head1);
System.out.println("");
System.out.println("The items in the reversed linked list are");
l.printL(head1);
}
}

Sortie :

Exemple n°2

Programme Java pour inverser une liste à chaînage unique à l'aide d'un algorithme itératif

Code :

class List {
static Node head1;
static class Node {
int data1;
Node nex;
Node(int d1)
{
data1 = d1;
nex = null;
}
}
// A recursive function to reverse the linked list
Node reverse(Node current, Node previous)
{
//Last node is marked as head
if (current.nex == null) {
head1 = current;
//previous node is updated with next
current.nex = previous;
return head1;
}
//current.nex node is saved for the recursive call
Node nex1 = current.nex;
//nex is updated
current.nex = previous;
reverse(nex1, current);
return head1;
}
// Content of the reversed linked list are printed
void printL(Node node)
{
while (node != null) {
System.out.print(node.data1 + " ");
node = node.nex;
}
}
//Main method is called which prints the reversed linked list by calling the function
public static void main(String[] args)
{
//The values to be inserted in the list before reversing are given here
List list = new List();
list.head1 = new Node(20);
list.head1.nex = new Node(30);
list.head1.nex.nex = new Node(40);
list.head1.nex.nex.nex = new Node(50);
System.out.println("The items in the linked list that needs to be reversed are");
list.printL(head1);
//Function to reverse the list is called here
Node result = list.reverse(head1, null);
System.out.println("");
System.out.println("");
System.out.println("The items in the reversed linked list are");
list.printL(result);
}
}

Sortie :

Conclusion

Dans ce tutoriel, nous comprenons le concept d'inversion de la liste chaînée à travers la définition, la logique sur laquelle la liste chaînée est inversée est expliquée. Les deux algorithmes pour inverser la liste chaînée sont expliqués, qui est un algorithme itératif, et l'algorithme récursif est expliqué ainsi que les exemples de programmation pour implémenter les algorithmes en Java.

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!