Listă (structură de date)

O listă este o colecție de elemente de informație (noduri), legate între ele prin referințe, realizându-se, astfel, o stocare necontiguă a datelor în memorie. Lungimea unei liste este dată de numărul de noduri din listă.

Structura corespunzătoare de date trebuie să permită determinarea eficientă a primului sau ultimului nod din structură și care este predecesorul sau succesorul unui nod dat, dacă există.

Conceptul de listă

Lista este o colecție, ale cărei elemente pot fi parcurse secvențial, într-o ordine determinată. Există, deci, un prim element, un ultim element și o modalitate de a trece de la un element al listei la cel următor. 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 inceputul 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 A B C D Indicii celor patru elemente din listă sunt, respectiv, 0, 1, 2, 3. Prin înserarea elementului X in fața elementului C, numărul de elemente din listă crește, iar indicii elementelor C și D situate după locul înserării crește cu o unitate: A B X C D Structura de listă se folosește foarte frecvent in informatică. Iată numai câteva exemple din domeniul universitar: lista facultaț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.

Interfețele List și ListIterator

Interfața java.util.List extinde interfața java.utilCollection și oferă o specificație a listei ca tip abstract de date cu urmatoarele caracteristici:

  - elementele listei sunt obiecte; 
  - elementele listei sunt indexate, primul element având indicele 0; 
  - lista poate fi parcursă în ambele sensuri: atât de la primul element catre ultimul, cât și invers; 
  - accesul la elementele listei se poate face atât prin intermediul indicelui, cât și al iteratorului.

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

  public boolean hasPrevious() - întoarce true dacă există un element care îl precede pe cel curent; 
  public Object previous() - poziționează iteratorul pe elementul precedent din listă și întoarce o referință către elementul respectiv. Dacă nu există element precedent, se generează excepția java.util.NoSuchElementException; 
  public int nextIndex() - întoarce indicele elementului următor din listă, sau -1 dacă un astfel de element nu există; 
  public int previousIndex() - întoarce indicele elementului precedent din listă, sau -1 daca un astfel de element nu există;

b/ operații opționale

  public void set(Object o) - se înlocuiește ultimul element al listei întors de metoda next()  sau previous() prin obiectul o primit ca argument; dacă nici una din aceste metode nu a fost invocată, se genereaza o java.lang.IllegalStateException; 
  public void add(Object o) - se înserează in listă elementul o, primit ca argument, imediat în fața următorului element care ar fi fost întors de metoda next(), dacă un astfel de element există, sau la sfârșitul listei în caz contrar; dacă lista nu conține nici un element, elementul nou adăugat devine singurul element din listă. 
   Amintim că se mostenește de la interfața Iterator și metoda remove(), care elimină din listă elementul curent. Dacă una din operațiile opționale nu este implementată, se generează o java.lang.UnsupportedOperationException.

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. Daca un astfel de iterator a fost generat, operațiile menționate se vor efectua numai folosind metodele acestuia.

Implementarea listei folosind un tablou

S-a aratat deja că principala deosebire dintre listă și tabloul unidimensional este că lista (ca orice colecție) conține un număr de elemente variabil, în timp ce la tablou numărul de elemente se fixează la crearea acestuia. Totuși, dacă se cunoaște lungimea maximă a listei, ea poate fi implementată sub forma de tablou, dacă se admite că numai o anumita zonă din tablou este ocupată efectiv de elementele listei. În acest caz, lungimea tabloului va fi numită capacitatea listei (numărul maxim de elemente pe care le poate conține lista), în timp ce numărul de elemente efectiv existente în listă la un moment dat se va numi lungimea listei. Să considerăm, de exemplu, că folosim pentru listă 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 adăugat pe rând la listă elementele A, B, C, D tabloul se prezintă astfel:

A B C D deci capacitatea este tot 10, dar lungimea este 4. Dacă înserăm un element X pe poziția de indice 1, elementele situate pe aceasta poziție și după ea se vor deplasa spre dreapta, obținându-se situația următoare: A X B C D Acum lungimea listei este 5, iar capacitatea a rămas neschimbată. Dacă eliminăm din listă elementul C, se obține situația următoare: A X B D Deci elementele situate după cel eliminat s-au deplasat spre stânga cu o poziție.

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

  java TestListaTI

pentru a urmări rezultatul testării.

Legături externe

Lista: stiva si coada in C - aplicatii rezolvate Arhivat în 15 octombrie 2012, la Wayback Machine.