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

Un approccio a Java: Il ciclo while

Ciao a tutti e bentornati! Dopo aver fatto una breve, ma corposa, introduzione sui cicli, andiamo oggi a vedere finalmente le prime implementazioni che utilizzano quello che abbiamo definito ciclo precondizionale. In Java, come…

Un approccio a Java: I cicli - Introduzione

Ciao a tutti e bentornati! Sino ad ora, abbiamo parlato di variabili e di strutture di selezione, andando a considerare alcuni degli aspetti fondamentali di questi due concetti. Teoricamente, per…

Un approccio a Java: strutture di selezione - casi d'uso

Ciao a tutti e bentornati! Sino ad ora ci siamo preoccupati di fare una carrellata quanto più completa riguardo i concetti fondamentali di cui abbiamo bisogno per approcciarci all'utilizzo delle…

Un approccio a Java: operatori booleani

La volta precedente, abbiamo ampiamente parlato delle variabili booleane, cercando di delineare quali siano le principali operazioni che si possono effettuare proprio a livello pratico.  Di tutti i casi esaminati, non abbiamo…

Un approccio a Java: le variabili booleane

Ciao a tutti e bentornati! La volta precedente, ho fatto un'introduzione alle strutture condizionali, definendo il loro funzionamento. Prima di poter dare qualche esempio pratico, è necessario chiarire in che modo ci…

Un approccio a Java: strutture condizionali

Ciao a tutti e bentornati! Le volte precedenti abbiamo introdotto il concetto di variabile, tentando di definire alcuni concetti basilari a riguardo.  Alcune situazioni fanno però intuire come il solo concetto…

Un approccio a Java: Le variabili - caso d'uso

Ciao a tutti amici e bentornati! Dopo l'introduzione fatta sulle variabili, cerchiamo di analizzare alcune criticità che si possono presentare in situazioni alquanto comuni. Partiamo quindi analizzando degli esempi pratici.  Esempio 1: divisione…

Un approccio a Java: Le variabili

Ciao a tutti e bentornati! Quest'oggi inizieremo un percorso che ci porterà a studiare, ed eventualmente ripassare, quelle che sono le basi della programmazione. Inizieremo parlando di variaibli. Introduzione Chiunque voglia approcciarsi al…

Hashmap con Concatenamento: hashing, collisioni e prime funzioni

Oggi andremo a vedere dei concetti strettamente legati alle hashmap. I concetti che andremo a vedere sono quelli di hashing e collisioni. Hashing L'idea dell'hashing con concatenamento è quella di creare una sorta di array di…

Hashmap con concatenamento: liste di trabocco

In questa breve serie di articoli andremo a vedere com'è possibile realizzare in C la struttura dati Hashmap. Nell'implementazione andremo ad usare le liste doppiamente concatenate come strutture dati ausiliarie. Andiamo…

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…