Liste liée Java

Dans ce didacticiel, nous allons en savoir plus sur Java LinkedList à l'aide d'exemples.

Le LinkedList La classe du framework de collections Java fournit la fonctionnalité de la structure de données de liste liée (liste doublement liée).

Chaque élément d'une liste liée est appelé nœud . Il se compose de 3 champs :

Précédent - stocke une adresse de l'élément précédent dans la liste. Il est null pour le premier élément
Suivant - stocke une adresse de l'élément suivant dans la liste. Il est null pour le dernier élément
Données - stocke les données réelles

Création d'une liste liée Java

Voici comment nous pouvons créer des listes liées en Java :

LinkedList<Type> linkedList = new LinkedList<>();

Ici, Tapez indique le type d'une liste chaînée. Par exemple,

// create Integer type linked list
LinkedList<Integer> linkedList = new LinkedList<>();

// create String type linked list
LinkedList<String> linkedList = new LinkedList<>();

Exemple :créer une liste liée en Java

import java.util.LinkedList;

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

    // create linkedlist
    LinkedList<String> animals = new LinkedList<>();

    // Add elements to LinkedList
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);
  }
}

Sortie

LinkedList: [Dog, Cat, Cow]

Dans l'exemple ci-dessus, nous avons créé un LinkedList nommés animaux .

Ici, nous avons utilisé le add() méthode pour ajouter des éléments à la LinkedList. Nous en apprendrons plus sur le add() méthode plus loin dans ce didacticiel.

Fonctionnement d'une LinkedList Java

Les éléments des listes liées ne sont pas stockés dans l'ordre. Au lieu de cela, ils sont dispersés et reliés par des liens (Précédent et Suivant ).

Ici, nous avons 3 éléments dans une liste chaînée.

Chien - c'est le premier élément qui contient null comme adresse précédente et l'adresse de Chat comme prochaine adresse
Chat - c'est le deuxième élément qui contient une adresse de Chien comme l'adresse précédente et l'adresse de Cow comme prochaine adresse
Vache - c'est le dernier élément qui contient l'adresse de Chat comme adresse précédente et null comme élément suivant

Pour en savoir plus, visitez la structure de données LinkedList.

Méthodes de Java LinkedList

LinkedList fournit diverses méthodes qui nous permettent d'effectuer différentes opérations dans les listes chaînées. Nous examinerons quatre opérateurs LinkedList couramment utilisés dans ce didacticiel :

Ajouter des éléments
Éléments d'accès
Modifier des éléments
Supprimer des éléments

1. Ajouter des éléments à une LinkedList

Nous pouvons utiliser le add() méthode pour ajouter un élément (nœud) à la fin de la LinkedList. Par exemple,

import java.util.LinkedList;

class Main {
  public static void main(String[] args){
    // create linkedlist
    LinkedList<String> animals = new LinkedList<>();

    // add() method without the index parameter
    animals.add("Dog");
    animals.add("Cat");
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

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

Sortie

LinkedList: [Dog, Cat, Cow]
Updated LinkedList: [Dog, Horse, Cat, Cow]

Dans l'exemple ci-dessus, nous avons créé une LinkedList nommée animaux . Ici, nous avons utilisé le add() méthode pour ajouter des éléments à animaux .

Remarquez la déclaration,

animals.add(1, "Horse");

Ici, nous avons utilisé le numéro d'index paramètre. C'est un paramètre facultatif qui spécifie la position où le nouvel élément est ajouté.

Pour en savoir plus sur l'ajout d'éléments à LinkedList, visitez le programme Java pour ajouter des éléments à LinkedList.

2. Accéder aux éléments LinkedList

Le get() La méthode de la classe LinkedList est utilisée pour accéder à un élément de la LinkedList. Par exemple,

import java.util.LinkedList;

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

    // add elements in the linked list
    languages.add("Python");
    languages.add("Java");
    languages.add("JavaScript");
    System.out.println("LinkedList: " + languages);

    // get the element from the linked list
    String str = languages.get(1);
    System.out.print("Element at index 1: " + str);
  }
}

Sortie

LinkedList: [Python, Java, JavaScript]
Element at index 1: Java

Dans l'exemple ci-dessus, nous avons utilisé le get() méthode avec le paramètre 1 . Ici, la méthode renvoie l'élément à l'index 1 .

Nous pouvons également accéder aux éléments de la LinkedList en utilisant le iterator() et le listIterator() méthode. Pour en savoir plus, visitez le programme Java pour accéder aux éléments de LinkedList.

3. Modifier les éléments d'une LinkedList

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

import java.util.LinkedList;

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

    // add elements in the linked list
    languages.add("Java");
    languages.add("Python");
    languages.add("JavaScript");
    languages.add("Java");
    System.out.println("LinkedList: " + languages);

    // change elements at index 3
    languages.set(3, "Kotlin");
    System.out.println("Updated LinkedList: " + languages);
  }
}

Sortie

LinkedList: [Java, Python, JavaScript, Java]
Updated LinkedList: [Java, Python, JavaScript, Kotlin]

Dans l'exemple ci-dessus, nous avons créé une LinkedList nommée languages. Remarquez la ligne,

languages.set(3, "Kotlin");

Ici, le set() la méthode change l'élément à l'index 3 à Kotlin .

4. Supprimer un élément d'une LinkedList

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

import java.util.LinkedList;

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

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

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

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

Sortie

LinkedList: [Java, Python, JavaScript, Kotlin]
Removed Element: Python
New LinkedList: [Java, JavaScript, Kotlin]

Ici, le remove() La méthode prend le numéro d'index comme paramètre. Et supprime l'élément spécifié par le numéro d'index.

Pour en savoir plus sur la suppression d'éléments de la liste liée, visitez le programme Java pour supprimer des éléments de LinkedList.

Autres méthodes

Méthodes	Description
`contains()`	vérifie si la LinkedList contient l'élément
`indexOf()`	retourne l'index de la première occurrence de l'élément
`lastIndexOf()`	renvoie l'index de la dernière occurrence de l'élément
`clear()`	supprime tous les éléments de la LinkedList
`iterator()`	retourne un itérateur pour itérer sur LinkedList

LinkedList comme Deque et Queue

Depuis le LinkedList La classe implémente également les interfaces Queue et Deque, elle peut également implémenter les méthodes de ces interfaces. Voici quelques-unes des méthodes couramment utilisées :

Méthodes	Descriptions
`addFirst()`	ajoute l'élément spécifié au début de la liste liée
`addLast()`	ajoute l'élément spécifié à la fin de la liste liée
`getFirst()`	retourne le premier élément
`getLast()`	retourne le dernier élément
`removeFirst()`	supprime le premier élément
`removeLast()`	supprime le dernier élément
`peek()`	retourne le premier élément (head) de la liste chaînée
`poll()`	retourne et supprime le premier élément de la liste liée
`offer()`	ajoute l'élément spécifié à la fin de la liste liée

Exemple :Java LinkedList en tant que file d'attente

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

class Main {
  public static void main(String[] args) {
    Queue<String> languages = new LinkedList<>();

    // add elements
    languages.add("Python");
    languages.add("Java");
    languages.add("C");
    System.out.println("LinkedList: " + languages);

    // access the first element
    String str1 = languages.peek();
    System.out.println("Accessed Element: " + str1);

    // access and remove the first element
    String str2 = languages.poll();
    System.out.println("Removed Element: " + str2);
    System.out.println("LinkedList after poll(): " + languages);

    // add element at the end
    languages.offer("Swift");
    System.out.println("LinkedList after offer(): " + languages);
  }
}

Sortie

LinkedList: [Python, Java, C]
Accessed Element: Python
Removed Element: Python
LinkedList after poll(): [Java, C]
LinkedList after offer(): [Java, C, Swift]

Exemple :LinkedList comme Deque

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

class Main {
  public static void main(String[] args){
    Deque<String> animals = new LinkedList<>();

    // add element at the beginning
    animals.add("Cow");
    System.out.println("LinkedList: " + animals);

    animals.addFirst("Dog");
    System.out.println("LinkedList after addFirst(): " + animals);

    // add elements at the end
    animals.addLast("Zebra");
    System.out.println("LinkedList after addLast(): " + animals);

    // remove the first element
    animals.removeFirst();
    System.out.println("LinkedList after removeFirst(): " + animals);

    // remove the last element
    animals.removeLast();
    System.out.println("LinkedList after removeLast(): " + animals);
  }
}

Sortie

LinkedList: [Cow]
LinkedList after addFirst(): [Dog, Cow]
LinkedList after addLast(): [Dog, Cow, Zebra]
LinkedList after removeFirst(): [Cow, Zebra]
LinkedList after removeLast(): [Cow]

Itération via LinkedList

Nous pouvons utiliser la boucle Java for-each pour parcourir LinkedList. Par exemple,

import java.util.LinkedList;

class Main {
    public static void main(String[] args) {
        // Creating a linked list
        LinkedList<String> animals = new LinkedList<>();
        animals.add("Cow");
        animals.add("Cat");
        animals.add("Dog");
        System.out.println("LinkedList: " + animals);

        // Using forEach loop
        System.out.println("Accessing linked list elements:");
        for(String animal: animals) {
            System.out.print(animal);
            System.out.print(", ");
        }
    }
}

Sortie

LinkedList: [Cow, Cat, Dog]
Accessing linked list elements:
Cow, Cat, Dog,

LinkedList Vs. Liste de tableaux

Java ArrayList et LinkedList implémente le List interface du Collections cadre. Cependant, il existe une différence entre eux.

Liste liée	Liste de tableaux
Mise en œuvre `List` , `Queue` , et `Deque` interfaces.	Met en œuvre `List` interface.
Stocke 3 valeurs (adresse précédente , données, et prochaine adresse ) dans une seule position.	Stocke une seule valeur dans une seule position.
Fournit l'implémentation de la liste doublement chaînée.	Fournit une implémentation de tableau redimensionnable.
Chaque fois qu'un élément est ajouté, `prev` et `next` l'adresse sont modifiées.	Chaque fois qu'un élément est ajouté, tous les éléments après cette position sont décalés.
Pour accéder à un élément, nous devons itérer depuis le début jusqu'à l'élément.	Peut accéder de manière aléatoire à des éléments à l'aide d'index.

Remarque :Nous pouvons également créer une LinkedList en utilisant des interfaces en Java. Par exemple,

// create linkedlist using List
List<String> animals1 = new LinkedList<>();

// creating linkedlist using Queue
Queue<String> animals2 = new LinkedList<>();

// creating linkedlist using Deque
Deque<String> animals3 = new LinkedList<>();

Ici, si la LinkedList est créée à l'aide d'une interface, nous ne pouvons pas utiliser les méthodes fournies par d'autres interfaces. Autrement dit, animaux1 ne peut pas utiliser les méthodes spécifiques à Queue et Deque interfaces.

Interface Java Deque ArrayDeque Java

Java