Impara Implementazione di LinkedList in Java

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.

Procediamo ora con la creazione della classe SinglyLinkedList, dove definiremo tutta la logica della 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 una head e una 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 è visibile l'implementazione del metodo per aggiungere un elemento alla fine della lista. Analizziamo il funzionamento di questo metodo:

Si crea un oggetto della classe Node, newNode, e lo si inizializza tramite il costruttore, passando il data dai parametri del metodo append();
Successivamente, si verifica se la lista è vuota e, in tal caso, si sostituisce il primo elemento della lista (head) con newNode tramite riassegnazione;
Si aggiunge quindi un'istruzione return per uscire dal metodo;
Se la lista non è vuota, in questo metodo si crea 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 ciascun elemento della lista e stamparli a schermo. In questo caso, si utilizza anche il segnaposto current, che viene inizializzato con Node head;
Successivamente, si imposta la condizione per il ciclo while su current != null e si stampa il campo data a schermo;
Per iterare sulla lista, si utilizza il riferimento riassegnando current, che appare come current = current.next;;
Questa operazione viene ripetuta fino a quando Node current diventa vuoto. Dopo di ciò, si esce dal ciclo e si passa alla riga successiva.

A proposito, riflettere 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. Si crea innanzitutto 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 esattamente il numero 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++). In questo ciclo, si individua l'elemento desiderato tramite l'operazione già nota: current = current.next;
Una volta trovato l'elemento desiderato, si assegna al suo attributo data un nuovo valore, eseguendo l'operazione
current.data = newData. Il valore newData viene passato come parametro a questo metodo.

Tutto è chiaro?

Grazie per i tuoi commenti!

Sezione 1. Capitolo 7

Chieda ad AI

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

Sezione 1. Capitolo 7