Nu este insa recomandabila folosirea listelor inlantuite in probleme care necesita acces aleator la elemente, deoarece astfel de operatii au complexitate liniara. Amintim ca, pentru accesul aleator la elemente, este preferabila folosirea claselor ArrayList sau Vector, in care listele sunt implementate prin tablouri.
Clasa are doi constructori:
public LinkedList() - construieste o lista dublu
inlantuita vida;
public LinkedList(Collection c) - construieste
o lista dublu inlantuita, care contine toate elementele din colectia c.
Clasa LinkedList contine toate metodele interfetelor Collections si
List. In plus, ea contine metode prin care se pot vizita, adauga sau elimina
elemente in capul sau coada listei, permitand folosirea acesteia ca stiva
sau coada. Aceste metode prezinta avantajul ca au complexitatea O(1).
Metodele prin care se pot face operatii in capul sau coada listei sunt
urmatoarele:
public Object getFirst() - intoarce o referinta la primul element al listei; public Object getLast() - intoarce o referinta la ultimul element al listei; public Object removeFirst() - elimina din lista primul element; public Object removeLast() - elimina din lista ultimul element; public void addFirst(Object o) - adauga un element in capul listei; public void addLast(Object o) - adauga un element in coada listei; Metodele de acces la elementele listei prin indici (Object get(int
index), Object remove(int index), void add(int index, Object element))
exista, intrucat clasa implementeaza interfata List, dar complexitatea
lor este in acest caz O(n). Este preferabil ca accesul la
elementele din interiorul listei sa se faca secvential, folosind un iterator
de lista, care se obtine prin una din metodele urmatoare:
|
Exemplu
In fisierul TestLista.java este un exemplu de aplicatie, in care se testeaza clasa LinkedList.java pentru realizarea unei liste ale carei elemente sunt siruri de caractere (obiecte din clasa String).
Iata si rezultatul executarii acestei aplicatii:
Se observa ca afisarea listei se face punandu-se intre paranteze drepte elementele acesteia separate prin virgule. Se poate urmari modul cum au fost executate diferite metode: adaugarea de elemente in capul si coada listei, inserarea de elemente, adaugarea tuturor elementelor unei colectii, cautarea unui element in lista, eliminarea dintr-o lista a tuturor elementelor existente intr-o colectie (in cazul de fata - in alta lista). Se demonstreaza, de asemenea, parcurgerea tuturor elementelor listei de la cap la coada folosind un iterator, iar apoi parcurgerea lor cu acelasi iterator in ordine inversa. Aplicatia poate fi extinsa, desigur, pentru a testa si alte metode ale clasei LinkedList sau ale interfetelor List si Collection. |
Exemplu
In fisierul LinkedStack.java este declarata clasa LinkedStack, ale carei instante sunt stive. In mod intentionat, pentru comparatie, denumirile metodelor au fost adoptate identice cu cele ale clasei java.util.Stack, in care stiva este implementata ca tablou. In acelasi fisier exista aplicatia TestLinkedStack, in care se testeaza clasa LinkedStack prin punerea in stiva a argumentelor din linia de comanda, care sunt apoi extrase din stiva si afisate in ordine inversa. |