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:

Node

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.

insertion

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.

remove

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

 
 
Alessio Mungelli

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.

 
 
 

Articoli correlati

    Linux per Principianti: I permessi

    Nei precedenti articoli abbiamo fatto una breve introduzione al mondo Unix e nell'articolo successivo abbiamo parlato di comandi base per la gestione del file system. Oggi andremo a parlare di permessi. Come esempio prenderemo sempre…

    Linux Per Principianti: Terminale Ubuntu

    Ho introdotto nell'articolo precedente, consultabile qui, i concetti base relativi al mondo del pinguino. Oggi andiamo a vedere alcune operazioni di base che si possono svolgere mediante linea di comando su…

    Linux per Principianti: Introduzione

    Se hai pensato di migrare da Windows a un sistema operativo Unix, o Linux nello specifico ci sono cose che dovresti sapere. L'obiettivo è quello di dare le informazioni essenziali…

    Java Algoritmi di Ordinamento: Selection Sort

    Andiamo oggi ad analizzare in dettaglio un algoritmo di ordinamento non molto efficiente ma piuttosto utilizzato in diversi ambiti. Stiamo parlando del Selection Sort. Vediamo meglio in dettaglio. Intuizione L'idea alla base è quella…

    Java algoritmi di ordinamento: Merge Sort

    Andiamo oggi ad analizzare uno tra i migliori algoritmi di ordinamento: il Merge Sort. Detto anche algoritmo per fusione, fa parte della famiglia dei Divide and Conquer proprio come il Quick Sort. A differenza del…

    Java algoritmi di ordinamento: Quick Sort

    Bentornati in questa nostra panoramica sul mondo Java! Oggi andremo a parlare di un algoritmo di ordinamento tra i più celebri. Il Quick Sort. A differenza del precedentemente trattato Bubble Sort, Quick…

    Come creare un aplicazione Vue.js in 5 minuti

    Vue.js sta acquisendo sempre più popolarità, diventando un importante concorrente di framework come Angular o React.js. Come framework per i principianti, conquista i cuori dei giovani sviluppatori front-end e delle…

    Java algoritmi di ordinamento: Bubble Sort

    Programmando, nasce spesso la necessità di ordinare le collezioni di dati o oggetti che devono poi essere manipolate. Ordinare una lista può essere utile nei casi in cui si debbano…

    Java Design Pattern: Prototype Pattern

    Andremo ora a parlare di un pattern creazionale che ci permette di "copiare con classe". Sì, anche se sembra strano, il compito fondamentale di questo pattern è copiare. Sto parlando…

    Java Design Pattern: Builder Pattern

    Andiamo oggi a parlare di un pattern creazionale che in molte situazioni può rappresentare una valida alternativa alla costruzione di oggetti mediante costruttori: il Builder Pattern. La necessità di introdurre meccanismi…

    Java Design Pattern: Strategy Pattern

    Uno dei pattern che gode di una notevole popolarità ed è al contempo piuttosto semplice è lo Strategy Pattern. Membro della famiglia dei pattern comportamentali, ha il compito di gestire algoritmi,…

    Java Design Pattern: Factory Pattern

    Continuando il discorso sui design pattern iniziato precedentemente, andiamo oggi a vedere un altro pattern molto utilizzato: il Factory Method Pattern. Il GoF (Gang of Four Design Patterns) lo definisce così: Definisce…