Informatica I - i metodi di una lista con iteratore

Il metodo add di LinkedListIterator

Il metodo add(Object obj) aggiunge un nuovo nodo e avanza di una posizione.

Codice:
ListNode n = new ListNode(obj, current.getNext());
current.setNext(n);

Se il nodo viene aggiunto alla fine della catena, bisogna anche aggiornare il riferimento tail. Infatti:

previous = current; // aggiorno riferimenti iteratore
current = current.getNext(); // a subito dopo nuovo nodo della catena.

if (!hasNext()) // se ho aggiunto all'ultimo nodo
LinkedList.this.tail = current; // aggiorno tail

Il metodo remove di LinkedListIterator

Il metodo remove() può generare un'eccezione di stato illegale (IllegalStateException) se usato impropriamente.

Codice:
if (previous == null) throw new IllegalStateException();
previous.setNext(current.getNext());

L'iteratore non ha un riferimento al nodo prima di previous, quindi non posso aggiornare correttamente previous dopo la rimozione:

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 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.

Conteggio elementi

Se si vuole sapere il numero di nodi che compongono una catena con un iteratore, possiamo contare i nodi al di fuori del codice di LinkedList, in una classe qualsiasi.

Codice:
public static int getSize(LinkedList list) {
  ListIterator iter = list.getIterator();
  int size = 0;
  while (iter.hasNext()) {
    size++;
    iter.next();
  }
  return size;
}

Catena doppia (doubly linked list)

Una catena doppia è un insieme ordinato di nodi. Ogni nodo è un oggetto che contiene:

• Un riferimento ad un elemento (il dato)
• Un riferimento al nodo successivo della lista (next)
• Un riferimento al nodo precedente della lista (prev)

Dato che la struttura è simmetrica, si usano due nodi vuoti, uno a ciascun estremo della catena.