[JAVA] Realizzazione di una Lista doppiamente concatenata (LinkedList)

[R0ckY909]

Salve a tutti! Mi sono appena iscritto a questo bel forum, spero possiate aiutarmi col mio problema Allora, sono uno studente di ingegneria informatica e mi è stato assegnato un progetto dal mio prof. di programmazione da presentare entro la fine del corso: partendo da un interfaccia "Lista", fare una classe astratta "ListaAstratta" che estende l'interfaccia e poi fare un erede della classe astratta, chiamata "ListaConcatenata". Cercando qui, ho trovato un'altra discussione (http://forum.html.it/forum/showthread/t-1407146.html) che espone il mio stesso problema, ma non essendoci risposte, non ne ho tratto niente e quindi volevo riprendere la questione.
Io praticamente ho problemi con il listIterator (la remove non so come implementarla e previous si comporta in modo strano, non so se è c'è qualcosa con la add) e non so come implementare il metodo sort...

Questa è la traccia del progetto:

import java.util.*;

public interface Lista<T extends Comparable<? super T>> extends Iterable<T> {
	
	int size ();
	void clear ();
	void addFirst (T x);
	void addLast (T x);
	T getFirst ();
	T getLast ();
	T removeFirst ();
	T removeLast ();
	boolean isEmpty ();
	boolean isFull ();
	void sort (Comparator<T> c);
	ListIterator<T> listIterator ();
	ListIterator<T> listIterator (int start);
	
} // Lista.

Ecco la classe astratta:

import java.util.*;

public abstract class ListaAstratta<T extends Comparable<? super T>> implements Lista<T> {
	
	public int size () {
		int c = 0;
		for (@SuppressWarnings("unused") T x : this)
			c++;
		return c;
	} // size
	
	public void clear () {
		for (Iterator<T> it = this.iterator(); it.hasNext(); ) {
			it.next();
			it.remove();
		}		
	} // clear
	
	public void addLast (T x) {
		ListIterator<T> lit = this.listIterator();
		while (lit.hasNext())
			lit.next();
		lit.add(x);
	} // addLast
	
	public T getLast () {
		ListIterator<T> lit = this.listIterator();
		while (lit.hasNext())
			lit.next();
		return lit.previous();
	} // getLast
	
	public T removeLast () {
		ListIterator<T> lit = this.listIterator();
		while (lit.hasNext())
			lit.next();
		T x = lit.previous();
		lit.remove();
		return x;
	} // removeLast
	
	public boolean isEmpty () {
		return !iterator().hasNext();
	} // isEmpty
	
	public boolean isFull () {
		return false;
	} // isFull
	
	public boolean contains (T x) {
		for (T e : this) {
			if (e.equals(x)) return true;
			if (e.compareTo(x) > 0) return false;
		}
		return false;
	} // contains
	
	@Override
	public String toString () {
		StringBuffer sb = new StringBuffer(100);
		sb.append ('[');
		Iterator<T> it = this.iterator();
		while (it.hasNext()) {
			sb.append (it.next());
			if (it.hasNext()) sb.append(", ");
		}
		sb.append(']');
		return sb.toString();
	} // toString
	
	@Override
	@SuppressWarnings("unchecked")
	public boolean equals (Object o) {
		if (!(o instanceof Lista)) return false;
		if (o == this) return true;
		Lista<T> s = (Lista<T>)o;
		if (s.size() != this.size()) return false;
		Iterator<T> it1 = this.iterator();
		Iterator<T> it2 = s.iterator();
		while (it1.hasNext()) {
			T e1 = it1.next();
			T e2 = it2.next();
			if (!e1.equals(e2)) return false;
		}
		return true;
	} // equals
	
	@Override
	public int hashCode () {
		final int MOLT = 43; 
		int h = 0;
		for (T e: this)
			h = h * MOLT + e.hashCode();
		return h;	
	} // hashCode
	
} // ListaAstratta.

Qui non ho avuto molti problemi, un pò dubbioso su lastRemove che non ho avuto modo di provare per il fatto della remove sulla classe concreta. Ecco infine la classe concreta:

import java.util.*;

public class ListaConcatenata<T extends Comparable<? super T>> extends ListaAstratta<T> {

	private static class Nodo<E> {
		E info;
		Nodo<E> next;
		Nodo<E> prev;
	} // Nodo
	
	private Nodo<T> head;
	private Nodo<T> tail;
	
	public ListaConcatenata () {
		head = null;
		tail = null;
	} // Costruttore
	
	public void addFirst (T x) {
		Nodo<T> nuovoNodo = new Nodo<T>();
		nuovoNodo.info = x;
		if (isEmpty())
			tail = nuovoNodo;
		else {
			head.prev = nuovoNodo;
			nuovoNodo.next = head;
		}
		head = nuovoNodo;
	} // addFirst
	
	public void addLast (T x) {
		Nodo<T> nuovoNodo = new Nodo<T>();
		nuovoNodo.info = x;
		if (isEmpty())
			head = nuovoNodo;
		else {
			tail.next = nuovoNodo;
			nuovoNodo.prev = tail;
		}
		tail = nuovoNodo;
	} // addLast
	
	public T getFirst () {
		if (head == null)
			throw new NoSuchElementException("Lista vuota!");
		return head.info;
	} // getFirst
	
	public T getLast () {
		if (tail == null)
			throw new NoSuchElementException("Lista vuota!");
		return tail.info;
	} // getLast
	
	public T removeFirst () {
		if (head == null)
			throw new NoSuchElementException("Lista vuota!");
		T x = head.info;
		if (head.next == null)
			tail = null;
		else
			head.next.prev = null;
		head = head.next;
		return x;	
	} // removeFirst
	
	public T removeLast () {
		if (tail == null)
			throw new NoSuchElementException("Lista vuota!");
		T x = tail.info;
		if (tail.prev == null)
			head = null;
		else
			tail.prev.next = null;
		tail = tail.prev;
		return x;
	} // removeLast
	
	public void sort (Comparator<T> c) {
	} // sort
	
	public Iterator<T> iterator () {
		return new Iteratore();
	} // iterator
	
	public ListIterator<T> listIterator () {
		return new IteratoreDiLista();
	} // listIterator
	
	public ListIterator<T> listIterator (int start) {
		return new IteratoreDiLista(start);
	} // listIterator
	
	// --------------
	// Inner Classes.
	// --------------
	
	private class Iteratore implements Iterator<T> {
		
		private Nodo<T> current;
		private Nodo<T> precedent;
		
		public Iteratore () {
			current = null;
			precedent = null;
		} // Costruttore
		
		public boolean hasNext () {
			if (current == null)
				return head != null;
			else
				return current.next != null;		
		} // hasNext
		
		public T next () {
			if (!hasNext())
				throw new NoSuchElementException();
			precedent = current; 
			if (current == null)
				current = head;
			else
				current = current.next;
			return current.info;
		} // next
		
		public void remove () {
			if (precedent == current)
				throw new IllegalStateException();
			if (current == head) 
				removeFirst();
			else if (current == tail)
				removeLast();
			else 
				precedent.next = current.next;
			current = precedent;	
		} // remove
		
	} // Iteratore.
	
	public class IteratoreDiLista implements ListIterator<T>  {
		
		private Nodo<T> current;
		private Nodo<T> precedent;
		private Nodo<T> successive;
		
		public IteratoreDiLista () {
			current = null;
			precedent = null;
			successive = null;
		} // 1° Costruttore
		
		public IteratoreDiLista (int start) {
			if (start > size())
				throw new IllegalArgumentException();
			int c = 0;
			while (hasNext() && c < start) {
				current = current.next;
				c++;
			}
			precedent = null;
			successive = null;
		} // 2° Costruttore (con indice di partenza)
		
		public boolean hasNext () {
			if (current == null)
				return head != null;
			else
				return current.next != null;		
		} // hasNext.
		
		public T next () {
			if (!hasNext())
				throw new NoSuchElementException();
			precedent = current; 
			if (current == null)
				current = head;
			else
				current = current.next;
			return current.info;
		} // next
		
		public boolean hasPrevious () {
			return current.prev != null;
		} // hasPrevious
		
		public T previous () {
			if (!hasPrevious())
				throw new NoSuchElementException();
			successive = current; 
			current = current.prev;
			return current.info;
		} // previous
		
		public void add (T x) {
			if (current == null) {
				addFirst(x);
				current = head;
			} else {
				Nodo<T> nuovoNodo = new Nodo<T>();
				nuovoNodo.info = x;
				nuovoNodo.next = current.next;
				current.next = nuovoNodo;
				nuovoNodo.prev = current;
			}
		} // add
		
		public void remove () {
			if (precedent == current || successive == current)
				throw new IllegalStateException()
			if (current == head) 
				removeFirst();
			else if (current == tail)
				removeLast ();
                        // Qui mi sono bloccato.
		} // remove
		
		public void set (T x) {
			if (current == null)
				throw new NoSuchElementException();
			current.info = x;
		} // set
		
                // Il prof. ha detto di non implementare i metodi di listIterator
                // che abbiano a che fare con gli indici.

		public int nextIndex () {
			throw new UnsupportedOperationException ();
		} // nextIndex
		
		public int previousIndex () {
			throw new UnsupportedOperationException ();
		} // previousIndex
		
	} // IteratoreDiLista

} // ListaConcatenata

Poi ho fatto un main di prova e questi sono i risultati:

Creazione di una lista...
/////////////////////////
Aggiunta dell' elemento 1 in testa della lista.
Aggiunta dell' elemento 2 in coda della lista.
Aggiunta dell' elemento 3 in testa della lista.
Aggiunta dell' elemento 4 in coda della lista.
Aggiunta dell' elemento 5 in testa della lista.
Aggiunta dell' elemento 6 in coda della lista.
Lista creata: [5, 3, 1, 2, 4, 6] size: 6
Elemento rimosso in testa: 5
Lista corrente: [3, 1, 2, 4, 6] size: 5
Elemento rimosso in coda: 6
Lista corrente: [3, 1, 2, 4] size: 4
Elemento corrente in testa: 3
Elemento corrente in coda: 4 // OK

Creazione dell'iterator... 
///////////////////////////
Lista corrente: [3, 1, 2, 4] size: 4
Verifica sul successivo: true
Elemento successivo: 3
Verifica sul successivo: true
Elemento successivo: 1
Rimozione elemento corrente.
Lista corrente: [3, 2, 4] size: 3
Verifica sul successivo: true
Elemento successivo: 2
Rimozione elemento corrente.
Lista corrente: [3, 4] size: 2 //OK

Creazione del listIterator...
/////////////////////////////
Lista corrente: [3, 4] size: 2
Verifica sul successivo: true
Elemento successivo: 3
Verifica sul successivo: true
Elemento successivo: 4
Aggiunta dell'elemento 7 in lista.
Lista corrente: [3, 4, 7] size: 3
Aggiunta dell'elemento 8 in lista.
Lista corrente: [3, 4, 8, 7] size: 4
Aggiunta dell'elemento 9 in lista.
Lista corrente: [3, 4, 9, 8, 7] size: 5
Aggiunta dell'elemento 10 in lista.
Lista corrente: [3, 4, 10, 9, 8, 7] size: 6
Verifica sul successivo: true
Elemento successivo: 10
Verifica sul successivo: true
Elemento successivo: 9
Verifica sul successivo: true
Elemento successivo: 8

// Qui si presentano i problemi...

Verifica sul precedente: true
Elemento precedente: 4
Verifica sul precedente: true
Elemento precedente: 2
Verifica sul precedente: true
Elemento precedente: 1
Verifica sul precedente: true
Elemento precedente: 3

Cioè, col previous mi itera la lista in maniera giusta, ma itera la lista allo stato prima che creassi il listIterator, non capisco... chiedo consigli, ringrazio anticipatamente chi mi aiuterà

[R0ckY909]

Ultima cosa, piazzo il main...

import java.util.*;

public class ListaMain {
		
	// -----
	// Main.		
	// -----
		
	public static void main (String [] args) {
		System.out.println ("Creazione di una lista...");
		System.out.println ("/////////////////////////");
		Lista<Integer> lista = new ListaConcatenata<Integer> ();
		System.out.println ("Aggiunta dell' elemento 1 in testa della lista.");
		lista.addFirst(1);
		System.out.println ("Aggiunta dell' elemento 2 in coda della lista.");
		lista.addLast(2);
		System.out.println ("Aggiunta dell' elemento 3 in testa della lista.");
		lista.addFirst(3);
		System.out.println ("Aggiunta dell' elemento 4 in coda della lista.");
		lista.addLast(4);
		System.out.println ("Aggiunta dell' elemento 5 in testa della lista.");
		lista.addFirst(5);
		System.out.println ("Aggiunta dell' elemento 6 in coda della lista.");
		lista.addLast(6);
		System.out.print("Lista creata: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println("Elemento rimosso in testa: "+lista.removeFirst());
		System.out.print("Lista corrente: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println("Elemento rimosso in coda: "+lista.removeLast());
		System.out.print("Lista corrente: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println("Elemento corrente in testa: "+lista.getFirst());
		System.out.println("Elemento corrente in coda: "+lista.getLast());
		System.out.println ();
		
		System.out.println("Creazione dell'iterator... ");
		System.out.println("///////////////////////////");
		Iterator<Integer> it = lista.iterator();
		System.out.print("Lista corrente: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println("Verifica sul successivo: "+it.hasNext());
		System.out.println("Elemento successivo: "+it.next());
		System.out.println("Verifica sul successivo: "+it.hasNext());
		System.out.println("Elemento successivo: "+it.next());
		System.out.println("Rimozione elemento corrente.");
		it.remove();
		System.out.print("Lista corrente: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println("Verifica sul successivo: "+it.hasNext());
		System.out.println("Elemento successivo: "+it.next());
		System.out.println("Rimozione elemento corrente.");
		it.remove();
		System.out.print("Lista corrente: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println ();
		
		System.out.println("Creazione del listIterator...");
		System.out.println("/////////////////////////////");
		ListIterator<Integer> lit = lista.listIterator();
		System.out.print("Lista corrente: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println("Verifica sul successivo: "+lit.hasNext());
		System.out.println("Elemento successivo: "+lit.next());
		System.out.println("Verifica sul successivo: "+lit.hasNext());
		System.out.println("Elemento successivo: "+lit.next());
		System.out.println("Aggiunta dell'elemento 7 in lista.");
		lit.add(7);
		System.out.print("Lista corrente: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println("Aggiunta dell'elemento 8 in lista.");
		lit.add(8);
		System.out.print("Lista corrente: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println("Aggiunta dell'elemento 9 in lista.");
		lit.add(9);
		System.out.print("Lista corrente: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println("Aggiunta dell'elemento 10 in lista.");
		lit.add(10);
		System.out.print("Lista corrente: "+lista);
		System.out.println(" size: "+lista.size());
		System.out.println("Verifica sul successivo: "+lit.hasNext());
		System.out.println("Elemento successivo: "+lit.next());
		System.out.println("Verifica sul successivo: "+lit.hasNext());
		System.out.println("Elemento successivo: "+lit.next());
		System.out.println("Verifica sul successivo: "+lit.hasNext());
		System.out.println("Elemento successivo: "+lit.next());

		// Qui si presentano i problemi...

		System.out.println("Verifica sul precedente: "+lit.hasPrevious());
		System.out.println("Elemento precedente: "+lit.previous());
		System.out.println("Verifica sul precedente: "+lit.hasPrevious());
		System.out.println("Elemento precedente: "+lit.previous());
		System.out.println("Verifica sul precedente: "+lit.hasPrevious());
		System.out.println("Elemento precedente: "+lit.previous());
		System.out.println("Verifica sul precedente: "+lit.hasPrevious());
		System.out.println("Elemento precedente: "+lit.previous()); 
		} // Main
	} // ListaMain