Come dice il nome stesso, una lista concatenata o linkata, dall’inglese “Linked list”, è una lista di elementi collegati in sequenza tra di loro. Gli elementi di una lista sono generalmente chiamati nodi. Ciascun nodo è costituito dal suo valore e da un riferimento al nodo successivo nella lista. Una lista ha un nodo head che identifica il suo primo elemento ed un nodo tail che indica l’ultimo elemento della lista inserito.
Iniziamo quindi a definire la struttura Java che rappresenterà i nostri nodi:
class Node {
private int value;
private Node next;
public Node(int value) {
this.value = value;
}
public int getValue() { return this.value;}
public Node getNext() { return this.next; }
public void setNext(Node pNext) { this.next = pNext;}
}
Un nodo contiene, come abbiamo detto, un valore che in questo esempio supponiamo essere un intero ed un riferimento al nodo sucessivo. L’ultimo nodo della lista avrà null come valore del campo “next”, non avendo ulteriori nodi dopo di lui. Inoltre, una lista è caratterizzata dalla sua dimensione, cioè dal numero di elementi che contiene. Possiamo quindi iniziare a definire la classe che rappresenta la nostra lista:
public class MyLinkedList {
private Node head;
private Node tail;
private int size;
public int getSize() { return this.size; }
}
Una volta che abbiamo definito i campi che caratterizzano una lista linkata, passiamo ad analizzare quali sono le principali operazioni necessarie per manipolarla ed utilizzarla.
Le operazioni fondamentali che definiamo sulla nostra lista sono:
- Inserimento di un elemento
- In fondo alla lista
- All’inizio della lista
- Alla posizione x della lista
- Rimozione di un elemento
- Dall’inizio della lista
- Dal fondo della lista
- Stampa di tutti gli elementi della lista
Partiamo con le operazioni di inserimento e vediamo quali sono le azioni necessarie per inserire un nuovo elemento al fondo della lista.
Occorre sostanzialmente analizzare due casi:
- Nel caso in cui la lista sia vuota basta far puntare sia head che tail al nuovo nodo.
- Nel caso in cui la lista contenga già degli elementi, come possiamo vedere dall’immagine seguente, occorre invece:
- Far puntare il campo next del nodo tail al nuovo nodo da inserire
- Aggiornare tail in modo che punti all’ultimo nodo
- Incrementare la dimensione della lista
Proviamo a tradurre quanto illustrato in figura in un metodo java, che chiamiamo “insert”:
class Node {
private int value;
private Node next = null;
public Node(int value) {
this.value = value;
}
public int getValue() { return this.value;}
public Node getNext() { return this.next; }
public void setNext(Node pNext) { this.next = pNext;}
}
public class MyLinkedList {
private Node head;
private Node tail;
private int size;
public int getSize() { return this.size; }
public void insert (Node ele) {
if (this.head == null) {
this.tail = ele;
this.head = this.tail;
}
else {
this.tail.setNext(ele);
this.tail = ele;
}
this.size++;
}
}
Una volta implementato il metodo “insert”, scriviamo un programmino di test per vedere se funziona e se gli elementi vengono inseriti correttamente. Prima però dobbiamo ridefinire il metodo toString() della nostra classe MyLinkedList, in modo che ci fornisca in output una rappresentazione leggibile dello stato delle liste.
Possiamo ad esempio implementarlo in questo modo, in cui facciamo restituire la situazione completa della lista, quindi la sua dimensione, il nodo head, il nodo tail e la sequenza di tutti gli elementi contenuti:
@Override
public String toString(){
StringBuilder ret = null;
if ((this.head != null) && (this.tail != null)) {
ret = new StringBuilder("[Dimensione: " + this.size
+ ", Head: "
+ this.head.getValue()
+ ", Tail: "
+ this.tail.getValue()
+ "] Elementi: ");
Node tmp = this.head;
while (tmp != null) {
ret.append(tmp.getValue() + " -> ");
tmp = tmp.getNext();
}
ret.append("/");
}
return ret == null ? "[null]" : ret.toString();
}
A questo punto aggiungiamo un main in cui creiamo una lista ed inseriamo alcuni elementi e, dopo ogni inserimento, stampiamo il risultato in output.
class Node {
private int value;
private Node next = null;
public Node(int value) {
this.value = value;
}
public int getValue() { return this.value;}
public Node getNext() { return this.next; }
public void setNext(Node pNext) { this.next = pNext;}
}
public class MyLinkedList {
private Node head;
private Node tail;
private int size;
public int getSize() { return this.size; }
public void insert (Node ele) {
if (this.head == null) {
this.tail = ele;
this.head = this.tail;
}
else {
this.tail.setNext(ele);
this.tail = ele;
}
this.size++;
}
@Override
public String toString(){
StringBuilder ret = null;
if ((this.head != null) && (this.tail != null)) {
ret = new StringBuilder("[Dimensione: " + this.size
+ ", Head: "
+ this.head.getValue()
+ ", Tail: "
+ this.tail.getValue()
+ "] Elementi: ");
Node tmp = this.head;
while (tmp != null) {
ret.append(tmp.getValue() + " -> ");
tmp = tmp.getNext();
}
ret.append("/");
}
return ret == null ? "[null]" : ret.toString();
}
public static void main (String args[])
{
MyLinkedList ll = new MyLinkedList();
System.out.println(ll);
ll.insert(new Node(10));
System.out.println(ll);
ll.insert(new Node(25));
System.out.println(ll);
ll.insert(new Node(12));
System.out.println(ll);
ll.insert(new Node(20));
System.out.println(ll);
}
}
Il risultato dell’esecuzione del programma di test è il seguente:
[null] [Dimensione: 1, Head: 10, Tail: 10] Elementi: 10 -> / [Dimensione: 2, Head: 10, Tail: 25] Elementi: 10 -> 25 -> / [Dimensione: 3, Head: 10, Tail: 12] Elementi: 10 -> 25 -> 12 -> / [Dimensione: 4, Head: 10, Tail: 20] Elementi: 10 -> 25 -> 12 -> 20 -> /
Volendo possiamo anche fornire l’overload del metodo “insert” che prende come parametro un intero e costruisce l’oggetto Node.
public void insert(int value) {
Node ele = new Node(value);
if (this.head == null) {
this.tail = ele;
this.head = this.tail;
}
else {
this.tail.setNext(ele);
this.tail = ele;
}
ele = null;
this.size++;
}
Modificando il main precedente, utilizzando i due diversi overload di insert per creare i nodi, otteniamo lo stesso risultato.
public static void main (String args[])
{
MyLinkedList ll = new MyLinkedList();
System.out.println(ll);
ll.insert(new Node(10));
System.out.println(ll);
ll.insert(25);
System.out.println(ll);
ll.insert(new Node(12));
System.out.println(ll);
ll.insert(20);
System.out.println(ll);
}
Dopo aver implementato i metodi per inserire degli elementi al fondo della lista, implementiamo quello che ci permette di inserire un nuovo elemento in testa alla lista.
Anche qui abbiamo i due casi:
- Nel caso in cui la lista sia vuota basta far puntare sia head che tail al nuovo nodo.
- Nel caso in cui la lista contenga già degli elementi, come possiamo vedere dall’immagine seguente, occorre invece:
- Far puntare il campo next del nuovo nodo al nodo head
- Aggiornare la reference head in modo che punti al nuovo nodo
- Incrementare la dimensione della lista
Implementiamo nella nostra classe MyLinkedList il metodo “headInsert”:
public void headInsert(Node ele)
{
if (this.head == null) {
this.head = ele;
this.tail = this.head;
}
else {
ele.setNext(this.head);
this.head = ele;
}
this.size++;
}
Modifichiamo il nostro main di test in modo che crei una lista inserendo gli elementi utilizzando entrambi i metodi “insert” e “headInsert”
public static void main (String args[])
{
MyLinkedList ll = new MyLinkedList();
System.out.println(ll);
ll.insert(new Node(10));
System.out.println(ll);
ll.headInsert(25);
System.out.println(ll);
ll.headInsert(new Node(12));
System.out.println(ll);
ll.insert(20);
System.out.println(ll);
}
Il risultato di questa nuova esecuzione è il seguente:
[null] [Dimensione: 1, Head: 10, Tail: 10] Elementi: 10 -> / [Dimensione: 2, Head: 25, Tail: 10] Elementi: 25 -> 10 -> / [Dimensione: 3, Head: 12, Tail: 10] Elementi: 12 -> 25 -> 10 -> / [Dimensione: 4, Head: 12, Tail: 20] Elementi: 12 -> 25 -> 10 -> 20 -> /
Come vediamo viene inserito il nodo 10, poi headInsert inserisce 25 in testa, poi viene ancora inserito 12 in testa ed infine 20 al fondo, con insert.
Infine, vediamo l’ultimo dei metodi di inserimento degli elementi nella lista, cioè quello che permette di inserire un nuovo elemento in una determinata posizione x.
In questo caso identifichiamo 3 casistiche:
- La posizione x è compresa nel numero di elementi della lista
- La posizione x è minore di zero
- In questo caso inseriamo l’elemento all’inizio, senza generare un errore.
- La posizione x è maggiore del numero di elementi presenti
- In questo caso inseriamo l’elemento in fondo alla lista, senza generare un errore.
Nel caso di inserimento dell’elemento in una posizione x “valida” occorre:
- Scorrere la lista fino alla posizione desiderata x -1
- Far puntare il campo next del nuovo nodo al campo next del nodo in posizione x-1
- Far puntare il campo next del nodo in posizione x-1 al nuovo elemento
- incrementare la dimensione della lista
L’immagine seguente illustra il procedimento appena descritto:
Aggiungiamo alla nostra classe MyLinkedList il metodo “posInsert” che implementa questa operazione:
public void posInsert(Node ele, int pos)
{
if (pos <= 0) {
this.headInsert(ele);
return;
}
if (pos >= (this.size-1)) {
this.insert(ele);
return;
}
Node tmp = this.head;
int i = 0;
while(i < (pos-1))
{
tmp = tmp.getNext();
i++;
}
ele.setNext(tmp.getNext());
tmp.setNext(ele);
tmp = null;
this.size++;
}
Modifichiamo nuovamente il programma di test, aggiungendo alla lista alcuni elementi utilizzando questo nuovo metodo. Al fine di effettuare un test esaustivo, inseriamo un elemento per ciascun caso precedentemente identificato, quindi x compreso nella lista, x minore di 0 ed x maggiore della dimensione della lista.
class Node {
private int value;
private Node next = null;
public Node(int value) {
this.value = value;
}
public int getValue() { return this.value;}
public Node getNext() { return this.next; }
public void setNext(Node pNext) { this.next = pNext;}
}
public class MyLinkedList {
private Node head;
private Node tail;
private int size;
public int getSize() { return this.size; }
public void insert (Node ele) {
if (this.head == null) {
this.tail = ele;
this.head = this.tail;
}
else {
this.tail.setNext(ele);
this.tail = ele;
}
this.size++;
}
public void insert (int value) {
Node ele = new Node(value);
if (this.head == null) {
this.tail = ele;
this.head = this.tail;
}
else {
this.tail.setNext(ele);
this.tail = ele;
}
ele = null;
this.size++;
}
public void headInsert(Node ele)
{
if (this.head == null) {
this.head = ele;
this.tail = this.head;
}
else {
ele.setNext(this.head);
this.head = ele;
}
this.size++;
}
public void posInsert(Node ele, int pos)
{
if (pos <= 0) {
this.headInsert(ele);
return;
}
if (pos > (this.size-1)) {
this.insert(ele);
return;
}
Node tmp = this.head;
int i = 0;
while(i < (pos-1))
{
tmp = tmp.getNext();
i++;
}
ele.setNext(tmp.getNext());
tmp.setNext(ele);
tmp = null;
this.size++;
}
@Override
public String toString(){
StringBuilder ret = null;
if ((this.head != null) && (this.tail != null)) {
ret = new StringBuilder("[Dimensione: " + this.size
+ ", Head: "
+ this.head.getValue()
+ ", Tail: "
+ this.tail.getValue()
+ "] Elementi: ");
Node tmp = this.head;
while (tmp != null) {
ret.append(tmp.getValue() + " -> ");
tmp = tmp.getNext();
}
ret.append("/");
}
return ret == null ? "[null]" : ret.toString();
}
public static void main (String args[])
{
MyLinkedList ll = new MyLinkedList();
System.out.println(ll);
ll.insert(new Node(10));
System.out.println(ll);
ll.insert(25);
System.out.println(ll);
ll.insert(new Node(12));
System.out.println(ll);
ll.posInsert(new Node(30), 2);
System.out.println(ll);
ll.posInsert(new Node(15), -1);
System.out.println(ll);
ll.posInsert(new Node(20), 10);
System.out.println(ll);
}
}
Il risultato prodotto è il seguente:
[null] [Dimensione: 1, Head: 10, Tail: 10] Elementi: 10 -> / [Dimensione: 2, Head: 10, Tail: 25] Elementi: 10 -> 25 -> / [Dimensione: 3, Head: 10, Tail: 12] Elementi: 10 -> 25 -> 12 -> / [Dimensione: 4, Head: 10, Tail: 12] Elementi: 10 -> 25 -> 30 -> 12 -> / [Dimensione: 5, Head: 15, Tail: 12] Elementi: 15 -> 10 -> 25 -> 30 -> 12 -> / [Dimensione: 6, Head: 15, Tail: 20] Elementi: 15 -> 10 -> 25 -> 30 -> 12 -> 20 -> /
Come possiamo vedere:
- Il valore 30 viene inserito in posizione 2 (partendo la numerazione degli elementi da 0)
- Il valore 15 viene inserito ad inizio lista (avendo -1 come posizione specificata)
- Il valore 20 viene inserito a fondo lista (avendo 20 come posizione specificata, mentre la lista contiene solo 5 elementi al momento del suo inserimento)
Dopo aver analizzato tutte le operazioni di inserimento degli elementi in una lista linkata, passiamo all'analisi dei metodi per la rimozione degli elementi dalla lista.
Anche per la rimozione consideriamo i due casi:
- Rimozione dalla testa della lista
- Rimozione dal fondo della lista
Il primo caso è molto semplice: basta semplicemente "spostare" la reference head affinchè punti all'elemento successivo a quello attuale.
La figura seguente illustra l'operazione:
Implementare il relativo metodo "removeFirst" in Java è altrettanto facile:
public void removeFirst(){
if (this.head != null) {
this.head = this.head.getNext();
this.size--;
}
}
Aggiungiamo qualche operazione di questo tipo nel main del programma di test:
public static void main (String args[])
{
MyLinkedList ll = new MyLinkedList();
System.out.println(ll);
ll.insert(new Node(10));
System.out.println(ll);
ll.insert(25);
System.out.println(ll);
ll.insert(new Node(12));
System.out.println(ll);
ll.posInsert(new Node(30), 2);
System.out.println(ll);
ll.removeFirst();
System.out.println(ll);
ll.posInsert(new Node(15), -1);
System.out.println(ll);
ll.posInsert(new Node(20), 10);
System.out.println(ll);
ll.removeFirst();
System.out.println(ll);
}
Il risutalto che otteniamo è il seguente:
[null] [Dimensione: 1, Head: 10, Tail: 10] Elementi: 10 -> / [Dimensione: 2, Head: 10, Tail: 25] Elementi: 10 -> 25 -> / [Dimensione: 3, Head: 10, Tail: 12] Elementi: 10 -> 25 -> 12 -> / [Dimensione: 4, Head: 10, Tail: 12] Elementi: 10 -> 25 -> 30 -> 12 -> / [Dimensione: 3, Head: 25, Tail: 12] Elementi: 25 -> 30 -> 12 -> / [Dimensione: 4, Head: 15, Tail: 12] Elementi: 15 -> 25 -> 30 -> 12 -> / [Dimensione: 5, Head: 15, Tail: 20] Elementi: 15 -> 25 -> 30 -> 12 -> 20 -> / [Dimensione: 4, Head: 25, Tail: 20] Elementi: 25 -> 30 -> 12 -> 20 -> /
La prima chiamata a "removeFirst" rimuove l'elemento 10 dalla testa della lista e decrementa la dimensione a 3, mentre la seconda chiamata rimuove l'elemento 15 dalla testa e decrementa la dimensione della lista a 4 elementi.
Infine, analizziamo l'operazione di rimozione di un elemento dal fondo della lista.
Per eliminare un elemento dalla fine della lista occorre:
- scorrere la lista fino al penultimo elemento
- far puntare tail a questo nodo
- settare il campo next di tail a null
- decrementare la dimensione della lista
L'immagine seguente illustra il procedimento:
Implementiamo il metodo all'interno della nostra classe MyLinkedList
public void removeLast(){
if (this.head == null) {
return;
}
if (this.head.getNext() == null) {
this.head = null;
this.size--;
return;
}
Node tmp = this.head;
while(tmp.getNext().getNext() != null)
{
tmp = tmp.getNext();
}
this.tail = tmp;
this.tail.setNext(null);
tmp = null;
this.size--;
}
Come sempre testiamo il metodo, inserendo qualche chiamata "removeLast" nel nostro main di test:
public static void main (String args[])
{
MyLinkedList ll = new MyLinkedList();
System.out.println(ll);
ll.insert(new Node(10));
System.out.println(ll);
ll.insert(25);
System.out.println(ll);
ll.insert(new Node(12));
System.out.println(ll);
ll.posInsert(new Node(30), 2);
System.out.println(ll);
ll.removeFirst();
System.out.println(ll);
ll.posInsert(new Node(15), -1);
System.out.println(ll);
ll.posInsert(new Node(20), 10);
System.out.println(ll);
ll.removeFirst();
System.out.println(ll);
ll.removeLast();
System.out.println(ll);
ll.removeLast();
System.out.println(ll);
}
Il risultato ottenuto è il seguente:
[null] [Dimensione: 1, Head: 10, Tail: 10] Elementi: 10 -> / [Dimensione: 2, Head: 10, Tail: 25] Elementi: 10 -> 25 -> / [Dimensione: 3, Head: 10, Tail: 12] Elementi: 10 -> 25 -> 12 -> / [Dimensione: 4, Head: 10, Tail: 12] Elementi: 10 -> 25 -> 30 -> 12 -> / [Dimensione: 3, Head: 25, Tail: 12] Elementi: 25 -> 30 -> 12 -> / [Dimensione: 4, Head: 15, Tail: 12] Elementi: 15 -> 25 -> 30 -> 12 -> / [Dimensione: 5, Head: 15, Tail: 20] Elementi: 15 -> 25 -> 30 -> 12 -> 20 -> / [Dimensione: 4, Head: 25, Tail: 20] Elementi: 25 -> 30 -> 12 -> 20 -> / [Dimensione: 3, Head: 25, Tail: 12] Elementi: 25 -> 30 -> 12 -> / [Dimensione: 2, Head: 25, Tail: 30] Elementi: 25 -> 30 -> /
Post interessantissimo ed esposto in maniera chiara.
Ho solo una precisazione da fare (giusto per correttezza del codice).
Ad un certo punto in main effettui una chiamata a:
ll.headInsert(25);
System.out.println(ll);
nel post pero’ hai inserito solo un metodo headInsert che accetta un argomento di tipo Node. Al pari del metodo insert, anche qui e’ necessario fare un overload di headInsert(Node ele) con headInsert(int value):
public void headInsert(int value) {
Node ele = new Node(value);
if (this.head == null) {
this.head = ele;
this.tail = this.head;
} else {
ele.setNext(this.head);
this.head = ele;
}
this.size++;
}
Grazie mille ancora
Buona sera,
mi viene spontaneo chiedere ma se il dato invece di essere un solo valore contiene campi di diverso tipo e se si devono copiare in un file di testo, come si sviluppa il tutto?
Buona sera,
mi viene spontaneo chiedere ma se il dato invece di essere un solo valore contiene campi di diverso tipo e se si devono copiare in un file di testo, come si sviluppa il tutto?