Realizarea propriilor clase de liste înlănțuite

Dacă, din diferite motive, nu ne satisface clasa LinkedList, dar dorim sa respectăm totuși interfața List, putem creea propriile noastre clase de liste prin extinderea clasei AbstractSequentialList sau implementând direct interfața List.

Clasa AbstractSequentialList

Clasa abstractă java.util.AbstractSequentialList extinde clasa java.util.AbstractList pentru a permite crearea claselor de liste înlănțuite.

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țuite

Considerăm că dorim să creem o clasă de liste dublu înlănțuite cu structura din figura 7.


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



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați