La nivel conceptual, se poate considera că lista este o structură liniară, adică elementele unei liste sunt situate pe o singură linie, la fel cu cele ale unui tablou unidimensional, iar ordinea naturală de parcurgere este cea în care elementele sunt situate în listă. Deosebirea față de tablou constă în aceea că, în timp ce numarul de elemente ale tabloului se fixează la crearea acestuia și nu mai poate fi modificat ulterior, numărul de elemente dintr-o listă se poate modifica prin adăugări și eliminări. Tocmai din această cauză considerăm că lista este o colecție și nu un tablou.
Adăugarea de elemente la o listă se poate face atât la începutul sau la sfârșitul acesteia, cât și prin înserarea de noi elemente între cele existente. Eliminarea de elemente se poate face în orice loc al listei.
Elementele unei liste pot fi indexate, la fel ca la un tablou
unidimensional, indicele specificând poziția elementului relativ la
începutul listei. Remarcăm însă că, dacă se înserează sau se elimină
elemente, se modifică indicii tuturor elementelor situate în listă în
urma lor.
Exemplu Fie lista
|
Structura de listă se folosește foarte frecvent în informatică. Iată numai câteva exemple din domeniul universitar: lista facultăților unei universități, lista catedrelor unei facultăți, lista studenților dintr-o grupă de studii, lista candidaților la un concurs, lista disciplinelor predate la o anumită specializare, lista sălilor de curs ale unei facultăți etc.
În interfața grafică Java se folosesc, de asemenea, numeroase clase
ale căror instanțe sunt liste sau conțin liste. Iată câteva 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.
ATENTIE: nu trebuie confundată interfața java.util.List cu
clasa java.awt.List. Este recomandabil ca acestea sa nu fie folosite în
acelasi fisier sursă. Dacă, totuși, această situație nu poate fi
evitată, trebuie ca la declararea variabilelor și crearea instanțelor
clasei java.awt.List să se precizeze cărui pachet aparține clasa.
Remarcăm, cu aceasta ocazie, că clasele de liste din pachetele java.awt și javax.swing nu implementează interfața java.util.List. În consecință, dacă clasele prin care se realizează în program interfața grafică sunt diferite de cele în care se utilizează alte structuri de date (de exemplu clasele de liste din pachetul java.util), nu se vor produce nici o dată confuzii. |
Pentru a se putea parcurge lista în ambele sensuri, a fost introdusă
interfața java.util.ListIterator, care extinde interfața java.util.Iterator.
Spre deosebire de Iterator, care permite parcurgerea secvențială a unei
colecții numai într-un singur sens, un ListIterator permite parcurgerea
listei în ambele sensuri.
Interfața java.util.List moștenește toate metodele
interfeței java.util.Collection
din care este derivată. În plus, sunt specificate următoarele metode
specifice lucrului cu liste: public void add(int index, Object element) - înserează un element în listă în poziția dată prin index; public boolean addAll(int index, Collection c) - înserează în listă toate elementele colecției c, începând de la poziția index; public Object get(int index) - întoarce o referință la elementul de listă de pe poziția index; public Object set(int index, Object element) - înlocuiește elementul de listă de pe poziția index prin cel primit ca argument; public Object remove(int index) - elimină din listă elementul de pe poziția index; public int indexOf(Object o) - întoarce indicele primului element din listă identic cu argumentul o; public int lastIndexOf(Object o) - întoarce indicele ultimului element din listă identic cu argumentul o; public ListIterator listIterator() - întoarce un iterator poziționat pe primul element din această listă; public ListIterator listIterator(int index) - întoarce un iterator poziționat pe elementul cu indicele index din această listă; public List subList(int fromIndex,int toIndex) - întoarce o sublistă care conține elementele din această listă cuprinse între indicii fromIndex (inclusiv) și toIndex (exclusiv). Interfața java.util.ListIterator extinde interfața java.util.Iterator și mostenește toate metodele acesteia. În plus, ea conține următoarele metode: a/ operații obligatorii b/ operații opționale Remarcăm că metodele add, remove și set există atât în interfața List, cât și în interfața ListIterator. Cele din interfața List se vor folosi numai dacă listei respective nu i s-a asociat un iterator. Dacă un astfel de iterator a fost generat, operațiile menționate se vor efectua numai folosind metodele acestuia. |
Să considerăm, de exemplu, că folosim pentru listă urmatorul tablou cu 10 de elemente:
|
|
|
|
|
|
|
|
|
|
|
|
|
Analizând pentru lista implementată ca tablou complexitatea
algoritmilor de înserare a unui element într-o listă, eliminare
a unui element din listă și de căutare a unui element, constatăm că în
toate aceste cazuri numărul de operații elementare crește direct
proporțional cu lungimea listei. În consecință complexitatea acestor
operații este O(n). În schimb, pentru astfel de liste,
accesul la oricare element al listei pentru care se cunoaste indicele
are complexitatea constantă O(1), la fel ca pentru
tablouri.
Exemplu: o listă de numere întregi implementată
ca tablou
În fișierul ListaTI.java sunt declarate clasele ListaTI și TestListaTI. Clasa ListaTI are ca instanțe liste de numere întregi implementate ca tablouri. Cealaltă clasă conține numai un program de testare. Clasa ListaTI nu respectă interfața java.util.List, deoarece elementele ei nu sunt obiecte, ci valori primitive de tip int. Rolul ei este pur didactic, pentru a arăta cum poate fi implementată o listă folosind ca suport un tablou. Clasa ListaTI are două câmpuri private: câmpul tab conține referința la tabloul de elemente, iar câmpul lungime conține numărul de elemente existente efectiv în listă. În limbajul Java nu este necesar să rezervăm un câmp special pentru capacitatea listei, deoarece aceasta este chiar lungimea tabloului tab, adica tab.length. Constructorul listei primește ca argument capacitatea acesteia și alocă în memorie un tablou tab cu număr de elemente corespunzător, după care pune câmpul lungime la valoarea 0; Clasa conține metode pentru principalele operații asupra listei: adaugare de elemente, înserare, eliminare, înlocuire, căutare. A fost, de asemenea, redefinită metoda toString din clasa Object, astfel încât lista să poată fi convertită într-un șir de caractere afișabil. Algoritmii folosiți în aceste operații pot fi ușor urmăriți citind corpurile metodelor respective. După compilarea fișierului, se poate da comanda |
Clasa AbstractList mostenește toate metodele clasei AbstractCollection și
contine, de asemenea, metodele interfeței List. Pentru a crea o nouă
clasă de liste, programatorul poate extinde clasa AbstractList, definind
numai metodele abstracte ale acesteia și redefinind, eventual, unele din
metodele concrete în funcție de obiectivele urmărite. În această clasă,
lista este implementată printr-un tablou de obiecte.
Pentru a obține o listă nemodificabilă este suficient ca în
clasa derivată din AbstractList să se definească metodele public abstract Object get(int index) - care întoarce o referință la elementul de pe poziția index; public abstract int size() - mostenită de la clasa AbstractCollection și care întoarce numărul de elemente din listă (lungimea listei). Pentru a obține o listă modificabilă, este necesar, de asemenea să se redefinească metodele care corespund operațiilor opționale din interfețele List și Collection. |
Principala deosebire dintre clasele ArrayList și Vector constă în
faptul că metodele clasei Vector prin care se modifică lista sunt
sincronizate, în timp ce cele ale clasei ArrayList nu sunt. Dacă mai
multe fire de execuție au acces la aceeași instanță a clasei ArrayList,
ea trebuie sincronizată folosind metoda statică Collections.synchronizedList(List
list), care întoarce o lista sincronizată cu aceleași elemente ca cea
primită ca argument.
Clasa ArrayList are trei constructori: public ArrayList(int initialCapacity) - construiește o listă vidă, de capacitate inițială dată ca argument; public ArrayList() - construiește o listă vidă de capacitate inițială standard public ArrayList(Collection c) - construiește o listă care conține toate elementele colecției c. Clasa conține toate metodele interfețelor Collection și List, cu precizarea că sunt redefinite și
cele care corespund unor operații opționale. În plus, oferă următoarele
metode specifice listei implementate ca tablou:
|