Linked List in Java

Linked List in Java: la linked list è una struttura dati dinamica, composta da nodi, ognuno contente la parte dell’informazione e il link al nodo successivo, possiamo rappresentarla graficamente nel seguente modo

Singly linked list
Singly linked list

Case study

Vogliamo realizzare una struttura dati per memorizzare delle note, non utilizzeremo gli array di oggetti ma una Linked List in quanto non vogliamo stabilire una dimensione massima per il numero di note

Classe Note

package spacecoding.data.linkedlist;

public class Note {
    private String title;
    private String body;
    private int priority;
    public Note(String title, String body, int priority) {
        this.title = title;
        this.body = body;
        this.priority = priority;
    }
    public String getTitle() {
        return title;
    }
    public void setTitle(String title) {
        this.title = title;
    }
    public String getBody() {
        return body;
    }
    public void setBody(String body) {
        this.body = body;
    }
    public int getPriority() {
        return priority;
    }
    public void setPriority(int priority) {
        this.priority = priority;
    }
    @Override
    public String toString() {
        return "Note{" +
                "title='" + title + '\'' +
                ", body='" + body + '\'' +
                ", priority=" + priority +
                '}';
    }
}

Classe nodo

La classe nodo ha due attributi, info e link, conseguentemente al nostro che study la parte info è un oggetto della classe Note. Il link è un oggetto della classe Nodo.

package spacecoding.data.linkedlist;

public class Nodo {
    private Note info;
    private Nodo link;

    public Nodo(Note info){
        this.info=info;
        link=null;
    }
    public void setInfo(Note info){
        this.info=info;
    }
    public Note getInfo(){
        return info;
    }
    public void setLink(Nodo link){
        this.link=link;
    }
    public Nodo getLink(){
        return link;
    }
}

Classe Lista (Linked List in Java)

La classe Lista rappresenta il nostro array dinamico (Linked List) di oggetti della classe Note, ha due attributi, il primo che è un Nodo e rappresenta la testa della lista (head) ed il secondo un intero che rappresenta il numero di elementi della lista stessa

    private Nodo head;
    private int elementi;
    public Lista(){
        head=null;
        elementi=0;
    }

inserisci in testa

Affinché il codice sia pulito scriviamo un metodo per creare un nodo

public Nodo creaNodo(Note nota, Nodo link){
        Nodo nuovoNodo=new Nodo(nota);
        nuovoNodo.setLink(link);
        return nuovoNodo;
}

di conseguenza il metodo per inserire in testa

public void inserisciInTesta(Note nota){
      head= creaNodo(nota,head);
      elementi++;
}

Nota che assegniamo il nodo creato ad head.

inserisci in coda

Nell’inserimento in coda dopo che si crea il nuovo elemento, ci si deve posizionare sull’ultimo nodo mediante un reference e collegare ad esso il nuovo nodo

public void inserisciInCoda(Note nota){
        if(head==null){
            inserisciInTesta(nota);
        }else{
            try{
                Nodo p=getLinkPosizione(elementi);
                p.setLink(creaNodo(nota,null));
                elementi++;
            }catch(ListaException e){

            }
        }
}

inserisci in posizione

Per l’inserimento in posizione dopo aver creato il nuovo elemento dobbiamo scorrere la lista fino al nodo precedente la posizione di inserimento e settare i vari link nel seguente modo:

public void inserisciInPosizione(Note nota,int posizione) throws ListaException{
        if(posizione<=1){
            inserisciInTesta(nota);
        }else{
            if(elementi<posizione){
                inserisciInCoda(nota);
            }else{
                Nodo p=getLinkPosizione(posizione-1);
                p.setLink(creaNodo(nota,p.getLink()));
            }
        }
}

metodo elimina in testa

public void eliminaIntesta() throws ListaException{
        if(head==null)
            throw new ListaException("Lista vuota");
        head=head.getLink();
        elementi--;
}

elimina in coda

 public void  eliminaInCoda() throws ListaException{
        if(head==null)
            throw new ListaException("Lista vuota");
        Nodo p=getLinkPosizione(elementi-1);
        p.setLink(null);
        elementi--;
}

elimina in posizione

   public void eliminaInPosizione(int posizione) throws ListaException{
        if(posizione==1){
            eliminaIntesta();
        }else{
            if(posizione==elementi){
                eliminaInCoda();
            }else{
                Nodo ps=getLinkPosizione(posizione);
                Nodo pp=getLinkPosizione(posizione-1);
                pp.setLink(ps.getLink());
                elementi--;
            }
        }
}

Test Classe Lista

Concludendo, testiamo la nostra linked list con un semplice programma

package spacecoding.data.linkedlist;
public class TestLista {
    public static void main(String[] args) {
        Note nota1=new Note("Ricerca sulle lontre","Kotaro e Hana",1);
        Note nota2=new Note("Appunti di PuffoGino","dormire oggi",1);
        Note nota3=new Note("Appunti di Nino","cercare più crocchini",1);
        Lista lista=new Lista();
        lista.inserisciInTesta(nota1);
        lista.inserisciInCoda(nota2);
        lista.inserisciInTesta(nota3);
        System.out.println("Ci sono : "+lista.getElementi()+" elementi memorizzati");
        System.out.println(lista.elenco());
        try {
            lista.inserisciInPosizione(nota1,4);
        } catch (ListaException e) {
            throw new RuntimeException(e);
        }
        System.out.println("Ci sono : "+lista.getElementi()+" elementi memorizzati");
        System.out.println(lista.elenco());
        try {
            lista.eliminaIntesta();
        } catch (ListaException e) {
            throw new RuntimeException(e);
        }
        System.out.println("Ci sono : "+lista.getElementi()+" elementi memorizzati");
        System.out.println(lista.elenco());

    }
}

Pubblicato da Carlo Contardi

Carlo Contardi, docente di informatica e sviluppatore Full Stack, condivide la sua passione per la programmazione e l’informatica attraverso il suo blog Space Coding. Offre preziosi consigli e soluzioni pratiche a chi vuole imparare a programmare o migliorare le proprie abilità. 🚀👨‍💻

Translate »