In clasa AbstractSequentialList există toate metodele interfețelor
List și Collection (unele din ele definite în aceasta clasă, altele
moștenite de la clasa AbstractList). Singura metodă abstractă este
public abstract ListIterator listIterator(int index)
care întoarce un iterator al listei, care începe iterarea de la
elementul de indice index. Acest iterator trebuie creat de programator.
În acest scop, se creează o clasă (de preferință interioară), care
implementează interfața java.util.ListIterator, iar metoda listIterator
întoarce o instanță a acestei clase, poziționată pe elementul de indice index.
Celelalte metode ale clasei AbstractSequentialList se bazează pe
folosirea acestui iterator. Este totuși necesar să fie redefinita și
metoda public int size().
Iteratorul de listă conține atât metodele pentru trecerea de
la un nod la nodul următor sau la cel precedent (lista este considerată
dublu înlanțuită), cât și pentru a vizita, adăuga sau elimina un element
de pe poziția curentă a iteratorului. Toate aceste operații necesită,
evident, cunoașterea structurii listei și a nodului de listă, deci
trebuie sa conțină algoritmi de efectuare a operațiilor respective
corespunzători cu aceste structuri. În secțiunea următoare vom prezenta
un exemplu de creare a unei clase de liste.
Crearea unei clase de liste înlănțuiteConsiderăm că dorim să creem o clasă de liste dublu înlănțuite cu structura din figura 7.
Principala deosebire față de schema din figura 5 (sectiunea Liste dublu inlantuite) este că la extremități au fost introduse doua noduri suplimentare, numite sentinele (în figura sunt colorate cu roșu), care nu conțin elemente de listă, ci numai legături. Introducerea acestor sentinele prezintă avantajul că simplifică algoritmii operațiilor asupra nodurilor, deoarece acum toate nodurile care conțin elemente sunt în interiorul listei.Clasa ListaDI conține și trei câmpuri: referințe la sentinelele din capul și coada listei și lungimea listei (numărul de elemente din listă, deci numărul de noduri care conțin elemente, excluzând sentinelele). La construire, lista este vidă, deci conține numai nodurile sentinelă. Constructorul clasei ListaDI creează cele două noduri sentinelă și legăturile de la listă către acestea (cap, coada) și dintre ele (precedent, următor). Pentru realizarea acestei liste vom scrie o clasă, numită ListaDI (Lista Dublu Inlantuită), care extinde clasa AbstractSequentialList și care conține două clase interioare: Nod, care reprezintă nodurile listei, și Iter, care reprezintă iteratorii de listă. Clasa interioară Nod conține numai trei referințe: două dintre ele, numite urmator si precedent, sunt referințe la instanțe ale clasei nod. A treia, numită element, este referința la Object (la elementul de listă, care poate fi un obiect oarecare). Clasa interioară Iter implemententează interfața ListIterator. Unul din câmpuri, numit cursor, este o referință la nodul curent al listei. Un alt câmp, numit indice, contine indicele elementului curent. In clasă sunt definite toate metodele interfeței ListIterator, astfel încât operațiile corespunzătoare să se facă asupra listei cu structura din figura 7. La invocarea metodei next se deplasează cursorul pe nodul următor al listei și se întoarce elementul din acest nod. La invocarea metodei previous se deplasează cursorul pe nodul precedent al listei, dar se întoarce elementul din nodul pe care cursorul se afla înainte de deplasare. Clasa ListaDI este definită în fișierul ListaDI.java. Atragem atenția în special asupra modului în care au fost redefinite metodele add si remove din clasa Iter si metoda listIterator din clasa ListaDI. In același fișier se găsește și aplicația TestListaDI în care se testează clasa ListaDI. Se poate observa că functionează corect metodele testate ale interfețelor List și Collection. |