Prérequis: Comme les tableaux, la liste chaînée est une structure de données linéaire. Contrairement aux tableaux, les éléments de liste chaînée ne sont pas stockés à l'emplacement contigu, les éléments sont liés à l'aide de pointeurs comme indiqué ci-dessous.

Comme les tableaux, la liste chaînée est une structure de données linéaire. Contrairement aux tableaux, les éléments de liste chaînée ne sont pas stockés à l'emplacement contigu, les éléments sont liés à l'aide de pointeurs comme indiqué ci-dessous.

En Java, LinkedList peut être représenté comme une classe et un Node comme une classe distincte. La classe LinkedList contient une référence de type classe Node.

Java

class> LinkedList {> > Node head;> // head of list> > /* Linked list Node*/> > static> class> Node {> > int> data;> > Node next;> > // Constructor to create a new node> > // Next is by default initialized> > // as null> > Node(> int> d) { data = d; }> > }> }>

Création et insertion :

Dans cet article, l'insertion dans la liste se fait à la fin, c'est-à-dire que le nouveau nœud est ajouté après le dernier nœud de la liste chaînée donnée. Par exemple, si la liste chaînée donnée est 5->10->15->20->25 et que 30 doit être inséré, alors la liste chaînée devient 5->10->15->20->25->30. .
Étant donné qu'une liste chaînée est généralement représentée par son pointeur principal, il est nécessaire de parcourir la liste jusqu'au dernier nœud, puis de remplacer l'avant-dernier nœud par le nouveau nœud.

Mise en œuvre:

Java

import> java.io.*;> > // Java program to implement> // a Singly Linked List> public> class> LinkedList {> > > Node head;> // head of list> > > // Linked list Node.> > // This inner class is made static> > // so that main() can access it> > static> class> Node {> > > int> data;> > Node next;> > > // Constructor> > Node(> int> d)> > {> > data = d;> > next => null> ;> > }> > }> > > // Method to insert a new node> > public> static> LinkedList insert(LinkedList list,> int> data)> > {> > // Create a new node with given data> > Node new_node => new> Node(data);> > > > // If the Linked List is empty,> > // then make the new node as head> > if> (list.head ==> null> ) {> > list.head = new_node;> > }> > else> {> > // Else traverse till the last node> > // and insert the new_node there> > Node last = list.head;> > while> (last.next !=> null> ) {> > last = last.next;> > }> > > // Insert the new_node at last node> > last.next = new_node;> > }> > > // Return the list by head> > return> list;> > }> > > // Method to print the LinkedList.> > public> static> void> printList(LinkedList list)> > {> > Node currNode = list.head;> > > System.out.print(> 'LinkedList: '> );> > > // Traverse through the LinkedList> > while> (currNode !=> null> ) {> > // Print the data at current node> > System.out.print(currNode.data +> ' '> );> > > // Go to next node> > currNode = currNode.next;> > }> > }> > > // Driver code> > public> static> void> main(String[] args)> > {> > /* Start with the empty list. */> > LinkedList list => new> LinkedList();> > > //> > // ******INSERTION******> > //> > > // Insert the values> > list = insert(list,> 1> );> > list = insert(list,> 2> );> > list = insert(list,> 3> );> > list = insert(list,> 4> );> > list = insert(list,> 5> );> > list = insert(list,> 6> );> > list = insert(list,> 7> );> > list = insert(list,> 8> );> > > // Print the LinkedList> > printList(list);> > }> }>

Sortir

LinkedList: 1 2 3 4 5 6 7 8 

Traversée : Pour le parcours, vous trouverez ci-dessous une fonction à usage général printList() qui imprime n'importe quelle liste donnée en parcourant la liste du nœud principal au dernier.

Mise en œuvre:

Java

import> java.io.*;> // Java program to implement> // a Singly Linked List> public> class> LinkedList {> > Node head;> // head of list> > // Linked list Node.> > // Node is a static nested class> > // so main() can access it> > static> class> Node {> > int> data;> > Node next;> > // Constructor> > Node(> int> d)> > {> > data = d;> > next => null> ;> > }> > }> > // Method to insert a new node> > public> static> LinkedList insert(LinkedList list,> > int> data)> > {> > // Create a new node with given data> > Node new_node => new> Node(data);> > new_node.next => null> ;> > // If the Linked List is empty,> > // then make the new node as head> > if> (list.head ==> null> ) {> > list.head = new_node;> > }> > else> {> > // Else traverse till the last node> > // and insert the new_node there> > Node last = list.head;> > while> (last.next !=> null> ) {> > last = last.next;> > }> > // Insert the new_node at last node> > last.next = new_node;> > }> > // Return the list by head> > return> list;> > }> > // Method to print the LinkedList.> > public> static> void> printList(LinkedList list)> > {> > Node currNode = list.head;> > System.out.print(> 'LinkedList: '> );> > // Traverse through the LinkedList> > while> (currNode !=> null> ) {> > // Print the data at current node> > System.out.print(currNode.data +> ' '> );> > // Go to next node> > currNode = currNode.next;> > }> > }> > // **************MAIN METHOD**************> > // method to create a Singly linked list with n nodes> > public> static> void> main(String[] args)> > {> > /* Start with the empty list. */> > LinkedList list => new> LinkedList();> > //> > // ******INSERTION******> > //> > // Insert the values> > list = insert(list,> 1> );> > list = insert(list,> 2> );> > list = insert(list,> 3> );> > list = insert(list,> 4> );> > list = insert(list,> 5> );> > list = insert(list,> 6> );> > list = insert(list,> 7> );> > list = insert(list,> 8> );> > // Print the LinkedList> > printList(list);> > }> }>

Sortir

LinkedList: 1 2 3 4 5 6 7 8 

Suppression par clé :

Le processus de suppression peut être compris comme suit :

Être fait:

Étant donné une « clé », supprimez la première occurrence de cette clé dans la liste chaînée .

Comment faire:

Pour supprimer un nœud de la liste chaînée, procédez comme suit.

1. Rechercher la clé pour sa première occurrence dans la liste
2. Désormais, n’importe laquelle des 3 conditions peut être présente :
   • Cas 1 : La clé se trouve au tête
     1. Dans ce cas, remplacez la tête du nœud par le nœud suivant de la tête actuelle.
        
     2. Libérez la mémoire du nœud principal remplacé.
   • Cas 2 : La clé se retrouve au milieu ou en dernier, sauf au niveau du tête
     1. Dans ce cas, recherchez le nœud précédent du nœud à supprimer.
     2. Remplacez le nœud suivant du nœud précédent par le nœud suivant du nœud actuel.
     3. Libérez la mémoire du nœud remplacé.
   • Cas 3 : La clé est introuvable dans la liste
     1. Dans ce cas, aucune opération n’est nécessaire.

Mise en œuvre:

Java

import> java.io.*;> // Java program to implement> // a Singly Linked List> public> class> LinkedList {> > Node head;> // head of list> > // Linked list Node.> > // Node is a static nested class> > // so main() can access it> > static> class> Node {> > int> data;> > Node next;> > // Constructor> > Node(> int> d)> > {> > data = d;> > next => null> ;> > }> > }> > // Method to insert a new node> > public> static> LinkedList insert(LinkedList list,> > int> data)> > {> > // Create a new node with given data> > Node new_node => new> Node(data);> > new_node.next => null> ;> > // If the Linked List is empty,> > // then make the new node as head> > if> (list.head ==> null> ) {> > list.head = new_node;> > }> > else> {> > // Else traverse till the last node> > // and insert the new_node there> > Node last = list.head;> > while> (last.next !=> null> ) {> > last = last.next;> > }> > // Insert the new_node at last node> > last.next = new_node;> > }> > // Return the list by head> > return> list;> > }> > // Method to print the LinkedList.> > public> static> void> printList(LinkedList list)> > {> > Node currNode = list.head;> > System.out.print(> 'LinkedList: '> );> > // Traverse through the LinkedList> > while> (currNode !=> null> ) {> > // Print the data at current node> > System.out.print(currNode.data +> ' '> );> > // Go to next node> > currNode = currNode.next;> > }> > System.out.println();> > }> > // **************DELETION BY KEY**************> > // Method to delete a node in the LinkedList by KEY> > public> static> LinkedList deleteByKey(LinkedList list,> > int> key)> > {> > // Store head node> > Node currNode = list.head, prev => null> ;> > //> > // CASE 1:> > // If head node itself holds the key to be deleted> > if> (currNode !=> null> && currNode.data == key) {> > list.head = currNode.next;> // Changed head> > // Display the message> > System.out.println(key +> ' found and deleted'> );> > // Return the updated List> > return> list;> > }> > //> > // CASE 2:> > // If the key is somewhere other than at head> > //> > // Search for the key to be deleted,> > // keep track of the previous node> > // as it is needed to change currNode.next> > while> (currNode !=> null> && currNode.data != key) {> > // If currNode does not hold key> > // continue to next node> > prev = currNode;> > currNode = currNode.next;> > }> > // If the key was present, it should be at currNode> > // Therefore the currNode shall not be null> > if> (currNode !=> null> ) {> > // Since the key is at currNode> > // Unlink currNode from linked list> > prev.next = currNode.next;> > // Display the message> > System.out.println(key +> ' found and deleted'> );> > }> > //> > // CASE 3: The key is not present> > //> > // If key was not present in linked list> > // currNode should be null> > if> (currNode ==> null> ) {> > // Display the message> > System.out.println(key +> ' not found'> );> > }> > // return the List> > return> list;> > }> > // **************MAIN METHOD**************> > // method to create a Singly linked list with n nodes> > public> static> void> main(String[] args)> > {> > /* Start with the empty list. */> > LinkedList list => new> LinkedList();> > //> > // ******INSERTION******> > //> > // Insert the values> > list = insert(list,> 1> );> > list = insert(list,> 2> );> > list = insert(list,> 3> );> > list = insert(list,> 4> );> > list = insert(list,> 5> );> > list = insert(list,> 6> );> > list = insert(list,> 7> );> > list = insert(list,> 8> );> > // Print the LinkedList> > printList(list);> > //> > // ******DELETION BY KEY******> > //> > // Delete node with value 1> > // In this case the key is ***at head***> > deleteByKey(list,> 1> );> > // Print the LinkedList> > printList(list);> > // Delete node with value 4> > // In this case the key is present ***in the> > // middle***> > deleteByKey(list,> 4> );> > // Print the LinkedList> > printList(list);> > // Delete node with value 10> > // In this case the key is ***not present***> > deleteByKey(list,> 10> );> > // Print the LinkedList> > printList(list);> > }> }>

Sortir

LinkedList: 1 2 3 4 5 6 7 8 1 found and deleted LinkedList: 2 3 4 5 6 7 8 4 found and deleted LinkedList: 2 3 5 6 7 8 10 not found LinkedList: 2 3 5 6 7 8 

Suppression à la position :

Ce processus de suppression peut être compris comme suit :

Être fait:
Donné un 'position' , supprimez le nœud à cette position de la liste chaînée .
Comment faire:

Les étapes pour le faire sont les suivantes :

1. Parcourez la liste en comptant l'index des nœuds
2. Pour chaque index, faites correspondre l'index pour qu'il soit identique à la position
3. Désormais, n'importe laquelle des 3 conditions peut être présente :
   • Cas 1 : La position est 0, c'est à dire que la tête est à supprimer
     1. Dans ce cas, remplacez la tête du nœud par le nœud suivant de la tête actuelle.
        
     2. Libérez la mémoire du nœud principal remplacé.
   • Cas 2 : La position est supérieure à 0 mais inférieure à la taille de la liste, c'est à dire au milieu ou en dernière, sauf en tête
     1. Dans ce cas, recherchez le nœud précédent du nœud à supprimer.
        
     2. Remplacez le prochain nœud précédent par le nœud suivant du nœud actuel.
     3. Libérez la mémoire du nœud remplacé.
   • Cas 3 : La position est supérieure à la taille de la liste, c'est à dire position introuvable dans la liste
     1. Dans ce cas, aucune opération n’est nécessaire.

Mise en œuvre:

Java

import> java.io.*;> // Java program to implement> // a Singly Linked List> public> class> LinkedList {> > Node head;> // head of list> > // Linked list Node.> > // Node is a static nested class> > // so main() can access it> > static> class> Node {> > int> data;> > Node next;> > // Constructor> > Node(> int> d)> > {> > data = d;> > next => null> ;> > }> > }> > // Method to insert a new node> > public> static> LinkedList insert(LinkedList list,> > int> data)> > {> > // Create a new node with given data> > Node new_node => new> Node(data);> > new_node.next => null> ;> > // If the Linked List is empty,> > // then make the new node as head> > if> (list.head ==> null> ) {> > list.head = new_node;> > }> > else> {> > // Else traverse till the last node> > // and insert the new_node there> > Node last = list.head;> > while> (last.next !=> null> ) {> > last = last.next;> > }> > // Insert the new_node at last node> > last.next = new_node;> > }> > // Return the list by head> > return> list;> > }> > // Method to print the LinkedList.> > public> static> void> printList(LinkedList list)> > {> > Node currNode = list.head;> > System.out.print(> 'LinkedList: '> );> > // Traverse through the LinkedList> > while> (currNode !=> null> ) {> > // Print the data at current node> > System.out.print(currNode.data +> ' '> );> > // Go to next node> > currNode = currNode.next;> > }> > System.out.println();> > }> > // Method to delete a node in the LinkedList by POSITION> > public> static> LinkedList> > deleteAtPosition(LinkedList list,> int> index)> > {> > // Store head node> > Node currNode = list.head, prev => null> ;> > //> > // CASE 1:> > // If index is 0, then head node itself is to be> > // deleted> > if> (index ==> 0> && currNode !=> null> ) {> > list.head = currNode.next;> // Changed head> > // Display the message> > System.out.println(> > index +> ' position element deleted'> );> > // Return the updated List> > return> list;> > }> > //> > // CASE 2:> > // If the index is greater than 0 but less than the> > // size of LinkedList> > //> > // The counter> > int> counter => 0> ;> > // Count for the index to be deleted,> > // keep track of the previous node> > // as it is needed to change currNode.next> > while> (currNode !=> null> ) {> > if> (counter == index) {> > // Since the currNode is the required> > // position Unlink currNode from linked list> > prev.next = currNode.next;> > // Display the message> > System.out.println(> > index +> ' position element deleted'> );> > break> ;> > }> > else> {> > // If current position is not the index> > // continue to next node> > prev = currNode;> > currNode = currNode.next;> > counter++;> > }> > }> > // If the position element was found, it should be> > // at currNode Therefore the currNode shall not be> > // null> > //> > // CASE 3: The index is greater than the size of the> > // LinkedList> > //> > // In this case, the currNode should be null> > if> (currNode ==> null> ) {> > // Display the message> > System.out.println(> > index +> ' position element not found'> );> > }> > // return the List> > return> list;> > }> > // **************MAIN METHOD**************> > // method to create a Singly linked list with n nodes> > public> static> void> main(String[] args)> > {> > /* Start with the empty list. */> > LinkedList list => new> LinkedList();> > //> > // ******INSERTION******> > //> > // Insert the values> > list = insert(list,> 1> );> > list = insert(list,> 2> );> > list = insert(list,> 3> );> > list = insert(list,> 4> );> > list = insert(list,> 5> );> > list = insert(list,> 6> );> > list = insert(list,> 7> );> > list = insert(list,> 8> );> > // Print the LinkedList> > printList(list);> > //> > // ******DELETION AT POSITION******> > //> > // Delete node at position 0> > // In this case the key is ***at head***> > deleteAtPosition(list,> 0> );> > // Print the LinkedList> > printList(list);> > // Delete node at position 2> > // In this case the key is present ***in the> > // middle***> > deleteAtPosition(list,> 2> );> > // Print the LinkedList> > printList(list);> > // Delete node at position 10> > // In this case the key is ***not present***> > deleteAtPosition(list,> 10> );> > // Print the LinkedList> > printList(list);> > }> }>

Sortir

LinkedList: 1 2 3 4 5 6 7 8 0 position element deleted LinkedList: 2 3 4 5 6 7 8 2 position element deleted LinkedList: 2 3 5 6 7 8 10 position element not found LinkedList: 2 3 5 6 7 8 

Toutes les opérations :

Vous trouverez ci-dessous le programme complet qui applique chaque opération ensemble :

Java

import> java.io.*;> // Java program to implement> // a Singly Linked List> public> class> LinkedList {> > Node head;> // head of list> > // Linked list Node.> > // Node is a static nested class> > // so main() can access it> > static> class> Node {> > int> data;> > Node next;> > // Constructor> > Node(> int> d)> > {> > data = d;> > next => null> ;> > }> > }> > // **************INSERTION**************> > // Method to insert a new node> > public> static> LinkedList insert(LinkedList list,> > int> data)> > {> > // Create a new node with given data> > Node new_node => new> Node(data);> > new_node.next => null> ;> > // If the Linked List is empty,> > // then make the new node as head> > if> (list.head ==> null> ) {> > list.head = new_node;> > }> > else> {> > // Else traverse till the last node> > // and insert the new_node there> > Node last = list.head;> > while> (last.next !=> null> ) {> > last = last.next;> > }> > // Insert the new_node at last node> > last.next = new_node;> > }> > // Return the list by head> > return> list;> > }> > // **************TRAVERSAL**************> > // Method to print the LinkedList.> > public> static> void> printList(LinkedList list)> > {> > Node currNode = list.head;> > System.out.print(> ' LinkedList: '> );> > // Traverse through the LinkedList> > while> (currNode !=> null> ) {> > // Print the data at current node> > System.out.print(currNode.data +> ' '> );> > // Go to next node> > currNode = currNode.next;> > }> > System.out.println(> ' '> );> > }> > // **************DELETION BY KEY**************> > // Method to delete a node in the LinkedList by KEY> > public> static> LinkedList deleteByKey(LinkedList list,> > int> key)> > {> > // Store head node> > Node currNode = list.head, prev => null> ;> > //> > // CASE 1:> > // If head node itself holds the key to be deleted> > if> (currNode !=> null> && currNode.data == key) {> > list.head = currNode.next;> // Changed head> > // Display the message> > System.out.println(key +> ' found and deleted'> );> > // Return the updated List> > return> list;> > }> > //> > // CASE 2:> > // If the key is somewhere other than at head> > //> > // Search for the key to be deleted,> > // keep track of the previous node> > // as it is needed to change currNode.next> > while> (currNode !=> null> && currNode.data != key) {> > // If currNode does not hold key> > // continue to next node> > prev = currNode;> > currNode = currNode.next;> > }> > // If the key was present, it should be at currNode> > // Therefore the currNode shall not be null> > if> (currNode !=> null> ) {> > // Since the key is at currNode> > // Unlink currNode from linked list> > prev.next = currNode.next;> > // Display the message> > System.out.println(key +> ' found and deleted'> );> > }> > //> > // CASE 3: The key is not present> > //> > // If key was not present in linked list> > // currNode should be null> > if> (currNode ==> null> ) {> > // Display the message> > System.out.println(key +> ' not found'> );> > }> > // return the List> > return> list;> > }> > // **************DELETION AT A POSITION**************> > // Method to delete a node in the LinkedList by POSITION> > public> static> LinkedList> > deleteAtPosition(LinkedList list,> int> index)> > {> > // Store head node> > Node currNode = list.head, prev => null> ;> > //> > // CASE 1:> > // If index is 0, then head node itself is to be> > // deleted> > if> (index ==> 0> && currNode !=> null> ) {> > list.head = currNode.next;> // Changed head> > // Display the message> > System.out.println(> > index +> ' position element deleted'> );> > // Return the updated List> > return> list;> > }> > //> > // CASE 2:> > // If the index is greater than 0 but less than the> > // size of LinkedList> > //> > // The counter> > int> counter => 0> ;> > // Count for the index to be deleted,> > // keep track of the previous node> > // as it is needed to change currNode.next> > while> (currNode !=> null> ) {> > if> (counter == index) {> > // Since the currNode is the required> > // position Unlink currNode from linked list> > prev.next = currNode.next;> > // Display the message> > System.out.println(> > index +> ' position element deleted'> );> > break> ;> > }> > else> {> > // If current position is not the index> > // continue to next node> > prev = currNode;> > currNode = currNode.next;> > counter++;> > }> > }> > // If the position element was found, it should be> > // at currNode Therefore the currNode shall not be> > // null> > //> > // CASE 3: The index is greater than the size of the> > // LinkedList> > //> > // In this case, the currNode should be null> > if> (currNode ==> null> ) {> > // Display the message> > System.out.println(> > index +> ' position element not found'> );> > }> > // return the List> > return> list;> > }> > // **************MAIN METHOD**************> > // method to create a Singly linked list with n nodes> > public> static> void> main(String[] args)> > {> > /* Start with the empty list. */> > LinkedList list => new> LinkedList();> > //> > // ******INSERTION******> > //> > // Insert the values> > list = insert(list,> 1> );> > list = insert(list,> 2> );> > list = insert(list,> 3> );> > list = insert(list,> 4> );> > list = insert(list,> 5> );> > list = insert(list,> 6> );> > list = insert(list,> 7> );> > list = insert(list,> 8> );> > // Print the LinkedList> > printList(list);> > //> > // ******DELETION BY KEY******> > //> > // Delete node with value 1> > // In this case the key is ***at head***> > deleteByKey(list,> 1> );> > // Print the LinkedList> > printList(list);> > // Delete node with value 4> > // In this case the key is present ***in the> > // middle***> > deleteByKey(list,> 4> );> > // Print the LinkedList> > printList(list);> > // Delete node with value 10> > // In this case the key is ***not present***> > deleteByKey(list,> 10> );> > // Print the LinkedList> > printList(list);> > //> > // ******DELETION AT POSITION******> > //> > // Delete node at position 0> > // In this case the key is ***at head***> > deleteAtPosition(list,> 0> );> > // Print the LinkedList> > printList(list);> > // Delete node at position 2> > // In this case the key is present ***in the> > // middle***> > deleteAtPosition(list,> 2> );> > // Print the LinkedList> > printList(list);> > // Delete node at position 10> > // In this case the key is ***not present***> > deleteAtPosition(list,> 10> );> > // Print the LinkedList> > printList(list);> > }> }>

Sortir

LinkedList: 1 2 3 4 5 6 7 8 1 found and deleted LinkedList: 2 3 4 5 6 7 8 4 found and deleted LinkedList: 2 3 5 6 7 8 10 not found LinkedList: 2 3 5 6 7 8 0 position element deleted LinkedList: 3 5 6 7 8 2 position element deleted LinkedList: 3 5 7 8 10 position element not found LinkedList: 3 5 7 8