Impara Implementazione di LinkedList in Java | Strutture Dati Fondamentali in Java

È il momento di metterti alla prova con alcuni compiti davvero complessi.

Implementeremo la nostra struttura dati semplificata—nello specifico, la SinglyLinkedList.

Iniziamo implementando la classe Node, che memorizzerà un valore e un riferimento al prossimo Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

L'implementazione della classe Node in SinglyLinkedList è già stata illustrata nel capitolo precedente, quindi non ci soffermeremo ulteriormente su questo aspetto.

Successivamente, creiamo la classe SinglyLinkedList, dove definiremo tutta la logica per la nostra struttura dati:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Abbiamo creato il campo Node head, che memorizzerà il primo elemento della nostra struttura dati.

In una normale LinkedList, sono presenti anche head e tail che memorizzano rispettivamente il primo e l'ultimo elemento della struttura dati. Poiché la struttura dati deve essere vuota durante l'inizializzazione, impostiamo questo campo a null nel costruttore.

La nostra struttura dati deve supportare tutte le operazioni CRUD.

Creazione

Procediamo passo dopo passo e scriviamo un metodo per aggiungere un elemento alla fine della lista, rappresentando l'operazione di Creazione:

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }
}

Sopra, è possibile vedere l'implementazione del metodo per aggiungere un elemento alla fine della lista. Analizziamo come funziona questo metodo:

Viene creato un oggetto della classe Node, newNode, e inizializzato tramite il costruttore, passando il data dai parametri del metodo append();
Successivamente, viene verificato se la lista è vuota e, in tal caso, si sostituisce il primo elemento della lista (head) con newNode tramite riassegnazione;
Viene poi aggiunta un'istruzione return per uscire dal metodo;
Se la lista non è vuota, in questo metodo viene creato un nuovo oggetto, current, che rappresenta il Node head in questo contesto;
Utilizzando un ciclo while, si itera su tutta la lista fino a quando current.next è null, ovvero fino a determinare che il prossimo elemento nella lista è vuoto;
Una volta trovato l'ultimo elemento non nullo nella lista, si imposta il suo collegamento a newNode, aggiungendo così l'elemento alla lista.

In altre parole, l'obiettivo del metodo append era impostare il collegamento dell'ultimo elemento verso il nuovo elemento. In questo modo, si aggiunge un nuovo elemento alla lista.

Lettura

Procediamo; ora dobbiamo implementare l'operazione di lettura.

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

L'operazione di lettura è piuttosto semplice. È necessario iterare su ogni elemento della lista e stamparli a schermo. In questo caso, utilizziamo anche il segnaposto current, che inizializziamo con Node head;
Successivamente, impostiamo la condizione per il ciclo while su current != null e stampiamo il campo data a schermo;
Per iterare sulla lista, utilizziamo il riferimento riassegnando current, che diventa current = current.next;;
Questo viene ripetuto finché Node current non diventa vuoto. Dopo di ciò, si esce dal ciclo e si passa alla riga successiva.

A proposito, rifletti su come sostituire questo ciclo while con un ciclo do-while. È possibile farlo?

Aggiornamento

Passiamo ora al metodo di aggiornamento, la cui implementazione risulta più interessante:

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Per prima cosa, si verifica se questo index è presente nella nostra lista utilizzando un'istruzione if. In caso contrario, viene stampato il messaggio "Indice non valido" e il metodo termina. Questa operazione viene eseguita per evitare errori;
Se l'indice è all'interno dei limiti della nostra lista, si procede con l'algoritmo già noto. Innanzitutto, si crea un oggetto della classe Node chiamato current, che viene inizializzato come head;
Invece di utilizzare un ciclo while, si utilizza un ciclo for, più adatto in questo caso poiché si conosce il numero esatto di iterazioni necessarie. Il numero di iterazioni corrisponde al valore del parametro index;
Il ciclo ha la seguente forma:
for (int i = 0; i < index; i++). All'interno di questo ciclo, si individua l'elemento desiderato tramite l'operazione già nota: current = current.next;
Una volta individuato l'elemento desiderato, si assegna un nuovo valore all'attributo data, eseguendo l'operazione
current.data = newData. Il valore newData viene fornito tra i parametri di questo metodo.

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 1. Capitolo 6

Chieda ad AI

Chieda pure quello che desidera o provi una delle domande suggerite per iniziare la nostra conversazione

Suggested prompts:

Can you show me the code for the append method?

How would you implement the read operation in code?

Can you explain how the update method works with an example?

Scorri per mostrare il menu

È il momento di metterti alla prova con alcuni compiti davvero complessi.

Implementeremo la nostra struttura dati semplificata—nello specifico, la SinglyLinkedList.

Iniziamo implementando la classe Node, che memorizzerà un valore e un riferimento al prossimo Node.

Node.java


              123456789
            
class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

L'implementazione della classe Node in SinglyLinkedList è già stata illustrata nel capitolo precedente, quindi non ci soffermeremo ulteriormente su questo aspetto.

Successivamente, creiamo la classe SinglyLinkedList, dove definiremo tutta la logica per la nostra struttura dati:

SinglyLinkedList.java


              1234567
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }
}

Abbiamo creato il campo Node head, che memorizzerà il primo elemento della nostra struttura dati.

La nostra struttura dati deve supportare tutte le operazioni CRUD.

Creazione

Procediamo passo dopo passo e scriviamo un metodo per aggiungere un elemento alla fine della lista, rappresentando l'operazione di Creazione:

SinglyLinkedList.java


              12345678910111213141516171819202122
            
public class SinglyLinkedList {
    private Node head;

    public SinglyLinkedList() {
        this.head = null;
    }

    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }

        Node current = head;
        while (current.next != null) {
            current = current.next;
        }

        current.next = newNode;
    }
}

Sopra, è possibile vedere l'implementazione del metodo per aggiungere un elemento alla fine della lista. Analizziamo come funziona questo metodo:

Viene creato un oggetto della classe Node, newNode, e inizializzato tramite il costruttore, passando il data dai parametri del metodo append();
Successivamente, viene verificato se la lista è vuota e, in tal caso, si sostituisce il primo elemento della lista (head) con newNode tramite riassegnazione;
Viene poi aggiunta un'istruzione return per uscire dal metodo;
Se la lista non è vuota, in questo metodo viene creato un nuovo oggetto, current, che rappresenta il Node head in questo contesto;
Utilizzando un ciclo while, si itera su tutta la lista fino a quando current.next è null, ovvero fino a determinare che il prossimo elemento nella lista è vuoto;
Una volta trovato l'ultimo elemento non nullo nella lista, si imposta il suo collegamento a newNode, aggiungendo così l'elemento alla lista.

In altre parole, l'obiettivo del metodo append era impostare il collegamento dell'ultimo elemento verso il nuovo elemento. In questo modo, si aggiunge un nuovo elemento alla lista.

Lettura

Procediamo; ora dobbiamo implementare l'operazione di lettura.

SinglyLinkedList.java


              12345678
            
public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

L'operazione di lettura è piuttosto semplice. È necessario iterare su ogni elemento della lista e stamparli a schermo. In questo caso, utilizziamo anche il segnaposto current, che inizializziamo con Node head;
Successivamente, impostiamo la condizione per il ciclo while su current != null e stampiamo il campo data a schermo;
Per iterare sulla lista, utilizziamo il riferimento riassegnando current, che diventa current = current.next;;
Questo viene ripetuto finché Node current non diventa vuoto. Dopo di ciò, si esce dal ciclo e si passa alla riga successiva.

A proposito, rifletti su come sostituire questo ciclo while con un ciclo do-while. È possibile farlo?

Aggiornamento

Passiamo ora al metodo di aggiornamento, la cui implementazione risulta più interessante:

SinglyLinkedList.java


              12345678910111213
            
public void update(int index, int newData) {
    if (index < 0 || index >= size()) {
        System.out.println("Invalid index");
        return;
    }

    Node current = head;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }

    current.data = newData;
}

Per prima cosa, si verifica se questo index è presente nella nostra lista utilizzando un'istruzione if. In caso contrario, viene stampato il messaggio "Indice non valido" e il metodo termina. Questa operazione viene eseguita per evitare errori;
Se l'indice è all'interno dei limiti della nostra lista, si procede con l'algoritmo già noto. Innanzitutto, si crea un oggetto della classe Node chiamato current, che viene inizializzato come head;
Invece di utilizzare un ciclo while, si utilizza un ciclo for, più adatto in questo caso poiché si conosce il numero esatto di iterazioni necessarie. Il numero di iterazioni corrisponde al valore del parametro index;
Il ciclo ha la seguente forma:
for (int i = 0; i < index; i++). All'interno di questo ciclo, si individua l'elemento desiderato tramite l'operazione già nota: current = current.next;
Una volta individuato l'elemento desiderato, si assegna un nuovo valore all'attributo data, eseguendo l'operazione
current.data = newData. Il valore newData viene fornito tra i parametri di questo metodo.

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 1. Capitolo 6