Dans ce didacticiel, nous découvrirons en détail la LinkedList Java à l'aide d'exemples.
La LinkedListclasse du framework de collections Java fournit la fonctionnalité de la structure de données de la liste liée (double liste liée).
Java Doublement LinkedList
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. C'est
nullpour le premier élément - Suivant - stocke une adresse de l'élément suivant dans la liste. C'est
nullpour le dernier élément - Données - stocke les données réelles
Créer une LinkedList Java
Voici comment nous pouvons créer des listes chaînées en Java:
LinkedList linkedList = new LinkedList();
Ici, Type indique le type d'une liste liée. Par exemple,
// create Integer type linked list LinkedList linkedList = new LinkedList(); // create String type linked list LinkedList linkedList = new LinkedList();
Exemple: créer LinkedList en Java
import java.util.LinkedList; class Main ( public static void main(String() args)( // create linkedlist LinkedList animals = new LinkedList(); // Add elements to LinkedList animals.add("Dog"); animals.add("Cat"); animals.add("Cow"); System.out.println("LinkedList: " + animals); ) )
Production
LinkedList: (Chien, Chat, Vache)
Dans l'exemple ci-dessus, nous avons créé un LinkedListanimal nommé.
Ici, nous avons utilisé la add()méthode pour ajouter des éléments à la LinkedList. Nous en apprendrons plus sur la add()méthode plus loin dans ce tutoriel.
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 connectés via des liens ( Précédent et Suivant ).
Implémentation Java LinkedList
Ici, nous avons 3 éléments dans une liste chaînée.
- Chien - c'est le premier élément qui détient null comme adresse précédente et l'adresse de Cat comme adresse suivante
- Chat - c'est le deuxième élément qui contient une adresse de chien comme adresse précédente et l'adresse de vache comme adresse suivante
- Cow - c'est le dernier élément qui contient l'adresse de Cat 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
LinkedListfournit diverses méthodes qui nous permettent d'effectuer différentes opérations dans des 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
- Changer les éléments
- Supprimer des éléments
1. Ajouter des éléments à une LinkedList
Nous pouvons utiliser la 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 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); ) )
Production
LinkedList: (Chien, Chat, Vache) Mise à jour de la LinkedList: (Chien, Cheval, Chat, Vache)
Dans l'exemple ci-dessus, nous avons créé une LinkedList nommée animals. Ici, nous avons utilisé la add()méthode pour ajouter des éléments aux animaux.
Notez la déclaration,
animals.add(1, "Horse");
Ici, nous avons utilisé le paramètre de numéro d'index . 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
La get()méthode de la classe LinkedList est utilisée pour accéder à un élément à partir de LinkedList. Par exemple,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList 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); ) )
Production
LinkedList: (Python, Java, JavaScript) Élément à l'index 1: Java
Dans l'exemple ci-dessus, nous avons utilisé la 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 LinkedList en utilisant iterator()la listIterator()méthode et. Pour en savoir plus, visitez le programme Java pour accéder aux éléments de LinkedList.
3. Modifier les éléments d'une LinkedList
La set()méthode de LinkedListclasse est utilisée pour modifier les éléments de LinkedList. Par exemple,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList 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); ) )
Production
LinkedList: (Java, Python, JavaScript, Java) Mise à jour de 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, la set()méthode change l'élément à l'index 3 en Kotlin.
4. Supprimer un élément d'une LinkedList
The remove() method of the LinkedList class is used to remove an element from the LinkedList. For example,
import java.util.LinkedList; class Main ( public static void main(String() args) ( LinkedList 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); ) )
Output
LinkedList: (Java, Python, JavaScript, Kotlin) Removed Element: Python New LinkedList: (Java, JavaScript, Kotlin)
Here, the remove() method takes the index number as the parameter. And, removes the element specified by the index number.
To learn more about removing elements from the linkedlist, visit the Java program to remove elements from LinkedList…
Other Methods
| Methods | Description |
|---|---|
contains() | checks if the LinkedList contains the element |
indexOf() | returns the index of the first occurrence of the element |
lastIndexOf() | returns the index of the last occurrence of the element |
clear() | removes all the elements of the LinkedList |
iterator() | returns an iterator to iterate over LinkedList |
LinkedList as Deque and Queue
Since the LinkedList class also implements the Queue and the Deque interface, it can implement methods of these interfaces as well. Here are some of the commonly used methods:
| Methods | Descriptions |
|---|---|
addFirst() | adds the specified element at the beginning of the linked list |
addLast() | adds the specified element at the end of the linked list |
getFirst() | returns the first element |
getLast() | returns the last element |
removeFirst() | removes the first element |
removeLast() | removes the last element |
peek() | returns the first element (head) of the linked list |
poll() | returns and removes the first element from the linked list |
offer() | adds the specified element at the end of the linked list |
Example: Java LinkedList as Queue
import java.util.LinkedList; import java.util.Queue; class Main ( public static void main(String() args) ( Queue 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); ) )
Output
LinkedList: (Python, Java, C) Accessed Element: Python Removed Element: Python LinkedList after poll(): (Java, C) LinkedList after offer(): (Java, C, Swift)
Example: LinkedList as Deque
import java.util.LinkedList; import java.util.Deque; class Main ( public static void main(String() args)( Deque 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); ) )
Output
LinkedList: (Cow) LinkedList after addFirst(): (Dog, Cow) LinkedList after addLast(): (Dog, Cow, Zebra) LinkedList after removeFirst(): (Cow, Zebra) LinkedList after removeLast(): (Cow)
Iterating through LinkedList
We can use the Java for-each loop to iterate through LinkedList. For example,
import java.util.LinkedList; class Main ( public static void main(String() args) ( // Creating a linked list LinkedList 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(", "); ) ) )
Output
LinkedList: (Cow, Cat, Dog) Accessing linked list elements: Cow, Cat, Dog,
LinkedList Vs. ArrayList
Both the Java ArrayList and LinkedList implements the List interface of the Collections framework. However, there exists some difference between them.
| LinkedList | ArrayList |
|---|---|
Implements List, Queue, and Deque interfaces. | Implements List interface. |
| Stores 3 values (previous address, data, and next address) in a single position. | Stocke une valeur unique dans une seule position. |
| Fournit l'implémentation de liste à double lien. | Fournit une implémentation de tableau redimensionnable. |
Chaque fois qu'un élément est ajouté, prevet l' nextadresse est modifiée. | 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 du début à l'élément. | Peut accéder de manière aléatoire aux éléments à l'aide d'index. |
Remarque : Nous pouvons également créer une LinkedList à l'aide d'interfaces en Java. Par exemple,
// create linkedlist using List List animals1 = new LinkedList(); // creating linkedlist using Queue Queue animals2 = new LinkedList(); // creating linkedlist using Deque Deque animals3 = new LinkedList();
Ici, si la LinkedList est créée à l'aide d'une seule interface, nous ne pouvons pas utiliser les méthodes fournies par d'autres interfaces. Autrement dit, les animaux1 ne peuvent pas utiliser de méthodes spécifiques aux interfaces Queueet Deque.
