Pe parcursul laboratoarelor și temelor ați folosit structuri de date oferite de API-ul Java. În cadrul acestui laborator le vom aprofunda.
În pachetul java.util (pachet standard din JRE) existǎ o serie de clase pe care le veti găsi folositoare. Collections Framework este o arhitectură unificată pentru reprezentarea şi manipularea colecţiilor. Ea conţine:
Colecţiile oferǎ implementǎri pentru urmǎtoarele tipuri:
Existǎ o interfaţǎ, numitǎ Collection, pe care o implementeazǎ majoritatea claselor ce desemneazǎ colecţii din java.util. Explicaţii suplimentare gǎsiţi pe Java Tutorials - Collection
Exemplul de mai jos construieşte o listǎ populatǎ cu nume de studenţi:
Collection names = new ArrayList(); names.add("Andrei"); names.add("Matei");
Colecţiile pot fi parcurse (element cu element) folosind:
Un iterator este un obiect care permite traversarea unei colecţii şi modificarea acesteia (ex: ştergere de elemente) în mod selectiv. Puteţi obţine un iterator pentru o colecţie, apelând metoda sa iterator(). Interfaţa Iterator este urmǎtoarea:
public interface Iterator<E> { boolean hasNext(); E next(); void remove(); // optional }
Exemplu de folosire a unui iterator:
Collection<Double> col = new ArrayList<Double>(); Iterator<Double> it = col.iterator(); while (it.hasNext()) { Double backup = it.next(); // apelul it.next() trebuie realizat înainte de apelul it.remove() if (backup < 5.0) { it.remove(); } }
Apelul metodei remove() a unui iterator face posibilă eliminarea elementului din colecţie care a fost întors la ultimul apel al metodei next() din acelaşi iterator. În exemplul anterior, toate elementele din colecţie mai mici decât 5 for fi şterse la ieşirea din bucla while.
Aceastǎ construcţie permite (într-o manierǎ expeditivǎ) traversarea unei colecţii. for-each este foarte similar cu for. Urmǎtorul exemplu parcurge elementele unei colecţii şi le afişeazǎ.
Collection collection = new ArrayList(); for (Object o : collection) System.out.println(o);
Construcţia for-each se bazeazǎ, în spate, pe un iterator, pe care îl ascunde. Prin urmare nu putem şterge elemente în timpul iterǎrii. În aceastǎ manierǎ pot fi parcurşi şi vectori oarecare. De exemplu, collection ar fi putut fi definit ca Object[].
Fie urmǎtoarea porţiune de cod:
c.add("Test"); Iterator it = c.iterator(); while (it.hasNext()) { String s = it.next(); // ERROR: next() returns an Object and it's needed an explicit cast to String String s = (String)it.next(); // OK }
Am definit o colecţie c, de tipul ArrayList (pe care îl vom examina într-o secţiune urmǎtoare). Apoi, am adǎugat în colecţie un element de tipul String. Am realizat o parcurgere folosind un iterator, şi am încercat obţinerea elementului nostru folosind apelul: String s = it.next();. Funcţia next însǎ întoarce un obiect de tip Object. Prin urmare apelul va eşua. Varianta corectǎ este String s = (String)it.next();. Am fi putut preciza, din start, ce tipuri de date dorim într-o colecţie:
Collection<String> c = new ArrayList<String>(); c.add("Test"); c.add(2); // ERROR! Iterator<String> it = c.iterator(); while (it.hasNext()) { String s = it.next(); }
Mai multe detalii despre acest subiect găsiți in laboratorul următor: Genericitate
O listǎ este o colecţie ordonatǎ. Listele pot conţine elemente duplicate. Pe langǎ operaţiile moştenite de la Collection, interfaţa List contine operaţii bazate pe pozitie (index), de exemplu: set, get, add la un index, remove de la un index.
List<String> fruits = new ArrayList<>(Arrays.asList("Apple", "Orange", "Grape")); fruits.add("Apple"); // metodă moștenită din Collection fruits.add(2, "Pear"); // [Apple, Orange, Pear, Grape, Apple] System.out.println(fruits.get(3)); // Grape fruits.set(1, "Cherry"); // [Apple, Cherry, Pear, Grape, Apple] fruits.remove(2); System.out.println(fruits); // [Apple, Cherry, Grape, Apple]
Alǎturi de List, este definitǎ interfaţa ListIterator, ce extinde interfaţa Iterator cu metode de parcurgere în ordine inversǎ. List posedǎ douǎ implementǎri standard:
ArrayList - implementare sub formǎ de vector. Accesul la elemente se face în timp constant: O(1)LinkedList - implementare sub formǎ de listǎ dublu înlǎnţuitǎ. Prin urmare, accesul la un element nu se face în timp constant, fiind necesarǎ o parcurgere a listei: O(n).Printre algoritmii implementaţi se numără:
sort - realizeazǎ sortarea unei listebinarySearch - realizaeazǎ o cǎutare binarǎ a unei valori într-o listǎ sortatǎÎn general, algoritmii pe colecţii sunt implementaţi ca metode statice în clasa Collections.
Collection cu clasa Collections. Spre deosebire de prima, a doua este o clasǎ ce conţine exclusiv metode statice. Aici sunt implementate diverse operaţii asupra colecţiilor.
Iatǎ un exemplu de folosire a sortǎrii:
List<Integer> l = new ArrayList<Integer>(); l.add(5); l.add(7); l.add(9); l.add(2); l.add(4); Collections.sort(l); System.out.println(l);
Mai multe detalii despre algoritmi pe colecţii gǎsiţi pe Java Tutorials - Algoritmi pe liste
Rularea exemplului de sortare ilustrat mai sus aratǎ cǎ elementele din ArrayList se sorteazǎ crescator. Ce se întâmplǎ când dorim sǎ realizǎm o sortare particularǎ pentru un tip de date complex? Spre exemplu, dorim sǎ sortǎm o listǎ ArrayList<Student> dupǎ media anilor. Sǎ presupunem cǎ Student este o clasǎ ce conţine printre membrii sǎi o variabilǎ ce reţine media anilor. Acest lucru poate fi realizat folosind interfeţele:
| Comparable | Comparator | |
| Logica de sortare | Logica de sortare trebuie sa fie în clasa ale cărei obiecte sunt sortate. Din acest motiv, această metodă se numeşte sortare naturală. | Logica de sortare se află într-o clasă separată. Astfel, putem defini mai multe metode de sortare, bazate pe diverse câmpuri ale obiectelor de sortat. |
| Implementare | Clasa ale cărei instanţe se doresc a fi sortate trebuie sa implementeze această interfaţă şi, evident, să suprascrie metoda compareTo(). | Clasa ale cărei instanţe se doresc a fi sortate nu trebuie să implementeze această interfaţă. Este nevoie de o alta clasă (poate fi şi internă) care să implementeze interfaţa Comparator. |
| Metoda de comparare | int compareTo(Object o1) Această metodă compară obiectul curent (this) cu obiectul o1 şi întoarce un întreg. Valoarea întoarsă este interpretată astfel: 1. pozitiv – obiectul este mai mare decât o1 2. zero – obiectul este egal cu o1 3. negativ – obiectul este mai mic decât o1 | int compare(Object o1,Object o2) Această metodă compară obiectele o1 and o2 şi întoarce un întreg. Valoarea întoarsă este interpretată astfel: 1. pozitiv – o2 este mai mare decât o1 2. zero – o2 este egal cu o1 3. negativ – o2 este mai mic decât o1 |
| Metoda de sortare | Collections.sort(List) Aici obiectele sunt sortate pe baza metodei compareTo(). | Collections.sort(List, Comparator) Aici obiectele sunt sortate pe baza metodei compare() din Comparator. |
| Pachet | Java.lang.Comparable | Java.util.Comparator |
Un Set (mulţime) este o colecţie ce nu poate conţine elemente duplicate. Interfaţa Set conţine doar metodele moştenite din Collection, la care adaugǎ restricţii astfel încât elementele duplicate sǎ nu poatǎ fi adǎugate. Avem trei implementǎri utile pentru Set:
(hash table); este implementarea cea mai performantǎ, însǎ nu avem garanţii asupra ordinii de parcurgere. Doi iteratori diferiţi pot parcurge elementele mulţimii în ordine diferitǎ.HashSet.HashSet este cǎ LinkedHashSet menţine o listǎ dublu-înlǎnţuitǎ peste toate elementele sale. Prin urmare (şi spre deosebire de HashSet), elementele rǎmân în ordinea în care au fost inserate. O parcurgere a LinkedHashSet va gǎsi elementele mereu în aceastǎ ordine.HashSet, care se bazeazǎ pe o tabelǎ de dispersie, calculeazǎ codul de dispersie al elementelor pe baza metodei hashCode, definitǎ în clasa Object. De aceea, douǎ obiecte egale, conform funcţiei equals, trebuie sǎ întoarcǎ acelaşi rezultat din hashCode.
Explicaţii suplimentare gǎsiti pe Java Tutorials - Set.
Un Map este un obiect care mapeazǎ chei pe valori. Într-o astfel de structurǎ nu pot exista chei duplicate. Fiecare cheie este mapatǎ la exact o valoare. Map reprezintǎ o modelare a conceptului de funcţie: primeşte o entitate ca parametru (cheia), şi întoarce o altǎ entitate (valoarea). Cele trei implementǎri pentru Map sunt:
Particularitǎţile de implementare corespund celor de la Set. Exemplu de folosire:
class Student { String name; float avg; public Student(String name, float avg) { this.name = name; this.avg = avg; } public String toString() { return "[" + name + ", " + avg + "]"; } } public class Test { public static void main(String[] args) { Map<String,Student> students = new HashMap<String, Student>(); students.put("Matei", new Student("Matei", 4.90F)); students.put("Andrei", new Student("Andrei", 6.80F)); students.put("Mihai", new Student("Mihai", 9.90F)); System.out.println(students.get("Mihai")); // adaugăm un element cu aceeași cheie System.out.println(students.put("Andrei", new Student("", 0.0F))); // put(...) întoarce elementul vechi // si îl suprascrie System.out.println(students.get("Andrei")); // remove(...) returnează elementul șters System.out.println(students.remove("Matei")); // afișăm structura de date System.out.println(students); } }
Interfaţa Map.Entry desemneazǎ o pereche (cheie, valoare) din map. Metodele caracteristice sunt:
O iterare obişnuitǎ pe un map se va face în felul urmǎtor:
for (Map.Entry<String, Student> entry : students.entrySet()) System.out.println(entry.getKey() + " has the following average grade: " + entry.getValue().getAverage());
În bucla for-each de mai sus se ascunde, de fapt, iteratorul mulţimii de perechi, întoarse de entrySet. Explicaţii suplimentare gǎsiţi pe Java Tutorials - Map.
Queue defineşte operaţii specifice pentru cozi:
Implementǎri utilizate frecvente pentru Queue:
LinkedList: pe lângǎ List, LinkedList implementeazǎ şi QueuePriorityQueue;Explicaţii suplimentare gǎsiţi pe Java Tutorials - Queue
Map sunt HashMap (neordonat, nesortat), TreeMap (map sortat) și LinkedHashMap (map ordonat)