Realizarea listelor înlănțuite folosind pachetul java.util

În pachetul java.util există clasa LinkedList, ale cărei instanțe sunt liste dublu înlănțuite. În majoritatea situațiilor este suficientă folosirea acestei clase. Dacă se dorește, totuși, crearea unor liste înlănțuite speciale, se poate aplica unul din următoarele procedee:

Clasa LinkedList

Clasa java.util.LinkedList extinde clasa AbstractSeqentialList care, la rândul ei, extinde clasa AbstractList. Instanțele clasei LinkedList sunt liste dublu înlănțuite, ale căror noduri conțin referințe la Object, deci elementele listei pot fi orice obiecte. Această clasă este avantajoasă atunci când operațiile se fac în special asupra elementelor din capul sau din coada listei, deoarece astfel de operații au complexitate constantă O(1). Pot fi folosite în mod convenabil, de asemenea, atunci când prelucrarea elementelor se face secvențial (în ordinea în care ele se gasesc în listă).

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:
   public ListIterator listIterator() - întoarce un iterator de listă poziționat inițial pe capul acesteia;
   public ListIterator listIterator(int index) - întoarce un iterator de listă, care începe iterarea de la elementul de indice index.

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). 
 
import java.util.*;

class TestLista {
  public static void main(String args[]) {
    LinkedList lista=new LinkedList();
    String[] ts1={"A1", "A2", "A", "B"}, ts2={"A2", "B"};
    List lista1=Arrays.asList(ts1), lista2=Arrays.asList(ts2);
    System.out.println("S-a creat lista "+lista);
    lista.add("A"); lista.add("B"); lista.add("C");
    System.out.println("Dupa adaugarea A, B, C: "+lista);
    lista.addFirst("X");
    lista.addLast("Z");
    System.out.println("Dupa adaugare in cap si la coada: "+lista);
    lista.add(2,"I");
    System.out.println("Inserare la indice 2: "+lista);
    System.out.println("Lungimea listei: "+lista.size());
    lista.addAll(lista1);
    System.out.println("S-a adaugat lista1: "+lista);
    System.out.println("Contine obiectul A1: "+
      lista.contains("A1"));
    System.out.println("Ultimul indice al lui A: "+
      lista.lastIndexOf("A"));
    System.out.println("Contine lista2: " + lista.containsAll(lista2));
    lista.removeAll(lista2);
    System.out.println("Dupa extragere: "+lista);
    ListIterator iter=lista.listIterator();
    System.out.println("Afisarea listei folosind iteratorul: ");
    while(iter.hasNext()) 
      System.out.print(iter.next()+" ");
    System.out.println("\nAfisarea listei in ordine inversa " +
        "cu acelasi iterator");
    while(iter.hasPrevious())
      System.out.print(iter.previous()+" ");
    System.out.println();
  }
}

Iată și rezultatul executării acestei aplicații:
S-a creat lista []
Dupa adaugarea A, B, C: [A, B, C]
Dupa adaugarea in cap si la coada: [X, A, B, C, Z]
Inserare la indice 2: [X, A, I, B, C, Z]
Lungimea listei: 6
S-a adaugat lista1: [X, A, I, B, C, Z, A1, A2, A, B]
Contine obiectul A1: true
Ultimul indice al lui A: 8
Contine lista2: true
Dupa extragere: [X, A, I, C, Z, A1, A]
Afisarea listei folosind iteratorul:
X A I C Z A1 A
Afisarea listei in ordine inversa cu acelasi iterator
A A1 Z C I A X

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.

Stiva realizată ca listă înlănțuită

Pentru realizarea unei stive, putem folosi o listă înlănțuită, punând condiția ca operațiile de vizitare, punere și scoatere a elementelor să se facă numai la unul din capetele listei, pe care îl vom numi varful stivei. Dacă dorim ca utilizatorul să nu poată folosi alte metode ale listei, putem sa creem o "clasă acoperitoare", în care lista apare ca un câmp privat și care conține numai metodele de lucru cu o stivă.
 
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ă.

Coada realizată ca listă înlănțuită

Pentru realizarea unei cozi se poate folosi, de asemenea, o listă înlănțuită, punând condiția ca punerea unui element în coadă sa se facă la sfarșitul listei, iar scoaterea elementului să se facă numai din capul listei. În cazul listelor din clasa LinkedList se vor folosi metodele addLast si, respectiv, removeFirst. Dacă se dorește ca utilizatorul să nu poată folosi alte metode ale listei, aceasta poate fi încapsulată într-o clasă acoperitoare, la fel cum s-a procedat în cazul stivei.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunărea de Jos" din Galați