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
- Case study
- Classe Note
- Classe Nodo
- Classe Lista
- Test Classe Lista
- Link utili (con link al codice completo delle classi)
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());
}
}