Java >> Tutoriel Java >  >> Java

LinkedList en Java expliqué avec des exemples

LinkedList est une structure de données linéaire similaire aux tableaux en Java. Les éléments LinkedList, en revanche, ne sont pas conservés dans des emplacements contigus comme les tableaux; au lieu de cela, ils sont liés entre eux via des pointeurs. Chaque membre LinkedList a une référence (adresse/pointeur) vers l'élément LinkedList suivant.

Les éléments de la classe Java LinkedList sont stockés sous la forme d'une liste à double liaison. Il utilise une structure de données de liste liée pour stocker des informations. Il implémente les interfaces List et Deque et hérite de la classe AbstractList. L'interface de liste est implémentée par les classes AbstractList, CopyOnWriteArrayList et AbstractSequentialList. Chacune des clauses mentionnées ci-dessus a son propre ensemble de fonctionnalités. Ils sont les suivants :

Liste abstraite :Cette classe est utilisée pour implémenter une liste immuable, et il suffit de l'étendre et d'implémenter uniquement les fonctions get() et size(). Cette classe implémente l'interface de liste.

CopyOnWriteArrayList :Cette classe implémente l'interface de liste. Il s'agit d'une version améliorée de ArrayList dans laquelle toutes les modifications (ajout, définition, suppression, etc.) sont effectuées en créant une nouvelle copie de la liste.

Voici les principales fonctionnalités de Java LinkedList :

  • Les éléments en double sont possibles dans la classe Java LinkedList.
  • La classe LinkedList en Java assure le suivi de l'ordre d'insertion.
  • La classe LinkedList en Java n'est pas synchronisée.
  • La manipulation dans la classe Java LinkedList est rapide car aucun décalage n'est nécessaire.
  • La classe LinkedList en Java est utilisée pour créer une liste, une pile ou une file d'attente.

Représentation de LinkedList

  • Le Node est le nom donné à chaque élément de la LinkedList. Les nœuds de la LinkedList ont chacun deux éléments :
  • a) Le contenu de l'élément
  • b) Pointeur/Adresse/Référence vers le nœud suivant de la LinkedList.
  • Le Head de la LinkedList contient simplement l'adresse du premier élément de la liste.
  • Parce que c'est la fin de la liste, le dernier élément de la LinkedList a null dans la section pointeur du nœud, comme indiqué dans le diagramme.
  • La liste liée par défaut est une liste liée singleton.
  • La liste à double lien est une version plus complexe de LinkedList. Chaque nœud d'une liste doublement liée est composé de trois parties :
  • a) Un pointeur vers le nœud précédent de la liste chaînée.
  • b) Le contenu de l'élément
  • c) Un pointeur vers le nœud suivant de la liste chaînée.

À quoi sert une liste liée ?

Vous devez être familiarisé avec les tableaux, qui sont également des structures de données linéaires, mais ils ont certaines limites, telles que :

  • La taille d'un tableau est fixe et il est difficile de prédire le nombre d'éléments à l'avance. Si la taille déclarée est insuffisante, nous ne pouvons pas augmenter la taille d'un tableau ; si nous déclarons un tableau de grande taille et n'avons pas besoin de stocker autant d'éléments, c'est une perte de mémoire.
  • Pour stocker leurs valeurs, les éléments du tableau nécessitent des régions de mémoire contiguës.
  • L'insertion d'un élément dans un tableau est lente car elle nécessite de déplacer d'autres éléments pour créer de la place pour le nouvel élément. Imaginons que nous ayons un tableau avec les éléments suivants :40, 42, 55, 60, 74, 95, 109. Si nous voulons ajouter un nouvel élément 58 après l'élément de valeur 42, nous devons d'abord décaler tous les éléments après 42 vers la droite pour faire place au nouvel élément.

De même, la suppression d'un élément d'un tableau est une opération qui prend du temps car tous les éléments après l'élément supprimé doivent être déplacés vers la gauche. La liste chaînée surmonte ces contraintes en offrant les fonctionnalités suivantes :

  • Les listes chaînées prennent en charge l'allocation de mémoire dynamique, ce qui signifie que le compilateur alloue de la mémoire au moment de l'exécution, et nous n'avons pas à fournir la taille de la liste lors de la déclaration de la liste chaînée.
  • Étant donné que les éléments sont liés les uns aux autres à l'aide du composant de référence du nœud, qui fournit l'adresse du nœud suivant dans la liste, les éléments de la liste liée ne nécessitent pas d'emplacements de mémoire contigus.
  • Les opérations d'insertion et de suppression de listes chaînées ne sont pas gourmandes en performances. L'ajout et la suppression d'un élément de la liste liée ne nécessite pas de déplacement d'élément. Au lieu de cela, le pointeur vers le nœud précédent et suivant doit être changé.

En interne, comment fonctionne LinkedList ?

Étant donné qu'une LinkedList fonctionne comme un tableau dynamique et que nous n'avons pas à définir la taille lorsque nous la créons, la taille de la liste augmente à mesure que nous ajoutons et supprimons des éléments de manière dynamique. De plus, les éléments ne sont pas maintenus dans un état continu. Par conséquent, il n'est pas nécessaire d'augmenter la taille.

La structure de données de la liste à double liaison est utilisée pour implémenter la LinkedList en interne. La différence fondamentale entre une liste chaînée standard et une liste doublement chaînée est que cette dernière a un pointeur supplémentaire, généralement appelé pointeur précédent, en plus du pointeur suivant et des données trouvées dans la liste chaînée simple.

Méthodes Java LinkedList

LinkedList a plusieurs méthodes qui effectuent diverses actions sur les listes liées. Dans cet article, nous examinerons quatre opérateurs LinkedList souvent utilisés :

  • Ajout d'éléments
  • Accès aux éléments
  • Modification des éléments
  • Suppression d'éléments

Ajout d'éléments à une LinkedList

La méthode add() est utilisée pour ajouter un élément (nœud) à la fin d'une LinkedList. Par exemple,

import java.util.LinkedList;

class CodeMain {

  public static void main(String[] args){
    // creation of a citiesList linkedlist
    LinkedList<String> citiesList = new LinkedList<>();

    // add() method without the index parameter
    citiesList.add("New York");
    citiesList.add("Los Angeles");
    citiesList.add("Manchester");
    System.out.println("LinkedList: " + citiesList);

    // add() method with the index parameter
    citiesList.add(1, "Paris");
    System.out.println("Updated LinkedList: " + citiesList);
  }
}

Nous avons établi une LinkedList nommée villes dans l'exemple précédent. Dans cet exemple, nous avons utilisé la méthode add() pour ajouter des composants aux villes.

citiesList.add(1, "Paris");

Nous avons utilisé le paramètre de numéro d'index dans ce cas. C'est un argument facultatif déterminant où le nouvel élément doit être placé.

Accès aux éléments LinkedList

Pour accéder à un élément LinkedList, utilisez la fonction get() de la classe LinkedList. Par exemple,

import java.util.LinkedList;

class CodeMain {
  public static void main(String[] args) {
    LinkedList<String> compCompanies = new LinkedList<>();

    // add elements in the linked list
    compCompanies.add("Microsoft");
    compCompanies.add("Apple");
    compCompanies.add("Google");
    System.out.println("LinkedList: " + compCompanies);

    // get the element from the linked list
    String strVal = compCompanies.get(1);
    System.out.print(" The Item at index 1: " + strVal);
  }
}

Nous avons utilisé la méthode get() avec le paramètre 1 dans l'exemple précédent. La procédure retourne l'élément à l'index 1 dans ce cas.

Modifier les éléments d'une LinkedList

La fonction set() de la classe LinkedList est utilisée pour modifier les éléments de la LinkedList. Par exemple,

import java.util.LinkedList;

class CodeMain {
  public static void main(String[] args) {

    LinkedList<String> clubList = new LinkedList<>();

    // add elements in the linked list
    clubList.add("Chelsea");
    clubList.add("Manchester City");
    clubList.add("Liverpool");
    languages.add("Manchester United");
    System.out.println("The original club LinkedList is: " + clubList);

    // changing the elements at the third index
    languages.set(3, "Aston Villa");
    System.out.println("The updated club LinkedList is : " + clubList);
  }
}

Supprimer un élément d'une LinkedList

La méthode remove() de la classe LinkedList est utilisée pour supprimer un élément de la LinkedList. Par exemple,

import java.util.LinkedList;

class CodeMain {
  public static void main(String[] args) {
    LinkedList<String> fruitList = new LinkedList<>();

    // add elements in LinkedList
    fruitList.add("Java");
    fruitList.add("Python");
    fruitList.add("JavaScript");
    fruitList.add("Kotlin");
    System.out.println("LinkedList: " + fruitList);

    // remove elements from index 1
    String str = fruitList.remove(1);
    System.out.println("Removed Element: " + str);

    System.out.println("Updated LinkedList: " + fruitList);
  }
}

Méthodes supplémentaires

  • contains() - détermine si l'élément est présent dans la LinkedList
  • indexOf() - renvoie l'index de la première apparition de l'élément.
  • LastIndexOf() - donne l'index de l'occurrence la plus récente de l'élément
  • clear() – supprime tous les éléments de la LinkedList
  • iterator() -fournit un itérateur qui est utilisé pour boucler sur la LinkedList.

Deque et file d'attente pour LinkedList

Étant donné que la classe LinkedList implémente à la fois les interfaces Queue et Deque, elle peut appliquer les fonctions des deux. Voici quelques-unes des méthodes les plus populaires :

  • addFirst() - ajoute l'élément spécifié au début de la liste liée.
  • addLast() - ajoute l'entrée fournie à la fin de la liste liée
  • getFirst() - responsable du retour du premier élément
  • getLast() - responsable du retour du dernier élément
  • removeFirst() - chargé de supprimer le premier élément
  • removeLast() - chargé de supprimer le dernier élément
  • peek() - donne le premier membre de la liste liée (tête).
  • poll() - récupère la première entrée de la liste liée et la supprime
  • offer() - ajoute l'entrée fournie à la fin de la liste liée

Exemple :Ajouter des éléments à une liste liée Java

Les méthodes add(), addFirst() et addLast() sont utilisées dans l'exemple suivant pour ajouter des membres à LinkedList aux positions appropriées. Il existe plusieurs autres méthodes utiles dans la classe LinkedList que je décrirai à la fin de cet article.

package com.codeunderscored;
import java.util.*;

public class CodeExampleJava{

   public static void main(String args[]){

     LinkedList<String> strList=new LinkedList<String>();

     //Linked list components are being added.
     strList.add("Green");
     strList.add("White");
     strList.add("Brown");

     //Adding a second element to the first
     strList.addFirst("Monroe");

     //Incorporating a new element into the final position
     strList.addLast("Spider");

     //Incorporating an element into the third position
     strList.add(2, "James");

     //LinkedList Iteration
     Iterator<String> newIterator=list.iterator();
     while(newIterator.hasNext()){
       System.out.println(newIterator.next());
     }
   }
}

Exemple :LinkedList comme Deque

import java.util.LinkedList;
import java.util.Deque;

class CodeMain {
  public static void main(String[] args){

    Deque<String> citiesList = new LinkedList<>();

    // adding a new item to citiesList's beginning
    citiesList.add("Manchester");
    System.out.println("LinkedList: " + citiesList);

    citiesList.addFirst("London");
    System.out.println("LinkedList after addFirst(): " + citiesList);

    // adding a new element to citiesList's end
    citiesList.addLast("New York");
    System.out.println("LinkedList after addLast(): " + citiesList);

    // removing the first element from  citiesList
    citiesList.removeFirst();
    System.out.println("LinkedList after removeFirst(): " + citiesList);

    // removal of the last element from  citiesList
    citiesList.removeLast();
    System.out.println("LinkedList after removeLast(): " + citiesList);
  }
}

Exemple :suppression d'éléments d'une LinkedList

Dans l'exemple suivant, nous examinerons quelques méthodes de suppression typiques dans la LinkedList qui sont utilisées pour supprimer des éléments de points spécifiques dans la LinkedList. Les didacticiels distincts fournissent une description détaillée de ces stratégies et des exemples.

package com.codeunderscored;
import java.util.*;

public class CodeExampleJava{
   public static void main(String args[]){

      LinkedList<String> nameList=new LinkedList<String>();

      //Linked list components are being added.
      nameList.add("Mike");
      nameList.add("Joy");
      nameList.add("White");
      nameList.add("Monroe");
      nameList.add("James");

      //Getting rid of the first element
      //Same as list.remove(0);
      nameList.removeFirst();

      //Removing the final component
      nameList.removeLast();

      //LinkedList Iteration
      Iterator<String> newIterator=nameList .iterator();
      while(newIterator .hasNext()){
         System.out.print(newIterator .next()+" ");
      }

      //When the second element is removed, the index is reset to zero.
      nameList.remove(1);

      System.out.print("\nAfter removing second element: ");

      //Re-iterating the LinkedList
      Iterator<String> secondIterator=nameList .iterator();
      while(secondIterator .hasNext()){
         System.out.print(secondIterator .next()+" ");
      }
   }
}

Exemple :itération via LinkedList

import java.util.LinkedList;

class CodeMain {
    public static void main(String[] args) {

        // Creating a new linked list
        LinkedList<String> flowerList = new LinkedList<>();
        flowerList.add("Rose");
        flowerList.add("Aster");
        flowerList.add("Azalea");
        System.out.println("The flowerList LinkedList is: " + flowerList);

        // Using the forEach loop
        System.out.println("Accessing the flowerList list elements:");
        for(String fl: flowerList) {
            System.out.print(fl);
            System.out.print(", ");
        }
    }
}

Exemple :LinkedList en Java

import java.util.*;

public class CodeLinkedList {

     public static void main(String args[]) {

       /* Declaration of a Linked List */
       LinkedList<String> strLinkedList = new LinkedList<String>();

       /*
* The function add(String Element) adds elements to the linked list.
*/

       strLinkedList.add("IBM");
       strLinkedList.add("Lenovo");
       strLinkedList.add("Toshiba");
       strLinkedList.add("Apple");
       strLinkedList.add("Microsoft");

       /*Display Linked List Content*/
       System.out.println("The contents of the Linked List comprise of: " +strLinkedList);

       /*Add First and Last Element*/
       strLinkedList.addFirst("First Item");
       strLinkedList.addLast("Last Item");
       System.out.println("Content of the LinkedList once it has been added : " +strLinkedList);

       /* This is how you get values and change them.  */
       Object firstvar = linkedlist.get(0);
       System.out.println("The First element is: " +firstvar);
       linkedlist.set(0, "The first point has been modified.  ");

       Object secondVar = linkedlist.get(0);
       System.out.println("First element after update by set method: " +secondVar);

       /*Remove first and last element*/
       strLinkedList.removeFirst();
       strLinkedList.removeLast();
       System.out.println("LinkedList with the first and last elements removed : " +strLinkedList);

       /* Toggle between adding and removing items from a place. */
       strLinkedList.add(0, "Item that has recently been added ");
       strLinkedList.remove(2);
       System.out.println("The comprehensive Content is: " +strLinkedList);
     }
}

Exemple :Java LinkedList en tant que file d'attente

import java.util.LinkedList;
import java.util.Queue;

class CodeMain {
  public static void main(String[] args) {

    Queue<String> fruitsList = new LinkedList<>();

    // add elements
    fruitsList.add("Mango");
    fruitsList.add("Quava");
    fruitsList.add("Apple");
    System.out.println("LinkedList: " + fruitsList);

    // accessing the fruitsList's first element
    String str_one = fruitsList.peek();
    System.out.println("Accessed Element: " + str_one);

    // accessing and removing the fruitsList's first element
    String second_string = fruitsList.poll();
    System.out.println("Removed Element: " + second_string);
    System.out.println("LinkedList after poll(): " + fruitsList);

    // add a new fruits at the end of  fruitsList
    languages.offer("Banana");
    System.out.println("LinkedList after offer(): " + fruitsList);
  }
}

Conclusion

Cet article a expliqué ce qu'est une structure de données de liste chaînée en Java et comment en créer, initialiser, implémenter, traverser, inverser et trier une.

Une LinkedList est une structure de données en Java qui contient des éléments de manière non contiguë. C'est une structure de données qui est linéaire. Chaque élément de données est appelé un « nœud », et chaque nœud comporte deux parties :les données et l'adresse. Le composant d'adresse de LinkedList stocke le lien vers le nœud suivant.

Le framework Collection dans le package java.util inclut une liste liée. Cette classe implémente la structure de données LinkedList, une structure de données linéaire dans laquelle les composants ne sont pas conservés dans un ordre séquentiel. Chaque élément est un objet séparé ayant une partie données et adresse. Des pointeurs et des adresses sont utilisés pour connecter les éléments. Chaque élément est appelé nœud.

Ils sont préférables aux baies en raison de leur nature dynamique et de la facilité d'insertion et de retrait. Il présente également certains inconvénients, tels que des nœuds inaccessibles immédiatement; au lieu de cela, nous devons commencer par le haut et suivre le lien vers le nœud souhaité.


Balise Java