IMPLEMENTAZIONE DI UN ELENCO COLLEGATO IN JAVA UTILIZZANDO CLASS

Prerequisito: Come gli array, la Linked List è una struttura dati lineare. A differenza degli array, gli elementi dell'elenco collegato non vengono memorizzati nella posizione contigua, gli elementi sono collegati utilizzando puntatori come mostrato di seguito.

lista collegata

Come gli array, la Linked List è una struttura dati lineare. A differenza degli array, gli elementi dell'elenco collegato non vengono memorizzati nella posizione contigua, gli elementi sono collegati utilizzando puntatori come mostrato di seguito.

In Java, LinkedList può essere rappresentato come una classe e un Nodo come una classe separata. La classe LinkedList contiene un riferimento al tipo di classe Node.

Giava

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; }> > }> }>

Creazione e inserimento:

In questo articolo l'inserimento nella lista avviene alla fine, cioè il nuovo nodo viene aggiunto dopo l'ultimo nodo della Lista Collegata data. Ad esempio, se la Lista collegata specificata è 5->10->15->20->25 e deve essere inserito 30, la Lista collegata diventa 5->10->15->20->25->30 .
Poiché una lista collegata è tipicamente rappresentata dal suo puntatore principale, è necessario attraversare la lista fino all'ultimo nodo e quindi cambiare il penultimo nodo con il nuovo nodo.

linkedlist_insert_last

Implementazione:

Giava

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);> > }> }>

Produzione

LinkedList: 1 2 3 4 5 6 7 8

Traversata: Per l'attraversamento, di seguito è riportata una funzione generica printList() che stampa qualsiasi elenco specificato attraversando l'elenco dal nodo principale all'ultimo.

Implementazione:

Giava

Produzione

LinkedList: 1 2 3 4 5 6 7 8

Cancellazione tramite CHIAVE:

Il processo di cancellazione può essere inteso come segue:

Da fare:

Data una 'chiave', elimina la prima occorrenza di questa chiave nell'elenco collegato .

Come farlo:

Per eliminare un nodo dall'elenco collegato, eseguire i seguenti passaggi.

Cerca la chiave per la sua prima occorrenza nell'elenco

Ora, può verificarsi una qualsiasi delle 3 condizioni:

Caso 1: La chiave si trova in Testa

In questo caso, cambia la testa del nodo con il nodo successivo della testa corrente.

Liberare la memoria del nodo testa sostituito.

Caso 2: La chiave si trova al centro o all'ultima, tranne che in Testa

In questo caso, Trova il nodo precedente del nodo da eliminare.

Cambia il successivo nodo precedente con il nodo successivo del nodo corrente.

Liberare la memoria del nodo sostituito.

Caso 3: La chiave non si trova nell'elenco

In questo caso non è necessario eseguire alcuna operazione.

linkedlist_deletion

Implementazione:

Giava

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);> > }> }>

Produzione

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

Cancellazione in posizione:

Questo processo di cancellazione può essere interpretato come segue:

Da fare:
Dato un 'posizione' , elimina il nodo in questa posizione dall'elenco collegato .
Come farlo:

I passaggi per farlo sono i seguenti:

Attraversa la lista contando l'indice dei nodi

Per ogni indice, abbina l'indice in modo che sia uguale alla posizione

Ora, può verificarsi una qualsiasi delle 3 condizioni:

Caso 1: La posizione è 0, cioè la testa deve essere cancellata

In questo caso, cambia la testa del nodo con il nodo successivo della testa corrente.

Liberare la memoria del nodo testa sostituito.

Caso 2: La posizione è maggiore di 0 ma inferiore alla dimensione dell'elenco, cioè al centro o all'ultimo, tranne che in testa

In questo caso, Trova il nodo precedente del nodo da eliminare.

Cambia il nodo successivo del precedente con il nodo successivo del nodo corrente.

Liberare la memoria del nodo sostituito.

Caso 3: La posizione è maggiore della dimensione dell'elenco, ovvero posizione non trovata nell'elenco

In questo caso non è necessario eseguire alcuna operazione.

linkedlist_deletion

Implementazione:

Giava

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);> > }> }>

Produzione

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

Tutte le operazioni:

Di seguito è riportato il programma completo che applica ciascuna operazione insieme:

Giava

'
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);> > }> }>

Produzione

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