Java >> Tutoriel Java >  >> Java

Comment inverser une liste chaînée en Java

Java

Dans ce tutoriel, nous allons voir comment inverser une liste chaînée en java. LinkedList est une structure de données linéaire où les éléments ne sont pas stockés dans des emplacements contigus et chaque élément est un objet séparé avec une partie données et une partie adresse. Chaque élément est appelé nœud. En raison de la dynamique et de la facilité des insertions et des suppressions, ils sont préférés aux tableaux. Mais avant d'aller plus loin, si vous n'êtes pas familier avec le concept de liste chaînée en Java, consultez l'article sur la liste chaînée en Java.

Entrée : Saisissez les éléments de la liste chaînée :6 7 8 4 5

Sortie : Avant d'inverser la liste chaînée :6 7 8 9 5

Après avoir inversé la liste chaînée :5 9 8 7 6

Cela peut être fait en utilisant les méthodes suivantes :

Approche 1 :Utiliser une méthode intégrée

Approche 2 : sans utiliser de méthode intégrée

Examinons chacune de ces approches pour une meilleure compréhension.

Programme 1 :Programme Java pour inverser une liste chaînée

Dans ce programme, nous verrons comment inverser une liste chaînée en java en utilisant la classe collections.

Algorithme :

  1. Démarrer
  2. Déclarer une liste chaînée de types entiers sans aucune taille initiale.
  3. Utilisez la méthode add pour ajouter les éléments.
  4. Ajoutez les éléments à la fin de la liste.
  5. Imprimez les éléments de la liste liée avant de les inverser.
  6. Utilisez la méthode In-built Collections.reverse() pour inverser une liste chaînée.
  7. Imprimer les éléments de la liste liée après l'inversion.
  8. Arrêter

Regardons l'exemple ci-dessous pour une meilleure compréhension de l'algorithme ci-dessus.

// Java program for reversing a linked list using in-built collections class
import java.util.*;
  
public class Main 
{
    public static void main(String[] args)
    {
        // Declaring linkedlist without any initial size
        LinkedList<Integer> ll = new LinkedList<Integer>();
  
        // Appending elements at the end of the list
        ll.add(new Integer(1));
        ll.add(new Integer(2));
        ll.add(new Integer(3));
        ll.add(new Integer(4));
        ll.add(new Integer(5));
        System.out.println("The elements of the linked list before reversing: " + ll);
        // Collections.reverse method to reverse the list
        Collections.reverse(ll);
        System.out.println("The elements of the linked list after reversing: " + ll);
    }
}


Les éléments de la liste chaînée avant inversion :[1, 2, 3, 4, 5]
Les éléments de la liste chaînée après inversion :[5, 4, 3, 2, 1]

Programme 2 :Programme Java pour inverser une liste chaînée

Dans ce programme, nous verrons comment inverser une liste chaînée en Java en utilisant n'importe quelle méthode intégrée.

Algorithme :

  1. Démarrer
  2. Déclarer une liste chaînée de types de chaînes sans aucune taille initiale.
  3. Utilisez la méthode add pour ajouter les éléments.
  4. Ajoutez les éléments à la fin de la liste.
  5. Imprimez les éléments de la liste liée avant de les inverser.
  6. Utilisez une fonction définie par l'utilisateur pour l'inversion.
  7. Prenez la liste chaînée comme paramètre et renvoyez la liste chaînée inverse.
  8. Exécutez la boucle n/2 fois où "n" est le nombre d'éléments dans la liste liée.
  9. Dans la première passe, échangez le premier et le nième élément.
  10. Dans la deuxième passe, échangez le deuxième et le (n-1)ème élément et ainsi de suite jusqu'à ce que vous atteigniez le milieu de la liste liée.
  11. Renvoyer la liste chaînée après la fin de la boucle.
  12. Imprimer les éléments de la liste liée après l'inversion.
  13. Arrêter

Regardons l'exemple ci-dessous pour une meilleure compréhension de l'algorithme ci-dessus.

// Java program to reverse a linked list
import java.util.*;

public class Main 
{
	public static void main(String[] args)
	{
		LinkedList<String> ll = new LinkedList<String>();
		ll.add(new String("Physics"));
		ll.add(new String("Maths"));
		ll.add(new String("Java"));
		ll.add(new String("English"));
		ll.add(new String("Chemistry"));
		System.out.println("The elements of the linked list before reversing: " + ll);
		// Calling user defined function for reversing
		ll = reverseLinkedList(ll);
		System.out.println("The elements of the linked list after reversing: " + ll);
	}
	//Takes a linkedlist as a parameter and returns a reversed linked list
	public static LinkedList<String> reverseLinkedList(LinkedList<String> ll)
	{
		for (int i = 0; i < ll.size() / 2; i++) 
		{
			String temp = ll.get(i);
			ll.set(i, ll.get(ll.size() - i - 1));
			ll.set(ll.size() - i - 1, temp);
		}
		// Return the reversed arraylist
		return ll;
	}
}


Les éléments de la liste chaînée avant inversion :[Physique, Maths, Java, Anglais, Chimie]
Les éléments de la liste chaînée après inversion :[Chimie, Anglais, Java, Maths, Physique]


Balise Java