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
|
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.
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
b/ operatii optionale
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. |
Sa consideram, de exemplu, ca folosim pentru lista urmatorul tablou cu 10 de elemente:
|
|
|
|
|
|
|
|
|
|
|
|
|
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
|
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. |
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:
|