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 concatenato è una struttura dati popolare, che consiste in un elenco di nodi collegati (o collegati).

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

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.

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 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.

Relazionato: 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:

nodo di classe pubblica {
Dati int privati;
Nodo privato NextNode;
//constructor
nodo pubblico() {
Dati = 0;
NextNode = nullo;
}
//getters e setter
public int getData() {
restituire i dati;
}
public void setData (int data) {
Dati = dati;
}
nodo pubblico getNextNode() {
ritorna NextNode;
}
public void setNextNode (Nodo 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.

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

public class LinkedList {
testa del nodo privato;
//constructor
Elenco Collegato pubblico() {
Testa = nullo;
}
}

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.

Relazionato: Come costruire strutture dati con classi JavaScript ES6

La raccolta di elenchi collegati dei metodi di inserimento è uno dei motivi per cui uno sviluppatore potrebbe scegliere di utilizzare questi dati struttura 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 (chiave int) {
//crea un nuovo nodo usando la classe del nodo
Temp. nodo = nuovo Nodo();
// controlla se il nodo Temp è stato creato con successo
//assegna i dati che gli sono stati forniti dall'utente
if (Temp != null) {
Temp.setData (chiave);
Temp.setNextNode (null);
//controlla se l'intestazione della lista collegata è vuota
//assegna il nodo appena creato alla posizione di testa
if (Testa == nullo) {
Prevalenza = Temp;
}
//se un nodo è già nella posizione di testa
//aggiungete il nuovo nodo e impostatelo come head
altro {
Temp.setNextNode (testa);
Prevalenza = 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.

autista di classe pubblica {
//esegue il programma
public static void main (String[] args) {
//crea una nuova lista collegata chiamata List
Lista LinkedList = new LinkedList();
//aggiunge ogni valore all'inizio dell'elenco collegato come nuovo nodo
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" è nella posizione principale nell'elenco collegato. Ma come confermarlo?

Utilizzo del metodo Visualizza tutti i nodi

Il metodo di visualizzazione di tutti i nodi è un metodo di elenco collegato essenziale. Senza di esso, 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.

// metodo di visualizzazione di tutti i nodi
public void displayAllNodes() {
//crea un nuovo nodo chiama Temp e assegnalo all'inizio della lista collegata
//se la testa ha un valore nullo allora la lista collegata è vuota
Temp. nodo = Testa;
if (Testa == nullo){
System.out.println("L'elenco è vuoto.");
Restituzione;
}
System.out.println("L'elenco:");
while (Temp != null) {
//stampa i dati in ogni nodo sulla console (a partire dalla testa)
System.out.print (Temp.getData() + " ");
Temp = Temp.getNextNode();
} 
}

Ora che il displayAllNodes 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.

//stampa i nodi in una lista collegata
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 displayAllNodes 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.

//cerca un singolo nodo usando una chiave
public boolean findNode (chiave int) {
//crea un nuovo nodo e posizionalo in testa alla lista concatenata
Temp. nodo = Testa;
//mentre il nodo corrente non è vuoto
//controlla se i suoi dati corrispondono alla chiave fornita dall'utente
while (Temp != null) {
if (Temp.getData() == chiave) {
System.out.println("Il nodo è nell'elenco"); 
restituire vero;
}
//sposta al nodo successivo
Temp = Temp.getNextNode();
}
//se la chiave non è stata trovata nell'elenco collegato
System.out.println("Il nodo non è nell'elenco"); 
restituire falso;
}

Con il displayAllNodes 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.

//controlla se un nodo è nella lista collegata
List.findNode (4);

Il codice sopra produrrà il seguente output nella console:

Il nodo è nella lista

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 (chiave int) { 
Temp. nodo = Testa; 
Nodo prev = null; 
// controlla se il nodo principale contiene i dati 
//e cancellalo 
if (Temp != null && Temp.getData() == chiave) { 
Head = Temp.getNextNode(); 
Restituzione; 
} 
//cerca gli altri nodi nell'elenco 
//e cancellalo 
while (Temp != null) { 
if (Temp.getNextNode().getData() == chiave ) { 
prev = Temp.getNextNode().getNextNode(); 
Temp.setNextNode (precedente); 
Restituzione; 
} 
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.

//cancella il nodo che contiene i dati 4
List.findAndDelete (4);
//stampa tutti i nodi nella lista collegata
List.displayAllNodes();

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

La lista:
2 6 8 10

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. Dal momento che hai tutto il necessario per iniziare, perché non provare questi esempi in Java?

Come creare ed eseguire operazioni su array in Java

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

Leggi Avanti

Circa l'autore