Realizarea propriilor clase de liste inlantuite

Daca, din diferite motive, nu ne satisface clasa LinkedList, dar dorim sa respectam totusi interfata List, putem creea propriile noastre clase de liste prin extinderea clasei AbstractSequentialList sau implementand direct interfata List.

Clasa AbstractSequentialList

Clasa abstracta java.util.AbstractSequentialList extinde clasa java.util.AbstractList pentru a permite crearea claselor de liste inlantuite.

In clasa AbstractSequentialList exista toate metodele interfetelor List si Collection (unele din ele definite in aceasta clasa, altele mostenite de la clasa AbstractList). Singura metoda abstracta este
   public abstract ListIterator listIterator(int index)
care intoarce un iterator al listei, care incepe iterarea de la elementul de indice index. Acest iterator trebuie creat de programator. In acest scop, se creeaza o clasa (de preferinta interioara), care implementeaza interfata java.util.ListIterator, iar metoda listIterator intoarce o instanta a acestei clase, pozitionata pe elementul de indice index. Celelalte metode ale clasei AbstractSequentialList se bazeaza pe folosirea acestui iterator.

Iteratorul de lista contine atat metodele pentru trecerea de la un nod la nodul urmator sau la cel precedent (lista este considerata dublu inlantuita), cat si pentru a vizita, adauga sau elimina un element de pe pozitia curenta a iteratorului. Toate aceste operatii necesita, evident, cunoasterea structurii listei si a nodului de lista, deci trebuie sa contina algoritmi de efectuare a operatiilor respective corespunzatori cu aceasta structura. In sectiunea urmatoare vom prezenta un exemplu de creare a unei clase de liste.
 

Crearea unei clase de liste inlantuite

Consideram ca dorim sa creem o clasa de liste dublu inlantuite cu structura din figura 7.


- Figura 7 -

Principala deosebire fata de schema din figura 5 (sectiunea Liste dublu inlantuite) este ca la extremitati au fost introduse doua noduri suplimentare, numite sentinele (in figura sunt colorate cu rosu), care nu contin elemente de lista, ci numai legaturi. Introducerea acestor sentinele prezinta avantajul ca simplifica algoritmii operatiilor asupra nodurilor, deoarece acum toate nodurile care contin elemente sunt in interiorul listei.Clasa ListaDI contine si trei campuri: referinte la sentinelele din capul si coada listei si lungimea listei (numarul de elemente din lista, deci numarul de noduri care contin elemente, excluzand sentinelele). 

La construire, lista este vida, deci contine numai nodurile sentinela. Constructorul clasei ListaDI creeaza cele doua noduri sentinela si legaturile de la lista catre acestea (cap, coada) si dintre ele (precedent, urmator). 

Pentru realizarea acestei liste vom scrie o clasa, numita ListaDI (Lista Dublu Inlantuita), care extinde clasa AbstractSequentialList si care contine doua clase interioare: Nod, care reprezinta nodurile listei, si Iter, care reprezinta iteratorii de lista.

Clasa interioara Nod contine numai trei referinte: doua din ele, numite urmator si precedent, sunt referinte la instante ale clasei nod. A treia, numita element, este referinta la Object (la elementul de lista, care poate fi un obiect oarecare).

Clasa interioara Iter implemententeaza interfata ListIterator. Unul din campuri, numit cursor, este o referinta la nodul curent al listei. Un alt camp, numit indice, contine indicele elementului curent. In clasa sunt definite toate metodele interfetei ListIterator, astfel incat operatiile corespunzatoare sa se faca asupra listei cu structura din figura 7. La invocarea metodei next se deplaseaza cursorul pe nodul urmator al listei si se intoarce elementul din acest nod. La invocarea metodei previous se deplaseaza cursorul pe nodul precedent al listei, dar se intoarce elementul din nodul pe care cursorul se afla inainte de deplasare.

Clasa ListaDI este definita in fisierul ListaDI.java. Atragem atentia in special asupra modului in care au fost redefinite metodele add si remove din clasa Iter si metoda listIterator din clasa ListaDI.

In acelasi fisier se gaseste si aplicatia TestListaDI in care se testeaza aceasta clasa. Se poate observa ca functioneaza corect metodele testate ale interfetelor List si Collection.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati