Java Strutture Dati: Liste Concatenate

Con il 2020 andiamo ad esaminare un nuovo aspetto della programmazione: le strutture dati. Spesso capita a tutti di utilizzare strutture messe a disposizione dai vari linguaggi di programmazione. L'obiettivo sarà quello di avere un'idea, se pur generale di come funzionano e dei loro meccanismi interni. Spesso ne daremo una versione non del tutto uguale a quella realmente implementata, ma alla fine avremo comunque una panoramica sul funzionamento della struttura.

In particolare, oggi andiamo a trattare un argomento per molti piuttosto ostico: le liste concatenate (in inglese Linked List).

Vediamo meglio.

Una lista concatenata è composta da nodi. Un nodo è l'insieme dei dati che deve rappresentare e del puntatore al suo successivo. Questo significa che ogni nodo avrà un campo che contiene l'indirizzo dell'elemento che viene dopo di lui nella lista.

Vediamo con un disegno:

Vediamo come il nodo sia composto da un generico campo data che rappresenta tutte le informazioni che dovrà contenere e un campo next, che rappresenta il puntatore al nodo successivo.

Perchè il campo next? 

L'idea è quella di non aver bisogno di uno spazio contiguo in RAM, per cui si sceglie di allocare un numero n di nodi dove c'è spazio disponibile. Otteniamo quindi il vantaggio di una struttura dinamica anche dal punto di vista dell'occupazione di memoria.

Implementazione della classe Node

In questa implementazione assumiamo che l'informazione del nodo sia un numero intero. Si può tranquillamente sostituire con tipi dato più complessi.

 

public class Node {

        int data;
        Node next;

        // Costruttore per creare un nuovo nodo
        // Inizializzo next a null per default

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

La classe è molto semplice nella sua implementazione, infatti presenta un solo costruttore che si limita ad inizializzare il campo data e setta a null il campo next di default. Per completezza ho preferito rendere esplicita l'inizializzazione del next.

Classe LinkedList

Andiamo a vedere qualche operazione che possiamo svolgere sulle liste concatenate.

Creazione, inserimento e stampa

import java.io.*; 

// Java program to implement 
// a Singly Linked List 
public class LinkedList { 

    private Node head; // testa della lista 

    // Metodo per inserire un nuovo nodo.
    // Restituisce una nuova lista
    public static LinkedList insert(LinkedList list, int data) 
    { 
        // Crea un nuovo nodo con il dato fornito 
        Node toInsert = new Node(data); 

        // Se la lista concatenata è vuota, 
        // allora rende il nuovo nodo la testa 
        if (head == null) { 
            head = toInsert; 
        } 
        else { 
            // Altrimenti scorre la lista sino all'ultimo nodo
            // e inserisce il nuovo nodo lì 
            Node last = head; 
            while (last.next != null) { 
                last = last.next; 
            } 
            // Inserisce il nuovo nodo come ultimo nodo
            last.next = toInsert; 
        } 
        // Restituisce la nuova lista restituendo il puntatore alla testa
        return list; 
    } 

    // Metodo per stampare una lista concatenata
    public static void printList(LinkedList list) 
    { 
        Node curr = head; 

        // Scorre la lista concatenata
        while (curr != null) { 
            // Stampa il dato al nodo corrente 
            System.out.print(curr.data + " "); 

            // Passa al nodo successivo
            curr = curr.next; 
        } 
    } 

    public static void main(String[] args) 
    { 
        /* Parte con una lista vuota */
        LinkedList list = new LinkedList(); 

        // Inserisce i valori
        list = insert(list, 11); 
        list = insert(list, 21); 
        list = insert(list, 31); 
        list = insert(list, 41); 
        list = insert(list, 51); 
        list = insert(list, 61); 
        list = insert(list, 71); 
        list = insert(list, 81); 

        // Stampa la lista concatenata
        printList(list); 
    } 
} 

Capiamo meglio cosa succede. Il metodo insert mostrato sopra esegue quello che chiamiamo inserimento in coda, rendendo il nodo da inserire l'ultimo.

Possiamo distinguere due casi: la lista vuota e la lista non vuota.

Nel caso di lista vuota, il nodo da inserire diventa la testa della lista, nonchè l'unico nodo della collezione.

Nel caso di lista non vuota si scorre la lista sino a quando non si trova l'ultimo nodo. Dopodichè il campo next dell'ultimo nodo viene impostato con l'indirizzo del nodo da inserire. In questa maniera otterremo una nuova lista il cui ultimo nodo è il nodo che vogliamo inserire.

Per quanto riguarda la stampa ci limitiamo a fare un ciclo che iteri sino a quando non terminano gli elementi da stampare. Ad ogni iterazione, si stampa il campo data del nodo che si sta esaminando.

Vediamo un disegno.

Cancellazione per chiave

L'idea è che, dato il dato da rimuovere dalla lista, si cancella la prima occorrenza che troviamo. Seguiremo i seguenti passi:

1. Si cerca l'occorrenza dell'elemento;
2. Se trovo l'elemento, ho tre casi:
   1. L'elemento trovato è la testa della lista, per cui si aggiorna il puntatore della testa e si lascia che il garbage collector si occupi del nodo non raggiungibile;
   2. L'elemento trovato è all'interno della lista o alla fine, per cui si dovrà cercare l'elemento precedente all'occorrenza trovata e si aggiorna il suo puntatore next.
3. Se non trovo l'elemento, non faccio nulla.

Vediamo il codice:

public static LinkedList deleteByKey(LinkedList list, int key) { 

        Node currNode = list.head, prev = null; 
        /*CASO 1: se l'elemento da eliminare è la testa,
          aggiorno il puntatore.*/
        if (currNode != null && currNode.data == key) { 

            list.head = currNode.next; // aggiorno puntatore testa
            // Return the updated List 
            return list; 
        } 
        /*CASO 2: l'elemento si trova da qualche altra parte*/
        // Cerco il dato da eliminare, 
        // tenendo traccia del nodo precedente 
        // e quando è necessario, cambio currNode.next 

        while (currNode != null && currNode.data != key) { 
            // se currNode non contiene il dato
            // passa al nodo successivo

            prev = currNode; 

            currNode = currNode.next; 

        } 
        // Se la chiave è presente, dovrebbe trovaris in currNode
        // Per cui currNode non dovrebbe essere nullo 

        if (currNode != null) { 

            // Dal momento che il dato è contenuto in currNode 
            // lo stacco dalla lista

            prev.next = currNode.next; 
        } 

        // CASO 3: la chiave non è presente

        // Se la chiave non è presente, currNode è null

        if (currNode == null) { 

            System.out.println(key + " non trovato"); 

        } 
        // restituisce la lista
        return list; 
    } 

Alcune varianti della cancellazione potrebbero comportare la cancellazione in testa, la cancellazione in coda o la cancellazione in una determinata posizione.

Vediamo con un disegno.

Conclusioni

Abbiamo visto brevemente come una lista concatenata può funzionare. Notiamo che l'implementazione fornita è quella del linguaggio Java, ma potrebbe essere tranquillamente convertita in altri linguaggi che mettano a disposizione meccanismi adeguati. Conoscere le logiche di funzionamento di queste strutture può tornare molto utile nel momento in cui dobbiamo fare del debug piuttosto complicato.

Vedremo in seguito un'implementazione che funziona allo stesso modo, ma con caratteristiche diverse, siccome qui diamo per scontato la presenza dell'elemento null. Vedremo un'implementazione dove una specifica classe rappresenterà il nodo vuoto.

Java mette a disposizione classi specifiche che implementano i meccanismi di una lista concatenata. Vedremo in seguito qualche esempio.

In sostanza, questo è uno di quei casi dove la teoria ci viene in soccorso.

Alessio Mungelli

Computer Science student at UniTo (University of Turin), Network specializtion, blogger and writer. I am a kind of expert in Java desktop developement with interests in AI and web developement. Unix lover (but not Windows hater). I am interested in Linux scripting. I am very inquisitive and I love learning new stuffs.