Realizarea listelor inlantuite folosind pachetul java.util

In pachetul java.util exista clasa LinkedList, ale carei instante sunt liste dublu inlantuite. In majoritatea situatiilor este suficienta folosirea acestei clase. Daca se doreste, totusi, crearea unor liste inlantuite speciale, swe poate aplica unul din urmatoarele procedee:

Clasa LinkedList

Clasa java.util.LinkedList extinde clasa AbstractSeqentialList care, la randul ei, extinde clasa AbstractList. Instantele clasei LinkedList sunt liste dublu inlantuite, ale caror noduri contin referinte la Object, deci elementele listei pot fi orice obiecte. Aceasta clasa este avantajoasa atunci cand operatiile se fac in special asupra elementelor din capul sau din coada listei, deoarece astfel de operatii au complexitate constanta. Pot fi folosite in mod convenabil, de asemenea, atunci cand prelucrarea elementelor se face secvential (in ordinea in care ele se gasesc in lista).

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:
   public ListIterator listIterator() - intoarce un iterator de lista pozitionat initial pe capul acesteia;
   public ListIterator listIterator(int index) - intoarce un iterator de lista, care incepe iterarea de la elementul de indice index.

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). 
 
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();
  }
}

Iata si rezultatul executarii acestei aplicatii:
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 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.

Stiva realizata ca lista inlantuita

Pentru realizarea unei stive putem folosi o lista inlantuita, punand conditia ca operatiile de vizitare, punere si scoatere a elementelor sa se faca numai la unul din capetele listei, pe care il vom numi varful stivei. Daca dorim ca utilizatorul sa nu poata folosi alte metode ale listei, putem sa creem o "clasa acoperitoare", in care lista apare ca un camp privat si care contine numai metodele de lucru cu o stiva.
 
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.

Coada realizata ca lista inlantuita

Pentru realizarea unei cozi se poate folosi, de asemenea, o lista inlantuita, punand conditia ca punerea unui element in coada sa se faca la sfarsitul listei, iar scoaterea elementului sa se faca numai din capul listei. In cazul listelor din clasa LinkedList se vor folosi metodele addLast si, respectiv, removeFirst. Daca se doreste ca utilizatorul sa nu poata folosi alte metode ale listei, aceasta poate fi incapsulata intr-o clasa acoperitoare, la fel cum s-a procedat in cazul stivei.



© Copyright 2001 - Severin BUMBARU, Universitatea "Dunarea de Jos" din Galati