La struttura dati catena (linked list) PDF

La struttura dati “catena” linked-list (capitolo 14) Department of Information Engineering  La struttura dati catena (linked list)...

La struttura dati “catena” linked-list (capitolo 14) Department of Information Engineering  La struttura dati catena (linked list) La catena o lista concatenata (linked list) non è un nuovo ADT, ma è una struttura dati alternativa all’array per la Department of Information Engineering realizzazione di ADT next Una catena è un insieme ordinato di nodi Ogni nodo è un oggetto che contiene dato un riferimento a un elemento (il dato) un riferimento al nodo successivo nella catena (next)  Catena inizio (head) fine (tail) next next next nu null ll Department of Information Engineering header dato dato dato Per agire sulla catena è sufficiente memorizzare il riferimento al suo primo nodo è comodo avere anche un riferimento all’ultimo nodo Il campo next dell’ultimo nodo contiene null Vedremo che è comodo avere un primo nodo senza dati, chiamato header  Catena vuota inizio (head) fine (tail) null null header Department of Information Engineering Per capire bene il funzionamento della catena, è necessario avere ben chiara la rappresentazione della catena vuota contiene il solo nodo header, che ha null in entrambi i suoi campi head e tail puntano entrambi al nodo header  Accesso ai nodi della catena inizio (head) fine (tail) next next next nu null ll Department of Information Engineering header dato dato dato Per accedere in sequenza a tutti i nodi della catena si parte dal riferimento head e si seguono i riferimenti contenuti nel campo next di ciascun nodo non è possibile scorrere la lista in senso inverso la scansione termina quando si trova il nodo con il valore null nel campo next  Nodo di una catena public class ListNode { //costruttori public ListNode() { element = null; next = null; } Notiamo una public ListNode(Object e, ListNode n) “stranezza” { element = e; next = n; Department of Information Engineering } la classe usa riferimenti //metodi pubblici a oggetti del tipo che public Object getElement() { return element; sta definendo } public ListNode getNext() Ciò è lecito e si usa { return next; } molto spesso quando si public void setElement(Object e) { element = e; rappresentano } “strutture a public void setNext(ListNode n) { next = n; definizione ricorsiva” } //campi di esemplare come la catena private Object element; private ListNode next; }  Nodo: incapsulamento eccessivo? A cosa serve l’incapsulamento in classi che hanno lo stato completamente accessibile tramite metodi? apparentemente a niente… Supponiamo di essere in fase di debugging: vogliamo Department of Information Engineering visualizzare un messaggio ogni volta che viene modificato il valore di una variabile di un nodo Senza incapsulamento occorre aggiungere enunciati in ogni punto del codice dove vengono usati i nodi Con incapsulamento è sufficiente inserire l’enunciato di visualizzazione all’interno dei metodi set che interessano I campi di esemplare possono essere modificate solo mediante l’invocazione del corrispondente metodo set terminato il debugging, per eliminare le visualizzazioni è sufficiente modificare il solo metodo set  Realizzazione di una catena Metodi da realizzare sono addFirst per inserire un oggetto all’inizio della catena addLast per inserire un oggetto alla fine della catena removeFirst per eliminare il primo oggetto della catena removeLast per eliminare l’ultimo oggetto della catena Department of Information Engineering getFirst per esaminare il primo oggetto getLast per esaminare l’ultimo oggetto IsEmpty e makeEmpty (la catena è un contenitore) Non vengono mai restituiti o ricevuti riferimenti ai nodi, ma sempre ai dati contenuti nei nodi Non si definisce un’interfaccia perché la catena non è un ADT (abbiamo esplicitamente indicato come deve essere realizzata, e non solo il suo comportamento) Si definisce l’eccezione EmptyLinkedListException per segnalare la condizione di catena vuota  La classe LinkedList (catena) public class LinkedList implements Container { // costruttore public LinkedList() { makeEmpty(); } //metodi pubblici public void makeEmpty() { head = tail = new ListNode(); } public boolean isEmpty() { return (head == tail); } public Object getFirst() // operazione O(1) { if (isEmpty()) throw new EmptyLinkedListException(); return head.getNext().getElement(); } public Object getLast() // operazione O(1) { if (isEmpty()) throw new EmptyLinkedListException(); return tail.getElement(); }... //vanno scritti i metodi addFirst,addLast,removeFirst,removeLast //campi di esemplare private ListNode head, tail; } class EmptyLinkedListException extends RuntimeException { } Department of Information Engineering Catena: i metodi addFirst e removeFirst  Catena: metodo addFirst inizio (head) fine (tail) next next nu null ll dato dato dato Department of Information Engineering inizio (head) fine (tail) nuovo nu next next nu nodo null ll ll dato dato dato inizio (head) fine (tail) next next next nu null ll dato dato dato  Catena: metodo addFirst public class LinkedList... {... public void addFirst(Object e) { //inserisco dato nello header attuale head.setElement(e); // creo un nuovo nodo con due riferimenti null ListNode n = new ListNode(); // collego il nuovo nodo allo header attuale n.setNext(head); // il nuovo nodo diventa lo header della catena head = n; // tail non viene modificato }... } Non esiste il problema di “catena piena” L’operazione è O(1)  Catena: metodo addFirst inizio (head) fine (tail) nu null ll Verifichiamo che tutto sia dato Department of Information Engineering corretto anche inserendo in inizio (head) fine (tail) una catena vuota nuovo nu nu nodo null ll ll Fare sempre attenzione ai dato casi limite inizio (head) fine (tail) next nu null ll dato  Catena: metodo addFirst alternativo Il codice di addFirst si può scrivere anche in modo più conciso public void addFirst(Object e) { Department of Information Engineering head.setElement(e); head = new ListNode(null, head); // funziona perché prima head viene USATO // (a destra) e solo successivamente viene // MODIFICATO (a sinistra) } public void addFirst(Object e) { head.setElement(e); ListNode n = new ListNode(); n.setNext(head); head = n; } È più “professionale”, anche se meno leggibile  Catena: metodo removeFirst inizio (head) fine (tail) next next nu null ll dato dato Department of Information Engineering inizio (head) fine (tail) nodo da next next nu eliminare null ll dato dato Il nodo viene eliminato dal garbage collector inizio (head) fine (tail) next nu null ll dato dato  Catena: metodo removeFirst public class LinkedList... {... public Object removeFirst() { Object e = getFirst();// delega a getFirst il Department of Information Engineering //controllo di lista vuota head = head.getNext();// aggiorno lo header head.setElement(null); return e; }... } L’operazione è O(1)  Catena: metodo removeFirst inizio (head) fine (tail) next nu null ll Verifichiamo che tutto sia corretto dato Department of Information Engineering anche rimanendo con una catena inizio (head) fine (tail) vuota next nu null ll Fare sempre attenzione ai casi dato limite inizio (head) fine (tail) nu null ll dato Department of Information Engineering removeLast Catena: i metodi addLast e  Catena: metodo addLast inizio (head) fine (tail) next next nu null ll dato dato dato Department of Information Engineering inizio (head) fine (tail) nuovo nodo next next next nu null ll dato dato dato inizio (head) fine (tail) next next next nu null ll dato dato dato  Catena: metodo addLast public class LinkedList... {... public void addLast(Object e) { tail.setNext(new ListNode(e, null)); Department of Information Engineering tail = tail.getNext(); //aggiorno il tail }... } Non esiste il problema di “catena piena” Anche questa operazione è O(1)  Catena: metodo addLast inizio (head) fine (tail) nu null ll Verifichiamo che tutto sia corretto dato Department of Information Engineering anche inserendo in una catena inizio (head) fine (tail) vuota nu Fare sempre null next ll attenzione ai casi limite dato inizio (head) fine (tail) next nu null ll dato  Catena: metodo removeLast inizio (head) fine (tail) spostamento next next next nu complesso null ll Department of Information Engineering dato dato dato inizio (head) fine (tail) next next next nu nodo da null ll eliminare dato dato dato inizio (head) fine (tail) next next nu null ll dato dato dato  Catena: metodo removeLast public class LinkedList... {... public Object removeLast() { Object e = getLast(); // L’ultimo nodo non ha un riferimento al penultimo! Department of Information Engineering // Bisogna cercare il penultimo nodo partendo dal primo // e andando avanti finche’ non si arriva alla fine ListNode temp = head; while (temp.getNext() != tail) temp = temp.getNext(); // a questo punto temp si riferisce al penultimo nodo tail = temp; tail.setNext(null); return e; }... } Purtroppo questa operazione è O(n)  Catena: metodo removeLast inizio (head) fine (tail) Verifichiamo che next nu tutto sia corretto null ll anche rimanendo Department of Information Engineering dato con una catena vuota inizio (head) fine (tail) Fare sempre nu nodo da attenzione ai casi null next ll eliminare limite dato inizio (head) fine (tail) nu null ll dato  Prestazioni dei metodi della Department of Information Engineering classe LinkedList  Header della catena La presenza del nodo header nella catena rende più semplici i metodi della catena stessa Department of Information Engineering in questo modo, non è necessario gestire i casi limite in modo diverso dalle situazioni ordinarie Senza usare il nodo header, le prestazioni asintotiche rimangono comunque le stesse Usando il nodo header si “spreca” un nodo per valori elevati del numero di dati nella catena questo spreco, in percentuale, è trascurabile  Prestazioni dei metodi di LinkedList Tutte le operazioni sulla catena sono O(1) tranne removeLast che è O(n) Department of Information Engineering si potrebbe pensare di tenere un riferimento anche al penultimo nodo, ma per aggiornare tale riferimento sarebbe comunque necessario un tempo O(n) Se si usa una catena con il solo riferimento head, anche addLast diventa O(n) per questo è utile usare il riferimento tail, che migliora le prestazioni di addLast senza peggiorare le altre e non richiede molto spazio di memoria  Ridimensionare una catena Non esiste il problema di “catena piena” non è mai necessario “ridimensionare” la catena Department of Information Engineering la JVM lancia l’eccezione OutOfMemoryError se viene esaurita la memoria disponibile (in particolare lo heap) Non c’è spazio di memoria sprecato (come negli array “riempiti solo in parte”) un nodo occupa però più spazio di una cella di array, almeno il doppio (contiene due riferimenti anziché uno)  Riassunto: la classe LinkedList public class LinkedList { public LinkedList() { makeEmpty(); } // costruttore public void makeEmpty() { head = tail = new ListNode(); } public boolean isEmpty() { return (head == tail); } public Object getFirst() // operazione O(1) { if (isEmpty()) throw new EmptyLinkedListException(); return head.getNext().getElement(); } public Object getLast() // operazione O(1) { if (isEmpty()) throw new EmptyLinkedListException(); return tail.getElement(); } //continua  Riassunto: la classe LinkedList //continua public void addFirst(Object e) { head.setElement(e);// inserisco dato in header attuale ListNode n = new ListNode(); // nuovo nodo n.setNext(head); // collego nuovo nodo a header attuale head = n; //il nuovo nodo diventa il nuovo header } // tail non viene modificato public Object removeFirst() { Object e = getFirst();// delega a getFirst controllo //di lista vuota head = head.getNext(); // aggiorno lo header head.setElement(null); return e; } public void addLast(Object e) { tail.setNext(new ListNode(e, null)); tail = tail.getNext(); } //continua 57  Riassunto: la classe LinkedList //continua public Object removeLast() { Object e = getLast(); // L’ultimo nodo non ha un riferimento al penultimo! // Bisogna cercare il penultimo nodo partendo dal primo // e andando avanti finche’ non si arriva alla fine ListNode temp = head; while (temp.getNext() != tail) temp = temp.getNext(); // a questo punto temp si riferisce al penultimo nodo tail = temp; tail.setNext(null); return e; } // campi di esemplare private ListNode head; private ListNode tail; } class EmptyLinkedListException extends RuntimeException { }  Riassunto: la classe ListNode public class ListNode { //costruttori public ListNode() { element = null; next = null; } public ListNode(Object e, ListNode n) { element = e; next = n; Department of Information Engineering } //metodi pubblici public Object getElement() { return element; } public ListNode getNext() { return next; } public void setElement(Object e) { element = e; } public void setNext(ListNode n) { next = n; } //campi di esemplare private Object element; private ListNode next; }  La classe interna ListNode Osserviamo che la classe ListNode, usata dalla catena, non viene mai usata al di fuori della catena stessa la catena non restituisce mai riferimenti a ListNode Department of Information Engineering la catena non riceve mai riferimenti a ListNode Per il principio dell’incapsulamento sarebbe preferibile che questa classe e i suoi dettagli non fossero visibili all’esterno della catena in questo modo una modifica della struttura interna della catena e/o di ListNode non avrebbe ripercussioni sul codice scritto da chi usa la catena È quindi più corretto definire ListNode come una classe interna a LinkedList  Riassunto: la classe LinkedList public class LinkedList {... //costruttori, metodi, campi di LinkedList come prima // ora definiamo ListNode come una classe interna privata private class ListNode //codice di ListNode come prima { //costruttori public ListNode() { element = null; next = null; } public ListNode(Object e, ListNode n) { element = e; next = n; } //metodi pubblici public Object getElement() { return element; } public ListNode getNext() { return next; } public void setElement(Object e) { element = e; } public void setNext(ListNode n) { next = n; } //campi di esemplare private Object element; private ListNode next; } } 61  Esercizio: realizzare pile e Department of Information Engineering code con catene  Pile e code realizzate con una catena Pile e code possono essere realizzate usando una catena invece di un array Pila: entrambe le estremità di una catena hanno, prese singolarmente, il comportamento di una pila Department of Information Engineering si può quindi realizzare una pila usando una delle due estremità della catena è più efficiente usare l’inizio della catena, perché le operazioni su tale estremità sono O(1) Coda: è sufficiente inserire gli elementi a un’estremità della catena e rimuoverli dall’altra estremità per ottenere il comportamento di una coda Affinché tutte le operazioni siano O(1) bisogna inserire alla fine e rimuovere all’inizio  Pila realizzata con una catena public class LinkedListStack implements Stack { public LinkedListStack() { list = new LinkedList(); } public void push(Object obj) { list.addFirst(obj); } Department of Information Engineering public Object pop() { return list.removeFirst(); } public Object top() { return list.getFirst(); } public void makeEmpty() { list.makeEmpty(); } public boolean isEmpty() { return list.isEmpty(); } private LinkedList list; }  Coda realizzata con una catena public class LinkedListQueue implements Queue { public LinkedListQueue() { list = new LinkedList(); } public void enqueue(Object obj) { list.addLast(obj); } Department of Information Engineering public Object dequeue() { return list.removeFirst(); } public Object getFront() { return list.getFirst(); } public void makeEmpty() { list.makeEmpty(); } public boolean isEmpty() { return list.isEmpty(); } private LinkedList list; }  Iteratori e iteratore in una catena Department of Information Engineering (capitolo 14)  Accedere a nodi di una catena Per eseguire operazioni sulla catena che necessitano di accedere ai nodi è necessario aggiungere metodi all’interno della classe LinkedList che è l’unica ad avere accesso ai nodi della catena Department of Information Engineering Potremmo volere, per esempio: Contare i nodi nella catena verificare la presenza di un particolare oggetto nella catena (algoritmo di ricerca) aggiungere/togliere elementi alla catena, anche in posizioni intermedie Questo limita molto l’utilizzo della catena come struttura dati definita una volta per tutte…  Accedere a nodi di una catena Esempio: vogliamo contare i nodi della catena È necessario scorrere tutta la catena Il codice va scritto dentro la classe LinkedList Department of Information Engineering public class LinkedList {... public int getSize() { ListNode temp = head.getNext(); int size = 0; while (temp != null) { size++; temp = temp.getNext(); } //se la catena è vuota size = 0 (giusto!) return size; }.... }  Accedere a nodi di una catena Vogliamo che la catena fornisca uno strumento per accedere ordinatamente a tutti i suoi elementi. Idea: scriviamo un metodo getHead che restituisce un riferimento al nodo header Department of Information Engineering public class LinkedList {... public ListNode getHead() { return head; }...} Questo approccio però non funziona Se la classe ListNode è public in LinkedList si viola l'incapsulamento, perché diventa possibile modificare lo stato della catena dall'esterno Se invece è private allora i nodi sono inaccessibili e il metodo getHead è totalmente inutile  Iteratore in una catena Soluzione del problema fornire all’utilizzatore della catena uno strumento con cui interagire con la catena per scandire i suoi nodi Department of Information Engineering Tale oggetto si chiama iteratore e ne definiamo prima di tutto il comportamento astratto Un iteratore rappresenta in astratto il concetto di posizione all’interno di una catena Un iteratore si trova sempre dopo un nodo e prima del nodo successivo (che può non esistere se l’iteratore si trova dopo l’ultimo nodo) In particolare, quando viene creato l’iteratore si trova dopo il nodo header  Iteratore in una catena ITERATORE inizio (head) fine (tail) nu Department of Information Engineering null ll header dato dato dato Un iteratore rappresenta in astratto il concetto di posizione all’interno di una catena la posizione è rappresentata concretamente da un riferimento a un nodo (il nodo precedente alla posizione dell’iteratore)  L'ADT ListIterator import java.util.NoSuchElementException; public interface ListIterator { Object next() throws NoSuchElementException; boolean hasNext(); void add(Object x); void remove() throws IllegalStateException; }  L'ADT ListIterator Possiamo immaginare un iteratore come un cursore in un elaboratore di testi Un nodo della catena corrisponde a un carattere Department of Information Engineering L’iteratore si trova sempre “tra due nodi”, come un cursore  Iteratore in una catena A questo punto, è sufficiente che la catena fornisca un metodo per creare un iteratore public class LinkedList Department of Information Engineering {... public ListIterator getIterator() {... }// dopo vediamo come scrivere questo metodo... } E si può scandire la catena senza accedere ai nodi LinkedList list = new LinkedList();... ListIterator iter = list.getIterator(); while(iter.hasNext()) System.out.println(iter.next()); // notare similitudine con StringTokenizer e Scanner  L’interfaccia Iterator in Java La libreria standard di Java definisce in java.util una interfaccia Iterator Department of Information Engineering Definisce in particolare i metodi next e hasNext Sempre in java.util si trova l’interfaccia ListIterator Estende Iterator Definisce altri metodi, tra cui add e remove L’interfaccia Iterator è implementata da una classe che abbiamo utilizzato molto spesso: Scanner Ha il metodo next Ha il metodo hasnext  Implementare ListIterator getIterator restituisce un riferimento a una interfaccia Quindi in realtà deve creare un oggetto di una classe che realizzi tale interfaccia Implementiamo ListIterator con la classe Department of Information Engineering LinkedListIterator I suoi oggetti sono costruiti solo all’interno di LinkedList e restituiti all’esterno solo tramite riferimenti a ListIterator Per un corretto funzionamento dell’iteratore occorre concedere a tale oggetto il pieno accesso alla catena in particolare, alla sua variabile di esemplare head Non vogliamo che l’accesso sia consentito ad altre classi Tutto questo ci porta a definire LinkedListIterator come una classe interna privata di LinkedList  La classe interna LinkedListIterator public class LinkedList {... //codice di LinkedList come prima... //incluso codice della classe privata ListNode public ListIterator getIterator() //metodo di LinkedList { //crea un iteratore posizionato al primo nodo della catena return new LinkedListIterator(head); } private class LinkedListIterator implements ListIterator { //costruttore public LinkedListIterator(ListNode h) { current = h; previous = null; } //metodi pubblici (dobbiamo ancora realizzarli) public boolean hasNext() {... } public Object next() {... } public void add(Object x) {... } public void remove() {... } //campi di esemplare private ListNode current;//nodo che precede pos. attuale private ListNode previous;//nodo che precede current } }  I metodi di LinkedListIterator import java.util.NoSuchElementException; public class LinkedList {... private class LinkedListIterator implements ListIterator {... //metodi pubblici hasNext, next public boolean hasNext() { return current.getNext() != null; } public Object next() { if (!hasNext()) throw new NoSuchElementException(); previous = current; current = current.getNext(); return current.getElement(); } //metodi pubblici add,remove (dobbiamo ancora realizzarli) public void add(Object x) {... } public void remove() {... } //campi di esemplare private ListNode current;//nodo che precede pos. attuale private ListNode previous;//nodo che precede current } }  Il metodo add di LinkedListIterator ITERATORE obj (inizio esecuzione) Department of Information Engineering inizio (head) fine (tail) nu null ll header ITERATORE dato (fine esecuzione) dato dato  Il metodo add di LinkedListIterator public void add(Object obj) { ListNode n = new ListNode(obj, current.getNext()); current.setNext(n); previous = current; //aggiorno riferimenti iteratore current = current.getNext(); //a subito dopo nuovo nodo if (!hasNext()) // se ho aggiunto all'ultimo nodo Department of Information Engineering LinkedList.this.tail = current; //aggiorno tail } Aggiunge il nuovo nodo e avanza di una posizione Se il nodo viene aggiunto alla fine della catena, allora bisogna anche aggiornare il riferimento tail della catena Nota sintattica: il riferimento LinkedList.this punta all'oggetto LinkedList all'interno di cui è stato creato l'iterator  Il metodo add di LinkedListIterator Se il nodo viene aggiunto alla fine della catena, allora bisogna anche aggiornare il riferimento tail della catena Nota sintattica: il riferimento LinkedList.this punta Department of Information Engineering all'oggetto LinkedList all'interno di cui è stato creato l'iterator  Il metodo remove di LinkedListIterator ITERATORE (fine esecuzione) ITERATORE (inizio esecuzione) Department of Information Engineering null inizio (head) fine (tail) nu null ll header dato dato dato dato  Il metodo remove di LinkedListIterator public void remove() throws IllegalStateException { if (previous == null) throw new IllegalStateException(); previous.setNext(current.getNext()); current = previous; // aggiorno riferimenti iteratore previous = null; // a subito prima del nodo rimosso if (!hasNext()) // se ho rimosso l'ultimo nodo LinkedList.this.tail = current; //aggiorno tail } L'iteratore non ha un riferimento al nodo prima di previous Quindi non posso aggiornare correttamente previous dopo la rimozione: gli assegno valore null, con la conseguenza che l'iteratore si trova in uno stato illegale dopo la rimozione Per questo motivo non si può invocare nuovamente remove. Invocando next o add previous verrà riaggiornato  Iteratori multipli nella stessa linked-list Se vengono creati più iteratori che agiscono sulla stessa lista (cosa perfettamente lecita, invocando il metodo iterator() più volte): Department of Information Engineering ognuno di essi mantiene il proprio stato, ovvero memorizza la propria posizione nella lista ogni iteratore può muoversi nella lista indipendentemente dagli altri tuttavia, dobbiamo usare una certa cautela quando utilizziamo gli iteratori per modificare la lista Per esempio, cosa succede se un iteratore rimuove il nodo che contrassegna la posizione di un altro iteratore?  Iteratori multipli nella stessa linked-list LinkedList list = new LinkedList() Iterator iter1 = list.iterator(); iter1.add(Integer.valueOf(1)); Department of Information Engineering Iterator iter2 = list.iterator(); // iter2 punta al primo elemento nell'elenco, 1 Iterator iter3 = list.iterator(); iter3.add(Integer.valueOf(2)); // 2 è diventato il primo elemento dell'elenco System.out.println(iter2.next()); // → 1 // iter2 non funziona correttamente!!  Operazioni su catene mediante un iteratore Department of Information Engineering  Catena: conteggio elementi Problema: data una catena e un riferimento a essa, si vuole sapere il numero di nodi che la compongono Soluzione: con un iteratore possiamo contare i nodi al di fuori del codice di LinkedList, in una classe qualsiasi public class MyClass Department of Information Engineering { public static void main(String[] args) { LinkedList list = new LinkedList();... // operazioni sulla catena int listSize = getSize(list); } public static int getSize(LinkedList list) { ListIterator iter = list.getIterator(); int size = 0; while (iter.hasNext()) { size++; iter.next(); // ignoro l’oggetto ricevuto } // perché devo solo contarli return size; } }  Catena: inserimento e rimozione Abbiamo visto l’inserimento e la rimozione di un elemento all’inizio e alla fine della catena, tramite i metodi addFirst, removeFirst, addLast, Department of Information Engineering removeLast Vogliamo estendere le modalità di funzionamento della catena per poter inserire e rimuovere elementi in qualsiasi punto della catena stessa abbiamo il problema di rappresentare il concetto di posizione nella catena in cui inserire (o da cui rimuovere) il nodo Possiamo usare di nuovo l’iteratore, e in particolare i suoi metodi add e remove  Catena: osservazioni finali Ci sono alcune differenze tra la nostra realizzazione della catena e la realizzazione della classe LinkedList proposta sul libro di testo Department of Information Engineering Usiamo un primo nodo “vuoto” “Sprechiamo” dello spazio in memoria Ma semplifichiamo la realizzazione dei metodi (non bisogna trattare i casi limite diversamente dagli altri) Usiamo un riferimento tail all’ultimo nodo Questo migliora le prestazioni di addLast senza peggiorare le altre e non richiede molto spazio di memoria Department of Information Engineering Catena doppia (doubly linked list)  Catena doppia La catena doppia (o lista doppiamente concatenata, doubly linked list) non è un nuovo ADT Department of Information Engineering Come la catena, è una struttura dati per la realizzazione di ADT Una catena doppia è un insieme ordinato di nodi ogni nodo è un oggetto che contiene un riferimento a un elemento (il dato) un riferimento al nodo successivo della lista (next) un riferimento al nodo precedente della lista (prev)  Catena doppia inizio (head) fine (tail) prev prev prev nu nu nu ll ll next next next nu ll ll Department of Information Engineering dato dato Dato che la struttura è simmetrica, si usano due nodi vuoti, uno a ciascun estremo della catena Tutto quanto detto per la catena (semplice) può essere agevolmente esteso alla catena doppia Il metodo removeLast diventa O(1) come gli altri metodi Un iteratore su catena doppia avrà anche un metodo per retrocedere di una posizione, oltre a quello per avanzare i metodi add e remove dell’iteratore si complicano