Strutture dati realizzate con array riempiti parzialmente e liste concatenate.
Si codifichino le classi ArrayVector.java e LinkedListVector.java per realizzare l'interfaccia MyList, usando un array riempito parzialmente nella prima, una lista concatenata nella seconda.
Si provino le classi realizzate con le seguenti classi di prova fornite dal docente: ArrayVectorTester.java e LinkedListVectorTester.java.
Si risponda, successivamente, alle seguenti domande:
1. Qual e' la complessita' temporale del metodo public void add(int index, Object obj) nelle due realizzazioni?
2. Qual e' la complessita' temporale del metodo public Object get(int index) nelle due realizzazioni?
3. Qual e' la complessita' temporale del metodo public int indexOf(Object obj) nelle due realizzazioni?
4. Perche' la lista concatenata risulta meno efficiente dell'array riempito parzialmente per la realizzazione di questo tipo di dati astratto?
Programmazione di LinkedListVector.java
Ci sono due alternative:
a. Programmare la classe lista concatenata, realizzata come a lezione, e usare nella classe LinkedListVector un esemplare di questa classe (LinkedList) per memorizzare i dati. Nella classe LinkedList codificata a lezione non si e' definito il metodo int size() e quindi si realizzi il conteggio degli elementi del contenitore nella classe LinkedListVector (ad esempio definendo e aggiornando una variabile int size, come sa fa solitamente).
b. Definire la classe nodo (ListNode a lezione) come classe interna della classe LinkedListVector e gestire internamente ai metodi della classe LinkedListVector la programmazione della lista concatenata.
La classe ListNode, nella forma piu' semplice, definisce variabili di esemplare senza specificatoredi accesso, rendendole visibili nella classe in cui ListNode e' contenuta. Non e' una violazione del principio dell'incapsulamento, perche', essendo ListNode una classe interna, non e' visibile al di fuori della classe in cui e' definita:
// Nodo della lista concatenata: classe interna
class ListNode
{
Object element; // visibile nella classe di cui ListNode e' classe interna
ListNode next; // visibile nella classe di cui ListNode e' classe interna
public ListNode(Object obj, ListNode n)
{
element = obj;
next = n;
}
public ListNode()
{
this(null, null);
}
}
Con la definizione riportata sopra della classe ListNode, il metodo public void add(Object obj) della classe LinkedListVector puo' essere codificato come segue, dove la variabile int size conta gli elementi contenuti nel vettore:
/**
aggiunge alla fine di questo Vettore l'elemento specificato
O(1)
@param obj nuovo elemento da aggiungere
*/
public void add(Object dato)
{
tail.next = new ListNode(dato, null);
tail = tail.next;
size++;
}
Rappresentazione
grafica dell'inserimento di un dato nella lista concatenata
LinkedListVector.java
Usare due nodi sentinella, senza dati, per marcare il primo node (head) e l'ultimo (tail).
La lista vuota sia costituita dai due nodi sentinella, come la seguente:
Provare i metodi della classe con la classe di prova DoublyLinkedListTester.java fornita dal docente.
