Nu este însă recomandabilă folosirea listelor înlănțuite în probleme care necesită acces aleator la elemente (pe baza indicelui elementului), deoarece astfel de operații au complexitate liniară O(n). Amintim că, pentru accesul aleator la elemente, este preferabilă folosirea claselor ArrayList sau Vector, în care listele sunt implementate prin tablouri.
Clasa are doi constructori:
public LinkedList() - construiește o listă dublu înlănțuită
vidă;
public LinkedList(Collection c) - construiește o listă dublu
înlănțuită, care conîine toate elementele din colecția c.
Clasa LinkedList conține toate metodele interfețelor Collections și
List. În plus, ea conține metode prin care se pot vizita, adăuga sau
elimina elemente din capul sau coada listei, permițând folosirea
acesteia ca stivă sau coadă. Aceste metode prezintă avantajul că au
complexitatea O(1).
Metodele prin care se pot face operații în capul sau coada
listei sunt următoarele: public Object getFirst() - întoarce o referință la primul element al listei; public Object getLast() - întoarce o referință la ultimul element al listei; public Object removeFirst() - elimină din listă primul element; public Object removeLast() - elimină din listă ultimul element; public void addFirst(Object o) - adaugă un element în capul listei; public void addLast(Object o) - adaugă un element în coada listei; Metodele de acces la elementele listei prin indici (Object
get(int index), Object remove(int index), void add(int index, Object
element)) există, întrucât clasa implementează interfața List, dar
complexitatea lor este în acest caz O(n). Este
preferabil ca accesul la elementele din interiorul listei să se facă
secvențial, folosind un iterator de listă, care se obține prin una din
metodele următoare: |
Exemplu În fișierul TestLista.java este dat un exemplu de aplicație, în care se testează clasa LinkedList pentru realizarea unei liste ale cărei elemente sunt șiruri de caractere (obiecte din clasa String).
Iată și rezultatul executării acestei aplicații:
Se observă că afișarea listei se face punându-se între paranteze drepte elementele acesteia separate prin virgule. Se poate urmări modul cum au fost executate diferite metode: adăugarea de elemente în capul și coada listei, înserarea de elemente, adăugarea tuturor elementelor unei colecții, căutarea unui element în listă, eliminarea dintr-o listă a tuturor elementelor existente într-o colecție (în cazul de față - în altă listă). Se ilustrează, de asemenea, parcurgerea tuturor elementelor listei de la cap la coadă folosind un iterator, iar apoi parcurgerea lor cu același iterator în ordine inversă. Aplicația poate fi extinsă, desigur, pentru a testa și alte metode ale clasei LinkedList sau ale interfețelor List și Collection. |
Exemplu In fișierul LinkedStack.java este declarată clasa LinkedStack, ale cărei instanțe sunt stive. În mod intenționat, pentru comparație, denumirile metodelor au fost adoptate identice cu cele ale clasei java.util.Stack, în care stiva este implementată ca tablou. În același fișier există aplicația TestLinkedStack, în care se testează clasa LinkedStack prin punerea în stivă a argumentelor din linia de comandă, care sunt apoi extrase din stivă și afișate în ordine inversă. |