linked list java linked list implementation java examples
Ce didacticiel explique ce qu'est une structure de données de liste liée en Java et comment créer, initialiser, implémenter, parcourir, inverser et trier une liste liée Java:
En Java, une LinkedList est une structure de données qui stocke des éléments dans un emplacement non contigu. C'est une structure de données linéaire.
Chaque élément de données est appelé un «nœud» et chaque nœud a une partie de données et une partie d'adresse. La partie adresse stocke le lien vers le nœud suivant dans LinkedList.
=> Visitez ici pour voir la série de formations Java pour tous.
Ce que vous apprendrez:
- LinkedList en Java
- Classe Java LinkedList
- Comment créer une liste liée en Java
- Implémentation de liste liée en Java
- Traverser / Imprimer la liste liée en Java
- Méthodes LinkedList
- Inverser la liste liée en Java
- Trier une liste liée en Java
- Supprimer les doublons
- Liste liée circulaire en Java
- Liste LinkedList Java 8
- Questions fréquemment posées
- Conclusion
LinkedList en Java
Ci-dessous, la disposition générale de LinkedList:
Comme le montre la représentation ci-dessus de LinkedList, chaque élément de LinkedList est le «Node». Chaque nœud a deux parties, la première partie stocke les données et la seconde partie a une référence ou un pointeur ou une adresse du nœud suivant dans LinkedList.
comment appeler une fonction en python principal
Cette disposition est nécessaire car les données de LinkedList sont stockées dans des emplacements non contigus, contrairement aux tableaux.
La «tête» de la LinkedList est un pointeur qui contient l'adresse du premier élément de la LinkedList. Le dernier nœud de la LinkedList est la queue. Comme le montre la figure ci-dessus, la partie adresse du dernier nœud de la LinkedList est définie sur «Null» indiquant la fin de la LinkedList.
Le diagramme ci-dessus représente un ' Liste à lien unique »Qui stocke uniquement l'adresse du nœud suivant dans LinkedList.
Il existe une autre version appelée ' Liste doublement liée ”Dont chaque nœud comprend trois parties:
- Adresse ou référence ou pointeur vers l'élément précédent dans LinkedList.
- Partie données
- Adresse ou référence ou pointeur vers l'élément suivant dans LinkedList.
L'adresse précédente du premier élément de LinkedList sera définie sur Null tandis que le pointeur suivant du dernier élément de LinkedList sera défini sur Null.
Représentation de la liste doublement liée:
Comme le montre la représentation ci-dessus, chaque nœud de la liste doublement liée a des pointeurs vers son nœud précédent et suivant (ainsi représentés sans flèches). Le pointeur précédent du premier nœud pointe vers null tandis que le pointeur suivant du dernier nœud pointe vers null.
Dans ce tutoriel LinkedList, nous traiterons principalement de la liste liée individuellement. Nous discuterons de la liste doublement chaînée dans notre prochain tutoriel.
Classe Java LinkedList
En Java, la liste chaînée est implémentée par le ' LinkedList ' classer. Cette classe appartient au ' java.util ' paquet. La classe LinkedList implémente les interfaces List et Deque et hérite de la classe AbstractList.
Ci-dessous, la hiérarchie des classes de la classe LinkedList.
Le diagramme ci-dessus montre la hiérarchie de la classe LinkedList. Comme indiqué, la classe LinkedList implémente les interfaces List et Deque.
Comme déjà mentionné, la classe LinkedList fait partie du ' java.util ' paquet. Par conséquent, vous devriez être en mesure d'utiliser la classe LinkedList dans votre programme en incluant l'une des instructions suivantes dans votre programme.
import java.util.*;
Ou
import java.util.LinkedList;
Donc, sur la base de la hiérarchie ci-dessus, une définition typique de la classe LinkedList est la suivante:
public class LinkedList extends AbstractSequentialList implements List, Deque, Cloneable, Serializable
Vous trouverez ci-dessous quelques-unes des caractéristiques de la classe LinkedList dont vous devez vous souvenir:
- Cette classe n'est pas synchronisée.
- Il permet des valeurs en double.
- Conserve l'ordre d'insertion.
- Comme les éléments ne doivent pas être déplacés pendant le déplacement, la manipulation des éléments qui s'y trouvent est plus rapide.
- Cette classe peut être utilisée pour implémenter une pile, une file d'attente et une liste.
Comment créer une liste liée en Java
Avant de passer à la création d'une liste liée en Java, examinons d'abord un nœud de liste liée en Java.
Comme déjà discuté, une liste chaînée se compose de nœuds. Ainsi, en Java, nous pouvons représenter une LinkedList comme une classe avec son Node comme une classe distincte. Par conséquent, cette classe aura une référence au type Node.
Ceci est montré comme ci-dessous:
class LinkedList { Node head; // list head //node - linkedlist class Node { int data; Node next; Node(int d) { data = d; } //constructor to create a new node } }
Pour créer un objet de type LinkedList, il existe deux constructeurs principaux comme suit:
# 1) LinkedList ()
La syntaxe générale de ce constructeur est:
LinkedList linkedList = new LinkedList();
L'instruction ci-dessus crée une LinkedList vide.
Par exemple,
LinkedList l_list = new LinkedList();
Cela créera une liste chaînée vide nommée l_list.
# 2) LinkedList (Collection c)
La syntaxe générale est:
LinkedList linkedList = new LinkedList (Collection c);
L'instruction ci-dessus crée une LinkedList avec des éléments de la collection c comme éléments initiaux.
Comme les autres structures de données de liste que nous avons déjà vues, la liste chaînée peut également être initialisée en utilisant la méthode add, la méthode Arrays.asList () ou en utilisant le constructeur avec la collection comme argument.
Implémentation de liste liée en Java
Vous trouverez ci-dessous un exemple simple de structure de données LinkedList en Java. Dans cet exemple d'implémentation, nous utiliserons la méthode add et la méthode asList pour initialiser les objets LinkedList.
import java.util.*; public class Main{ public static void main(String() args) { //create a LinkedList object and initialize it with Array elements converted to list LinkedList intList = new LinkedList<>(Arrays.asList(10,20,30,40,50)); //print the LinkedList just created System.out.println('Contents of first LinkedList: ' + intList); //create an empty list LinkedList colorsList = new LinkedList<>(); //add elements to the linkedList using add method. colorsList.add('Red'); colorsList.add('Green'); colorsList.add('Blue'); colorsList.add('Cyan'); colorsList.add('Magenta'); // print the LinkedList System.out.println('
Contents of second LinkedList: ' + colorsList); } }
Production:
Contenu de la première LinkedList: (10, 20, 30, 40, 50)
Contenu de la deuxième LinkedList: (Rouge, Vert, Bleu, Cyan, Magenta)
Le programme ci-dessus montre la création et l'initialisation de la LinkedList. Tout d'abord, nous créons une LinkedList de type Integer et fournissons un tableau d'entiers convertis en liste à l'aide de la méthode asList comme valeurs initiales pour LinkedList.
Ensuite, nous créons une LinkedList vide de type String, puis en utilisant la méthode add, nous ajoutons des valeurs à LinkedList.
Enfin, nous affichons les deux objets LinkedList sous forme de chaîne.
Traverser / Imprimer la liste liée en Java
Pour imprimer le contenu ou effectuer des opérations sur les éléments de la LinkedList, vous devez parcourir ses éléments. Nous avons déjà vu ces méthodes dans nos précédents tutoriels. Dans cette section, nous discuterons des exemples de chacun par rapport à LinkedList.
Utilisation de la boucle for
import java.util.LinkedList; class Main { public static void main(String() args) { // Create a LinkedList and initialize it LinkedList colorList = new LinkedList<>(); colorList.add('Red'); colorList.add('Green'); colorList.add('Blue'); // Using for loop,print the contents of the LinkedList System.out.println('LinkedList elements using for loop:'); for(int i=0; i Production:
Éléments LinkedList utilisant la boucle for:
Rouge vert bleu
Utilisation de la boucle forEach
import java.util.LinkedList; class Main { public static void main(String() args) { // Create a LinkedList and initialize it LinkedList colorList = new LinkedList<>(); colorList.add('Red'); colorList.add('Green'); colorList.add('Blue'); // Using forEach loop,print the contents of the LinkedList System.out.println('LinkedList elements using forEach loop:'); for(String color:colorList) { System.out.print(color + ' '); } } }
Production:
Éléments LinkedList utilisant la boucle forEach:
Rouge vert bleu
Utiliser Iterator
import java.util.*; public class Main{ public static void main(String args()){ //declare a LinkedList object LinkedList l_list=new LinkedList(); //Add elements to LinkedList l_list.add('Red'); l_list.add('Green'); l_list.add('Blue'); l_list.add('Yellow'); //declare an iterator for the LinkedList Iterator itr=l_list.iterator(); System.out.println('The contents of Linked List:'); //Iterate through the LinkedList using Iterator and print its elements while(itr.hasNext()){ System.out.print(itr.next() + ' '); } } }
Production:
Le contenu de la liste liée:
Rouge Vert Bleu Jaune
questions d'entretien du centre d'assistance de niveau d'entrée
Méthodes LinkedList
La classe LinkedList fournit une API qui prend en charge diverses méthodes pour manipuler la liste Linked. Nous avons tabularisé les méthodes dans l'API LinkedList ci-dessous.
Nous discuterons des principales opérations / méthodes dans la section suivante.
Méthode Prototype Description Dégager vide clair () Supprime tous les éléments de la liste. Ajouter booléen ajouter (E e) Ajouter un élément spécifié à LinkedList void add (index int, élément E) Ajouter un élément à l'index donné dans LinkedList Tout ajouter booléen addAll (Collection c) Ajoute les éléments de la collection donnée c à la fin de LinkedList. booléen addAll (index int, Collection c) Ajoute les éléments d'une collection donnée c à l'index spécifié dans LinkedList addFirst void addFirst (E e) Ajoutez l'élément donné comme premier élément à LinkedList. addLast void addLast (E e) Ajoutez l'élément donné à la fin de la liste. Cloner Clone d'objet () Crée une copie superficielle de LinkedList Contient Boolean contient (Object o) Vérifie si la liste contient des éléments spécifiés; si oui renvoie vrai. descendingIterator Itérateur descendantIterator () Renvoie un itérateur ordonné inversé pour LinkedList. Élément Élément E () Renvoie l'élément en tête de la liste. Obtenir E get (index int) Obtient l'élément à l'index spécifié. getFirst E getFirst () Récupère le premier élément de LinkedList. getLast E getLast () Récupère le dernier élément de LinkedList. Indice de Int indexOf (objet o) Trouvez l'index de la première occurrence des éléments donnés dans la liste et renvoyez l'index. -1 si élément non trouvé. lastIndexOf Int lastIndexOf (objet o) Renvoie la position de la dernière occurrence de l'élément donné dans la LinkedList; -1 si l'élément donné n'est pas présent listIterator ListIterator listIterator (index int) Renvoie le listIterator à partir de l'index spécifié dans la liste liée. Offre offre booléenne (E e) Ajoute l'élément donné comme dernier élément (queue) dans LinkedList. offrePremier Offre booléenne First (E e) Ajoute l'élément donné comme premier élément dans LinkedList. offreDernière Offre booléenne Last (E e) Ajoutez l'élément e donné à la fin de la LinkedList. Coup d'oeil E coup d'oeil () Renvoie la tête de la liste sans la supprimer. coup d'oeil E coup d'oeil d'abord () Renvoie le premier élément de la liste. renvoie null si la liste est vide. peekLast E peekLast () Renvoie le dernier élément ou nul si la liste est vide. Il ne supprime pas l'élément. Sondage Sondage E () Renvoie la tête de la LinkedList et la supprime également. pollFirst E pollFirst () Renvoie et supprime le premier élément de la liste; renvoie null si la liste est vide. sondageDernier E pollDernier () Renvoie et supprime le dernier élément de la liste; renvoie null si la liste est vide. Pop E pop () Extrait l'élément de la représentation de pile de LinkedList. Pousser Poussée du vide (E e) Pousse ou insère un élément dans la représentation de pile de LinkedList. Supprimer E supprimer () Supprime et renvoie la tête de LinkedList. E supprimer (index int) Supprime l'élément à l'index donné de LinkedList. boolean remove (objet o) Supprime la première occurrence de l'élément donné de LinkedList. supprimer d'abord E removeFirst () Renvoie et supprime le premier élément de la liste. removeFirstOccurence booléen removeFirstOccurrence (Object o) Supprime la première occurrence de l'élément donné de la liste lorsque la liste est parcourue de haut en bas. removeLast E removeLast () Renvoie le dernier élément de la LinkedList et le supprime également. removeLastOccurence booléen removeLastOccurrence (Object o) Supprime la dernière occurrence de l'élément donné de LinkedList lorsqu'il est parcouru de la tête à la queue Ensemble Ensemble E (index int, élément E) Définit l'élément donné à l'index donné. Remplace l'élément actuel par new. Taille Taille int () Renvoie la taille ou le nombre d'éléments dans la LinkedList toArray Object () toArray () Convertit la LinkedList en un tableau contenant tous les éléments de la liste dans l'ordre approprié T () toArray (T () a) Convertit LinkedList en un tableau avec un type d'exécution identique à l'argument a.
Le programme Java ci-dessous illustre les différentes méthodes que nous avons répertoriées ci-dessus.
import java.util.*; public class Main { public static void main(String args()) { //create a linked list LinkedList l_list = new LinkedList(); // Add elements to linkedList using various add methods l_list.add('B'); l_list.add('C'); l_list.addLast('G'); l_list.addFirst('A'); l_list.add(3, 'D'); l_list.add('E'); l_list.add('F'); //print the linkedList System.out.println('Linked list : ' + l_list); //Create and initialize an ArrayList ArrayList aList = new ArrayList<>(); aList.add('H'); aList.add('I'); //add the ArrayList to linkedList using addAll method l_list.addAll(aList); //print the linkedList System.out.println('Linked list after adding ArrayList contents: ' + l_list); // use various remove methods to remove elements from linkedList l_list.remove('B'); l_list.remove(3); l_list.removeFirst(); l_list.removeLast(); //print the altered list System.out.println('Linked list after deletion: ' + l_list); // use contains method to check for an element in the linkedList boolean ret_value = l_list.contains('G'); //print the results of contains method if(ret_value) System.out.println('List contains the element 'G' '); else System.out.println('List doesn't contain the element 'G''); // use size methods to return Number of elements in the linked list int size = l_list.size(); System.out.println('Size of linked list = ' + size); // Get and set elements from linked list Object element = l_list.get(3); System.out.println('Element returned by get() : ' + element); l_list.set(3, 'J'); System.out.println('Linked list after change : ' + l_list); //convert linkedList to Array using toArray methods String () list_array = l_list.toArray(new String(l_list.size())); System.out.println('Array obtained from linked List:' + Arrays.toString(list_array)); } }
Production:
Liste liée: (A, B, C, D, G, E, F)
Liste liée après l'ajout du contenu ArrayList: (A, B, C, D, G, E, F, H, I)
Liste liée après suppression: (C, D, E, F, H)
La liste ne contient pas l’élément «G»
Taille de la liste liée = 5
Élément renvoyé par get (): F
Liste liée après modification: (C, D, E, J, H)
Tableau obtenu à partir de la liste liée: (C, D, E, J, H)
Le programme ci-dessus montre différentes méthodes de la classe LinkedList. Tout d'abord, nous déclarons une LinkedList de type String. Ensuite, nous utilisons différentes versions de la méthode add comme add, andFirst, addLast, addAll, etc. pour remplir la LinkedList avec des valeurs.
Ici, nous pouvons ajouter l'élément directement à la fin de la liste ou ajouter l'élément à une position spécifiée dans la liste.
Nous utilisons également la méthode addFirst pour ajouter un élément au début de la liste et addLast pour ajouter un élément à la fin de la liste. Ensuite, nous effectuons des opérations de suppression sur la LinkedList comme remove, removeFirst, removeLast, etc.
Pour la méthode remove, nous pouvons soit spécifier l'élément à supprimer, soit spécifier l'index ou la position dans la LinkedList à laquelle l'élément doit être supprimé. Les méthodes removeFirst et removeLast suppriment respectivement le premier et le dernier élément de la liste.
Ensuite, nous recherchons dans la liste un élément particulier à l'aide de la méthode contains. Ensuite, nous utilisons la méthode size () pour récupérer la taille ou la longueur de LinkedList. Ensuite, nous utilisons les méthodes get / set pour récupérer la valeur à un index particulier dans la liste, puis remplacer une valeur à une position spécifiée dans la liste.
Enfin, nous convertissons la LinkedList en Array à l'aide de la méthode toArray.
Inverser la liste liée en Java
Pour inverser une liste chaînée en Java, nous utilisons la méthode «descendingIterator ()» qui renvoie un itérateur inversé pour la liste. Nous pouvons ensuite utiliser cet itérateur pour parcourir la liste et afficher les éléments.
Le programme ci-dessous inverse la liste liée à l'aide de la méthode descendingIterator ().
import java.util.*; public class Main{ public static void main(String args()){ //create a LinkedList object LinkedList l_list=new LinkedList(); l_list.add('Pune'); l_list.add('Mumbai'); l_list.add('Nagpur'); System.out.println('Linked List : ' + l_list); System.out.println('Linked List in reverse order:'); //use descendingIterator method to get a reverse iterator Iterator iter=l_list.descendingIterator(); //traverse the list using iterator and print the elements. while(iter.hasNext()) { System.out.print(iter.next() + ' '); } } }
Production:
Liste liée: (Pune, Mumbai, Nagpur)
Liste liée dans l'ordre inverse:
Nagpur Mumbai Pune
Dans le programme ci-dessus, nous déclarons une liste chaînée, puis nous l'imprimons. Ensuite, nous obtenons un itérateur inversé, puis parcourons la liste en l'utilisant et affichons chaque élément. La sortie affiche le contenu de la liste liée, d'abord dans l'ordre dans lequel les éléments sont ajoutés, puis la sortie affiche le contenu dans l'ordre inverse.
Trier une liste liée en Java
Les objets de classe LinkedList peuvent être triés à l'aide de la méthode Collections.sort (). Cette méthode propose deux versions avec ou sans utilisation d'un comparateur. Lorsque la méthode Collections.sort () est appelée sans comparateur, la collection est triée dans l'ordre naturel.
Quand le comparateur est utilisé avec cette méthode, nous pouvons définir nos propres critères de tri en remplaçant la méthode compareTo.
Le programme Java ci-dessous trie une LinkedList à l'aide de Collections.sort (). Ici, nous trions les tableaux en utilisant un ordre naturel ainsi qu'en utilisant un comparateur.
import java.util.*; public class Main{ public static void main(String args()) { // create and initialize the LinkedList object LinkedList l_list = new LinkedList<>(); l_list.add('Jan'); l_list.add('Feb'); l_list.add('Mar'); l_list.add('Apr'); l_list.add('May'); l_list.add('Jun'); //print original unsorted linkedlist System.out.println('Original LinkedList (unsorted): ' + l_list); // sort LinkedList with Collecitons.sort() method in natural order Collections.sort(l_list); System.out.println('
LinkedList (sorted in natural order): ' + l_list); // sort LinkedList using Collection.sort() and Comparator in Java Collections.sort(l_list, new Comparator() { @Override public int compare(String s1, String s2) { return s1.length() - s2.length(); } } ); System.out.println('LinkedList (sorted using Comparator): ' + l_list); } }
Production:
LinkedList d'origine (non triée): (janvier, février, mars, avril, mai, juin)
LinkedList (triée par ordre naturel): (avril, février, janvier, juin, mars, mai)
LinkedList (trié à l'aide du comparateur): (avril, février, janvier, juin, mars, mai)
Supprimer les doublons
Pour supprimer les doublons, vous devez traverser chaque nœud et le comparer avec le nœud suivant. Si les deux nœuds sont identiques, nous sautons un nœud et passons au suivant.
De cette manière, après avoir traversé chaque nœud et se débarrasser des nœuds en double, nous obtiendrons la liste résultante qui est sans éléments en double.
Ci-dessous, un programme Java pour supprimer les doublons.
class LinkedList_Duplicate { //A class to represent node in linkedlist class Node{ int data; Node next; public Node(int data) { this.data = data; this.next = null; } } //Initially the head and tail of the linked list set to null public Node head = null; public Node tail = null; //add a new node to the linkedlist public void addNode(int data) { //Create new node Node newNode = new Node(data); //If list is empty set head and tail to new node if(head == null) { head = newNode; tail = newNode; } else { // add newNode after the tail tail.next = newNode; //newNode is now the tail or last element tail = newNode; } } //scans the linkedlist and removes duplicate nodes public void removeDuplicateNodes() { //Head is the current node Node current = head, index = null, temp = null; //head = null means list is empty if(head == null) { return; } //traverse through the list else { while(current != null){ //temp node points to previous node to index. temp = current; //Index will point to node next to current index = current.next; while(index != null) { //Check if current node's data is equal to index node's data if(current.data == index.data) { //since node is duplicate skip index and point to next node temp.next = index.next; } else { //Temp will point to previous node of index. temp = index; } index = index.next; } current = current.next; } } } //print the linked list public void print() { //Node current will point to head Node current = head; if(head == null) { System.out.println('List is empty'); return; } while(current != null) { //Print each node by incrementing pointer System.out.print(current.data + ' '); current = current.next; } System.out.println(); } }class Main{ public static void main(String() args) { LinkedList_Duplicate l_List = new LinkedList_Duplicate(); //Add data to the list l_List.addNode(1); l_List.addNode(1); l_List.addNode(2); l_List.addNode(3); l_List.addNode(5); l_List.addNode(2); l_List.addNode(1); l_List.addNode(1); //print the original list System.out.println('Original Linkedlist: '); l_List.print(); //Removes duplicate nodes l_List.removeDuplicateNodes(); //print the altered list without duplicates System.out.println('LinkedList after removing duplicates: '); l_List.print(); } }
Production:
Linkedlist d'origine:
1 1 2 3 5 2 1 1
LinkedList après avoir supprimé les doublons:
1 2 3 5
questions et réponses d'entretien qtp depuis 4 ans d'expérience
Dans le programme ci-dessus, nous avons une classe de liste liée créée pour supprimer les doublons. Nous avons également une classe pour définir chaque nœud. En d'autres termes, les nœuds de la liste sont les objets de ce nœud de classe. Nous avons une méthode pour ajouter le nœud à une liste liée.
Ensuite, dans la méthode removeDuplicate, nous traversons chaque nœud de la liste liée en commençant par la tête et comparons chaque nœud suivant pour le doublon. Si un doublon est trouvé, nous sautons ce nœud et passons au nœud suivant.
De cette façon, l'ist est construit en sautant les nœuds en double et la liste modifiée est imprimée en utilisant la méthode print ().
Liste liée circulaire en Java
Une liste liée circulaire est une liste dont la queue ou le dernier nœud est connecté à la tête ou au premier nœud.
Le diagramme ci-dessous montre la liste circulaire liée en Java.
Comme indiqué dans le diagramme ci-dessus, la partie adresse du dernier nœud ou de la queue de la liste liée n'est pas définie sur null. Au lieu de cela, il pointe vers le premier nœud ou tête de la liste formant ainsi une liste chaînée circulaire.
Le programme ci-dessous implémente une liste liée circulaire dans laquelle nous devons manipuler des nœuds individuels de la liste liée.
class CircularLinkedList { //Node definition for circular linked list public class Node{ int data; Node next; public Node(int data) { this.data = data; } } //Initially head and tail pointers point to null public Node head = null; public Node tail = null; //add new node to the circular linked list public void add(int data){ //Create new node Node newNode = new Node(data); //check if list is empty if(head == null) { //head and tail point to same node if list is empty head = newNode; tail = newNode; newNode.next = head; } else { //tail points to new node if list is not empty tail.next = newNode; //New node becomes new tail. tail = newNode; //tail points back to head tail.next = head; } } //Display the nodes in circular linked list public void displayList() { Node current = head; if(head == null) { System.out.println('The List is empty'); } else { System.out.println('Circular linked list nodes: '); do{ //Print each node of the linked list System.out.print(current.data + ' '); current = current.next; }while(current != head); System.out.println(); } } } class Main{ public static void main(String() args) { //create a CircularLinkedList object CircularLinkedList c_list = new CircularLinkedList(); //Add data to the list c_list.add(10); c_list.add(20); c_list.add(30); c_list.add(40); //Display the nodes in circular linked list c_list.displayList(); } }
Production:
Nœuds de liste liée circulaire:
10 20 30 40
Liste LinkedList Java 8
Bien qu'il n'y ait plus de fonctionnalités ajoutées spécifiquement à la classe LinkedList dans Java 8, il a toujours introduit des flux pour manipuler les données.
Le programme ci-dessous montre l'utilisation du flux Java 8 pour afficher LinkedList.
import java.util.LinkedList; import java.util.List; public class Main { public static void main(String() args) { //create a LinkedList and initialize it to values List colorsList = new LinkedList<>(); colorsList.add('Red'); colorsList.add('Green'); colorsList.add('Blue'); colorsList.add('Cyan'); colorsList.add('Magenta'); //convert List to stream & print it System.out.println('The contents of LinkedList:'); colorsList.stream().forEach(System.out::println); } }
Production:
Le contenu de LinkedList:
Rapporter
Vert
Bleu
Cyan
Magenta
Questions fréquemment posées
Q # 1) Quand la liste liée est-elle utilisée en Java?
Répondre: Comme il est plus rapide que les collections comme ArrayList dans les opérations de modification, il doit être utilisé dans les applications qui nécessitent des opérations d'ajout / suppression fréquentes. Pour les applications qui ont principalement des données en lecture seule, ArrayList ou des collections similaires peuvent être utilisées.
Q # 2) Qu'est-ce que ListNode?
Répondre: Un ListNode est une classe de base associée à une liste chaînée en Java et représente des informations associées à un seul élément ou à un nœud. Chaque ListNode se compose de données et d'un pointeur ou d'une référence vers l'élément suivant.
Q # 3) La liste liée autorise-t-elle les valeurs nulles?
Répondre: Oui, la liste liée autorise n'importe quel nombre de valeurs nulles.
Q # 4) Quels sont les avantages d'une liste liée?
Réponse: Certains des avantages sont:
- Les opérations de manipulation comme l'ajout, la suppression y sont plus rapides.
- Il n'est pas nécessaire de pré-allouer de la mémoire pour une liste chaînée et il en résulte une utilisation efficace de la mémoire.
- Il offre un temps d'accès plus rapide et sans frais supplémentaires pour la mémoire, et peut être étendu en temps constant.
- C'est une structure de données dynamique
- Augmente et diminue au moment de l'exécution en fonction des valeurs ajoutées ou supprimées.
Q # 5) Quelle est l'application de la liste liée?
Réponse: Il est principalement utilisé dans les applications suivantes:
- Pour implémenter la fonctionnalité «Annuler» dans des logiciels tels que MS-Word, Photoshop, etc.
- Pour implémenter des structures de données telles que pile et file d'attente.
- Nous pouvons également implémenter des graphiques en utilisant une liste chaînée.
- Pour le hachage de compartiment, chaque compartiment peut être implémenté sous forme de liste liée.
Q # 6) Quelles sont les limites d'une liste liée?
Réponse: Certaines des limitations sont:
- Avec un pointeur supplémentaire pour contenir la référence de l'élément suivant dans chaque nœud, la mémoire utilisée est bien plus que des tableaux.
- Il s'agit d'une structure de données à accès strictement séquentiel, par conséquent les nœuds de la liste liée doivent toujours être lus depuis le début.
- Il est difficile de le parcourir en arrière, en particulier les listes à lien unique.
- Étant donné que les nœuds sont stockés dans des emplacements non contigus, le temps requis pour l'accès peut être élevé.
Conclusion
Dans ce didacticiel, nous avons appris la structure de base des données de liste chaînée. Ensuite, nous sommes passés à la classe java.util.LinkedList fournie en Java. Nous avons discuté de cette classe en détail, y compris ses constructeurs, méthodes, etc.
Nous avons également discuté de certaines opérations spéciales liées aux listes liées telles que le tri, l'inversion d'une liste, la suppression des doublons, la liste liée circulaire, etc.
Dans notre prochain tutoriel, nous aborderons les fonctionnalités spécifiques de la liste à double chaînage.
=> Consultez le guide de formation Java complet ici.
lecture recommandée
- Liste doublement liée en Java - Exemples d'implémentation et de code
- Liste Java - Comment créer, initialiser et utiliser une liste en Java
- Méthodes de liste Java - Trier la liste, contient, ajouter une liste, supprimer une liste
- Algorithme de recherche binaire en Java - Implémentation et exemples
- Tri par insertion en Java - Algorithme de tri par insertion et exemples
- Tutoriel sur l'interface Java et les classes abstraites avec des exemples
- Structure de données de liste liée en C ++ avec illustration
- Liste secrète pour tableau et autres collections en Java