Liste

Conceptul de lista

Lista este o colectie, ale carei elemente pot fi parcurse secvential, intr-o ordine determinata. Exista, deci un prim element, un ultim element si o modalitate de a trece de la un element al listei la cel urmator.

La nivel conceptual, se poate considera ca elementele unei liste sunt situate pe o singura linie, la fel cu cele ale unui tablou unidimensional, iar ordinea naturala de parcurgere este cea in care elementele sunt situate in lista. Deosebirea fata de tablou consta in aceea ca, in timp ce numarul de elemente ale tabloului se fixeaza la crearea acestuia si nu mai poate fi modificat ulterior, numarul de elemente dintr-o lista se poate modifica prin adaugari si eliminari. Tocmai din aceasta cauza spunem ca lista este o colectie si nu un tablou.

Adaugarea de elemente la o lista se poate face atat la inceputul sau la sfarsitul acesteia, cat si prin inserarea de noi elemente intre cele existente. Eliminarea de elemente se poate face in orice loc al listei.

Elementele unei liste pot fi indexate, la fel ca la un tablou unidimensional, indicele specificand pozitia elementului relativ la inceputul listei. Remarcam insa ca, daca se insereaza sau se elimina elemente, se modifica indicii tuturor elementelor situate in lista in urma lor.
 
Exemplu
Fie lista
A
B
C
D
Indicii celor patru elemente din lista sunt, respectiv, 0, 1, 2, 3. Prin inserarea elementului X in fata elementului C, numarul de elemente din lista creste, iar indicii elementelor C si D situate dupa locul inserarii creste cu o unitate:
A
B
X
C
D

Structura de lista se foloseste foarte frecvent in informatica. Iata numai cateva exemple din domeniul universitar: lista facultatilor unei universitati, lista catedrelor unei facultati, lista studentilor dintr-o grupa de studii, lista candidatilor la un concurs, lista disciplinelor predate la o anumita specializare, lista salilor de curs ale unei facultati etc.

In interfata grafica Java se folosesc, de asemenea, numeroase clase ale caror instante sunt liste sau contin liste. Iata cateva exemple: java.awt.List, java.awt.Choice, java.awt.Menu, java.awt.PopupMenu, javax.swing.JList, javax.swing.JComboBox, javax.swing.ButtonGroup, javax.swing.JMenu, javax.swing.JPopupMenu.
 

Interfetele List si ListIterator

Interfata java.util.List este derivata din interfata java.utilCollection si ofera o specificatie a listei ca tip abstract de date cu urmatoarele caracteristici:
   - elementele listei sunt obiecte;
   - elementele listei sunt indexate, primul element avand indicele 0;
   - lista poate fi parcursa in ambele sensuri: atat de la primul element catre ultimul, cat si invers;
   - accesul la elementele listei se poate face atat prin intermediul indicelui, cat si al iteratorului.
 
ATENTIE: nu trebuie confundata interfata java.util.List cu clasa java.awt.List. Este recomandabil ca acestea sa nu fie folosite in acelasi fisier sursa. Daca, totusi, aceasta situatie nu poate fi evitata, trebuie ca la declararea si variabilelor si crearea instantelor clasei java.awt.List sa se precizeze carui pachet apartine clasa.

Remarcam, cu aceasta ocazie, ca clasele de liste din pachetele java.awt si javax.swing nu implementeaza interfata java.util.List. In consecinta, daca clasele prin care se realizeaza in program interfata grafica sunt diferite de cele in care se utilizeaza alte structuri de date (de exemplu clasele de liste din pachetul java.util), nu se vor produce nici o data confuzii.

Pentru a se putea parcurge lista in ambele sensuri, a fost introdusa interfata java.util.ListIterator, care este derivata din interfata java.util.Iterator. Spre deosebire de Iterator, care permite parcurgerea secventiala a unei colectii numai intr-un singur sens, un ListIterator permite parcurgerea listei in ambele sensuri.
 
Interfata java.util.List mosteneste toate metodele interfetei java.util.Collection din care este derivata. In plus, sunt specificate urmatoarele metode specifice lucrului cu liste:
   public void add(int index, Object element) - insereaza un element in lista in pozitia data prin index;
   public boolean addAll(int index, Collection c) - insereaza in lista toate elementele colectiei c, incepand de la pozitia index;
   public Object get(int index) - intoarce o referinta la elementul de lista de pe pozitia index;
   public Object set(int index, Object element) - inlocuieste elementul de lista de pe pozitia index prin cel primit ca argument;
   public Object remove(int index) - elimina din lista elementul de pe pozitia index;
   public int indexOf(Object o) - intoarce indicele primului element din lista identic cu argumentul o;
   public int lastIndexOf(Object o) - intoarce indicele ultimului element din lista identic cu argumentul o;
   public ListIterator listIterator() - intoarce un iterator pozitionat pe primul element din aceasta lista;
   public ListIterator listIterator(int index) - intoarce un iterator pozitionat pe elementul cu indicele index din aceasta lista;
   public List subList(int fromIndex,int toIndex) - intoarce o sublista care contine elementele din aceasta lista cuprinse intre indicii fromIndex (inclusiv) si toIndex (exclusiv).

Interfata java.util.ListIterator  este derivata din interfata java.util.Iterator si mosteneste toate metodele acesteia. In plus, ea contine urmatoarele metode:

a/ operatii obligatorii
   public boolean hasPrevious() - intoarce true daca exista un element care il precede pe cel curent;
   public Object previous() - pozitioneaza iteratorul pe elementul precedent din lista si intoarce o referinta catre elementul respectiv. Daca nu exista element precedent, se genereaza exceptia java.util.NoSuchElementException;
   public int nextIndex() - intoarce indicele elementului urmator din lista, sau -1 daca un astfel de element nu exista;
   public int previousIndex() - intoarce indicele elementului precedent din lista, sau -1 daca un astfel de element nu exista;

b/ operatii optionale
   public void set(Object o) - se inlocuieste ultimul element al listei intors de metoda next()  sau previous() prin obiectul o primit ca argument; daca nici una din aceste metode nu a fost invocata, se genereaza o java.lang.IllegalStateException;
   public void add(Object o) - se insereaza in lista elementul o, primit ca argument, imediat in fata urmatorului element care ar fi fost intors de metoda next(), daca un astfel de element exista, sau la sfarsitul listei in caz contrar; daca lista nu contine nici un element, elementul nou adaugat devine singurul element din lista.
    Amintim ca se mosteneste de la interfata iterator si metoda remove(), care elimina din lista elementul curent. Daca una din operatiile optionale nu este implementata, se genereaza o java.lang.UnsupportedOperationException.

Remarcam ca metodele add, remove si set exista atat in interfata List, cat si in interfata ListIterator. Cele din interfata List se vor folosi numai daca listei respective nu i s-a asociat un iterator. Daca un astfel de iterator a fost generat, operatiile mentionate se vor efectua numai folosind metodele acestuia. 

Implementarea listei folosind un tablou

S-a aratat deja ca principala deosebire intre lista si tabloul unidimensional este ca lista (ca orice colectie) contine un numar de elemente variabil, in timp ce la tablou numarul de elemente se fixeaza la crearea acestuia. Totusi, daca se cunoaste lungimea maxima a listei, ea poate fi implementata sub forma de tablou, daca se admite ca numai o anumita zona din tablou este ocupata efectiv de elementele listei. In acest caz, lungimea tabloului va fi numita capacitatea listei (numarul maxim de elemente pe care le poate contine lista), in timp ce numarul de elemente efectiv existente in lista la un moment dat se va numi lungimea listei.

Sa consideram, de exemplu, ca folosim pentru lista urmatorul tablou cu 10 de elemente:
                   
La crearea listei, acest tablou este vid, deci capacitatea este 10, iar lungimea este 0. Dupa ce s-au adaugat pe rand la lista elementele A, B, C, D tabloul se prezinta astfel:
A
B
C
D
           
deci capacitatea este tot 10, dar lungimea este 4. Daca inseram un element X pe pozitia de indice 1, elementele situate pe aceasta pozitie si dupa ea se vor deplasa spre dreapta, obtinandu-se situatia urmatoare:
A
X
B
C
D
         
Acum lungimea listei este 5, iar capacitatea a ramas neschimbata. Daca eliminam din lista elementul C, se obtine situatia urmatoare:
A
X
B
D
           
Deci elementele situate dupa cel eliminat s-au deplasat spre stanga cu o unitate.

Analizand pentru lista implementata ca tablou complexitatea algoritmilor de inserare a unui element intr-o lista, eliminare a unui element din lista si de cautare a unui element, constatam ca in toate aceste cazuri numarul de operatii elementare creste proportional cu lungimea listei. In consecinta complexitatea acestor operatii este O(n). In schimb, pentru astfel de liste, accesul la oricare element al listei pentru care se cunoaste indicele are complexitatea constanta O(1), la fel ca pentru tablouri.
 
Exemplu: o lista de numere intregi implementata ca tablou

In fisierul ListaTI.java sunt declarate clasele ListaTI si TestListaTI. Clasa ListaTI are ca instante liste de numere intregi implementate ca tablouri. Cealalta clasa contine numai un program de testare.

Clasa ListaTI nu respecta interfata java.util.List, deoarece elementele ei nu sunt obiecte, ci valori primitive de tip int. Rolul ei este pur didactic, pentru a arata cum poate fi implementata o lista folosind ca suport un tablou.

Clasa ListaTI are doua campuri private: campul tab contine referinta la tabloul de elemente, iar campul lungime contine numarul de elemente existente efectiv in lista. In limbajul Java nu este necesar sa rezervam un camp special pentru capacitatea listei, deoarece aceasta este chiar lungimea tabloului tab, adica tab.length.

Constructorul listei primeste ca argument capacitatea acesteia si aloca in memorie un tablou tab cu numar de elemente corespunzator, dupa care pune campul lungime la valoarea 0;

Clasa contine metode pentru principalele operatii asupra listei: adaugare de elemente, inserare, eliminare, inlocuire, cautare. A fost, de asemenea, redefinita metoda toString din clasa Object, astfel incat lista sa poata fi convertita intr-un sir de caractere afisabil. Algoritmii folositi in aceste operatii pot fi usor urmariti citind corpurile metodelor respective. 

Dupa compilarea fisierului, se poate da comanda
   java TestListaTI
pentru a urmari rezultatul testarii.

Clasa AbstractList

Clasa abstracta java.util.AbstractList are rolul de a oferi un prototip pentru elaborarea unor clase de liste si este derivata din clasa java.util.AbstractCollection.

Clasa AbstractList mosteneste toate metodele clasei AbstractCollection si contine, de asemenea, metodele interfetei List. Pentru a crea o noua clasa de liste, programatorul poate extinde clasa AbstractList, definind numai metodele abstracte ale acesteia si redefinind, eventual, unele din metodele concrete in functie de obiectivele urmarite. In aceasta clasa, lista este implementata printr-un tablou de obiecte.
 
Pentru a obtine o lista nemodificabila este suficient ca in clasa derivata sa se defineasca metodele 
   public abstract Object get(int index) - care intoarce o referinta la elementul de pe pozitia index;
   public abstract int size() - mostenita de la clasa AbstractCollection si care intoarce numarul de elemente din lista (lungimea listei).

Pentru a obtine o lista modificabila, este necesar, de asemenea sa se redefineasca metodele care corespund operatiilor optionale din interfetele List si Collection.

Clasele ArrayList si Vector

In pachetul java.util exista doua clase pentru liste implementate prin tablouri: clasele java.util.ArrayList si java.utilVector. Ambele clase au urmatoarele caracteristici:
    - Extind clasa AbstractList.
    - Elementele listei sunt obiecte, adica instante ale clasei Object sau ale subclaselor acesteia. Intrucat in Java clasa Object este radacina ierarhiei tuturor claselor, inseamna ca elementele listei pot apartine oricarei clase.
    - Desi lista este implementata folosind un tablou, capacitatea listei se mareste automat atunci cand lungimea tabloului creste peste capacitate. Aceasta se realizeaza in modul urmator: daca lungimea este egala cu capacitatea si se adauga un nou element, se aloca automat in memorie un nou tablou de capacitate superioara, iar elementele din vechiul tablou se muta in cel nou. Vechiul tablou, lasat fara referinta, va fi eliminat din memorie de catre colectorul de reziduuri.

Principala deosebire intre clasele ArrayList si vector consta in faptul ca metodele clasei Vector prin care se modifica lista sunt sincronizate, in timp ce cele ale clasei ArrayList nu sunt. Daca mai multe fire de executie au acces la aceeasi instanta a clasei ArrayList, ea trebuie sincronizata folosind metoda statica Collections.synchronizedList.
 
Clasa ArrayList are trei constructori:
   public ArrayList(int initialCapacity) - construieste o lista vida, de capacitate initiala data ca argument;
   public ArrayList() - construieste o lista vida de capacitate initiala standard
   public ArrayList(Collection c) - construieste o lista care contine toate elementele colectiei c.

Clasa contine toate metodele interfetelor Collection si List, cu precizarea ca sunt redefinite si cele care corespund unor operatii optionale. In plus, ofera urmatoarele metode specifice listei implementate ca tablou:
   public void trimToSize() - reduce capacitatea listei la cea corespunzatoare numarului de elemente existente efectiv (pentru economie de memorie);
   public void ensureCapacity(int minCapacity) - mareste capacitatea listei la cea primita ca argument; daca in realitate capacitatea este deja mai mare, ea ramane neschimbata;
   protected void removeRange(int fromIndex, int toIndex) - elimina din lista elementele incepand de la indicele fromIndex pana la cel care il precede pe toIndex;
   public Object clone() - intoarce o clona a listei (cu precizarea ca se copiaza tabloul de referinte, dar nu si elementele propriu-zise, adica obiectele indicate de aceste referinte).
 
Exemplu
In fisierul TestArrayList.java este dat un exemplu de aplicatie in care se testeaza clasa ArrayList. Ca elemente ale listei se folosesc obiecte din clasa String.



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