Introduzione all'utilizzo di elenchi collegati in Java

Una struttura dati utilizza diversi metodi predefiniti per archiviare, recuperare ed eliminare i dati, il che culmina nella creazione di programmi efficienti. Un elenco collegato è una struttura di dati popolare, che consiste in un elenco di nodi collegati (o collegati).

Ma come si crea un elenco collegato in Java? Diamo un'occhiata.

---

---

Come funziona un elenco collegato?

Ogni lista collegata inizia con un nodo speciale che viene spesso chiamato 'testa', che ha la responsabilità di puntare sempre all'inizio della lista. La testa è importante perché ogni nodo in una lista collegata non ha bisogno di seguire fisicamente il suo successore (il che significa che un predecessore e un successore non devono essere fisicamente adiacenti).

Come ogni struttura dati, l'elenco collegato facilita la creazione, il recupero, l'inserimento e la distruzione attraverso un insieme di funzioni predefinite che possono essere utilizzate da qualsiasi sviluppatore.

Creazione di un elenco collegato in Java

Un programma Java progettato per creare e manipolare elenchi collegati avrà tre sezioni distinte; la classe del nodo, la classe dell'elenco collegato e il driver. Sebbene queste tre sezioni possano essere combinate in un unico file, esiste un principio di progettazione in informatica noto come 'separazione delle preoccupazioni' che ogni sviluppatore dovrebbe conoscere.

Il principio della separazione degli interessi impone che ogni sezione del codice che affronta un problema specifico debba essere separata. Questo principio ti aiuterà a creare un codice più pulito (più leggibile) ed è ideale per creare strutture di dati.

Il primo passaggio nella creazione di un elenco collegato in Java consiste nel creare una classe nodo. Una classe nodo dovrebbe avere due attributi; uno degli attributi rappresenterà la porzione dati del nodo, mentre l'altro attributo rappresenterà la porzione collegata. Una classe nodo dovrebbe anche avere un costruttore, getter e setter.

---

---

Imparentato: Impara come creare classi in Java

I getter e i setter consentiranno ad altre classi (come la classe della lista concatenata) di accedere ai vari nodi all'interno della lista concatenata.

---

---

Esempio di classe del nodo

Di seguito è riportato un esempio di classe di nodi per farti un'idea di cosa intendiamo:


public class Node {
private int Data;
private Node NextNode;
//constructor
public Node() {
Data = 0;
NextNode = null;
}
//getters and setters
public int getData() {
return Data;
}
public void setData(int data) {
Data = data;
}
public Node getNextNode() {
return NextNode;
}
public void setNextNode(Node nextNode) {
NextNode = nextNode;
}
}

In questo esempio, l'attributo data memorizzerà valori interi. Ora che hai la classe del nodo, è il momento di passare all'elenco collegato.

Esempio di elenco collegato

Di seguito è riportato un esempio di elenco collegato in Java.

public class LinkedList {
private Node Head;
//constructor
public LinkedList() {
Head = null;
}
}


Il codice sopra creerà una classe di elenchi collegati, tuttavia, senza le sue varie operazioni, la classe può essere vista come l'equivalente di una shell vuota. La struttura dati dell'elenco collegato ha diverse operazioni che possono essere utilizzate per popolarla:

• Inserire nella parte anteriore.
• Inserisci nel mezzo.
• Inserire sul retro.

Imparentato: Come costruire strutture dati con classi JavaScript ES6

La raccolta di elenchi collegati di metodi di inserimento è uno dei motivi per cui uno sviluppatore potrebbe scegliere di utilizzare questa struttura di dati su un'altra struttura di dati come gli stack (che consente solo l'inserimento e l'eliminazione dall'alto).

Utilizzo del metodo Insert at the Front

Il metodo insert at the front, come suggerisce il nome, inserisce nuovi dati (o nuovi nodi) all'inizio della lista collegata.

Inserisci nell'esempio del metodo anteriore

Di seguito è riportato un esempio di come inseriresti nuovi dati all'inizio dell'elenco.

//insert node at front method
public void insertAtFront(int key) {
//create a new node using the node class
Node Temp = new Node();
//check if the Temp node was successfully created
//assign the data that was provides by the user to it
if(Temp != null) {
Temp.setData(key);
Temp.setNextNode(null);

//check if the head of the linked list is empty
//assign the node that was just created to the head position
if(Head == null) {
Head = Temp;
}
//if a node is already at the head position
//add the new node to it and set it as the head
else {
Temp.setNextNode(Head);
Head = Temp;
}
}
}


Il inserireAtFront Il metodo nell'esempio precedente consente a un utente di aggiungere nuovi nodi a un determinato elenco collegato.

Applicazione dell'inserto nella parte anteriore Esempio

Di seguito è riportato un esempio di come applicheresti l'inserto sul davanti.

public class Driver {
//executes the program
public static void main(String[] args) {
//create a new linked list called List
LinkedList List = new LinkedList();
//add each value to the front of the linked list as a new node
List.insertAtFront(10);
List.insertAtFront(8);
List.insertAtFront(6);
List.insertAtFront(4);
List.insertAtFront(2);
}
}


Il Autista class (che è il nome che viene spesso assegnato alla classe eseguibile in Java), utilizza la classe LinkedList per creare un elenco collegato di cinque numeri pari. Guardando il codice sopra dovrebbe essere facile vedere che il numero '2' si trova nella posizione iniziale nell'elenco collegato. Ma come confermarlo?

come attirare spettatori su Twitch

Utilizzo del metodo Visualizza tutti i nodi

Il metodo di visualizzazione di tutti i nodi è un metodo di elenco collegato essenziale. Senza di essa, uno sviluppatore non sarà in grado di vedere i nodi in un elenco collegato. Percorre la lista concatenata (a partire dalla testata) stampando i dati memorizzati in ogni nodo che forma la lista.

Esempio di metodo Visualizza tutti i nodi

Di seguito è riportato un esempio di utilizzo del metodo visualizza tutte le note in Java.

//display all nodes method
public void displayAllNodes() {
//create a new node call Temp and assign it to the head of the linked list
//if the head has a null value then the linked list is empty
Node Temp = Head;
if (Head == null){
System.out.println('The list is empty.');
return;
}
System.out.println('The List:');

while(Temp != null) {
//print the data in each node to the console(starting from the head)
System.out.print(Temp.getData() + ' ');
Temp = Temp.getNextNode();
}
}

Ora che il visualizzaTuttiNodi il metodo è stato aggiunto al Lista collegata class è possibile visualizzare l'elenco collegato aggiungendo una singola riga di codice alla classe driver.

Utilizzo del metodo Visualizza tutti i nodi Esempio

Di seguito, vedrai come utilizzeresti il ​​metodo di visualizzazione di tutti i nodi.

//print the nodes in a linked list
List.displayAllNodes();

L'esecuzione della riga di codice sopra produrrà il seguente output nella console:

La lista:

2 4 6 8 10

Utilizzo del metodo Trova nodo

Ci saranno casi in cui un utente vorrà trovare un nodo specifico in un elenco collegato.

Ad esempio, non sarebbe pratico per una banca che ha milioni di clienti stampare tutti i clienti nel proprio database quando hanno solo bisogno di vedere i dettagli di un cliente specifico.

Pertanto, invece di usare il visualizzaTuttiNodi metodo, un metodo più efficiente consiste nel trovare il singolo nodo contenente i dati richiesti. Questo è il motivo per cui la ricerca di un metodo a nodo singolo è importante nella struttura dati dell'elenco collegato.

Trova il metodo del nodo Esempio

Di seguito è riportato un esempio dell'utilizzo del metodo find node.

//search for a single node using a key
public boolean findNode(int key) {
//create a new node and place it at the head of the linked list
Node Temp = Head;
//while the current node is not empty
//check if its data matches the key provided by the user
while (Temp != null) {
if (Temp.getData() == key) {
System.out.println('The node is in the list');
return true;
}
//move to the next node
Temp = Temp.getNextNode();
}
//if the key was not found in the linked list
System.out.println('The node is not in the list');
return false;
}

Con il visualizzaTuttiNodi metodo, hai confermato che il Lista collegata contiene 5 numeri pari da 2 a 10. Il trovaNodo l'esempio sopra può confermare se uno di quei numeri pari è il numero 4 semplicemente chiamando il metodo nella classe driver e fornendo il numero come parametro.

Utilizzo dell'esempio del metodo Trova nodo

Di seguito è riportato un esempio di come utilizzeresti in pratica il metodo di ricerca del nodo.

//check if a node is in the linked list
List.findNode(4);


Il codice sopra produrrà il seguente output nella console:

The node is in the list

Utilizzo del metodo Elimina un nodo

Utilizzando lo stesso esempio di banca dall'alto, un cliente nel database della banca potrebbe voler chiudere il proprio conto. È qui che sarà utile il metodo di eliminazione di un nodo. È il metodo di elenco collegato più complesso.

Il metodo Elimina un nodo cerca un determinato nodo, elimina quel nodo e collega il nodo precedente a quello che segue il nodo che è stato eliminato.

Elimina un nodo di esempio di metodo

Di seguito è riportato un esempio del metodo di eliminazione di un nodo.

public void findAndDelete(int key) {
Node Temp = Head;
Node prev = null;
//check if the head node holds the data
//and delete it
if (Temp != null && Temp.getData() == key) {
Head = Temp.getNextNode();
return;
}
//search the other nodes in the list
//and delete it
while (Temp != null) {
if (Temp.getNextNode().getData() == key ) {
prev = Temp.getNextNode().getNextNode();
Temp.setNextNode(prev);
return;
}
Temp = Temp.getNextNode();
}
}

Utilizzo dell'esempio del metodo Elimina un nodo

Di seguito è riportato un esempio di utilizzo pratico del metodo di eliminazione di un nodo.

non ho ricevuto il mio ordine su Amazon

//delete the node that holds the data 4
List.findAndDelete(4);
//print all nodes in the linked list
List.displayAllNodes();

L'utilizzo delle due righe di codice sopra nella classe Driver preesistente produrrà il seguente output nella console:

The List:
2 6 8 10

Ora puoi creare elenchi collegati in Java

Se sei arrivato alla fine di questo articolo tutorial, avrai imparato:

• Come creare una classe nodo.
• Come creare una classe di elenchi collegati.
• Come popolare una classe di elenchi collegati con i suoi metodi predefiniti.
• Come creare una classe driver e utilizzare i diversi metodi dell'elenco collegato per ottenere il risultato desiderato.

Un elenco collegato è solo una delle tante strutture di dati che è possibile utilizzare per archiviare, recuperare ed eliminare i dati. Dato che hai tutto il necessario per iniziare, perché non provare questi esempi in Java?

Condividere Condividere Tweet E-mail Come creare ed eseguire operazioni su array in Java

Imparare Java? Lascia che gli array gestiscano i tuoi dati con facilità.

Leggi Avanti Argomenti correlati

• Programmazione
• Giava
• Programmazione
• Suggerimenti per la codifica

Circa l'autore Kadeisha Kean(21 articoli pubblicati)

Kadeisha Kean è uno sviluppatore software full-stack e scrittore tecnico/tecnologico. Ha la spiccata capacità di semplificare alcuni dei concetti tecnologici più complessi; producendo materiale che può essere facilmente compreso da qualsiasi principiante della tecnologia. È appassionata di scrivere, sviluppare software interessanti e viaggiare per il mondo (attraverso documentari).

Altro da Kadeisha Kean

Iscriviti alla nostra Newsletter

Iscriviti alla nostra newsletter per suggerimenti tecnici, recensioni, ebook gratuiti e offerte esclusive!

Clicca qui per iscriverti