Salutare,
Astăzi vom compara două dintre cele mai populare implementări de liste în Java: ArrayList vs LinkedList. Vom evidenția o serie de asemănări și deosebiri între cele două implementări. În plus, vom studia și modul în care datele sunt organizate în memorie pentru fiecare din cele două tipuri.
Una dintre cele mai importante asemănări o reprezintă faptul că ambele clase vor implementa aceeați interfață: List. Lucru de altfel evident, pentru că vorbim în ambele cazuri de liste. Interfața List oferă un API comun pentru ambele clase, API prin care se poate obține un element, adăuga unul nou, șterge un element sau de ce nu obține chiar dimensiunea listei respective. Tot la capitolul asemănări putem menționa și faptul că ambele liste implementează interfețe Cloneable și Serializable. Apare și totuși o diferență: LinkedList implementează interfața Deque, iar ArrayList interfața RandomAccess. Dacă ne uităm în JDK, vom observa că interfața RandomAccess nu este altceva decât o interfață marker, care indică faptul că implementarea respectivă suportă acces rapid la un element - adică timp constant.
Acum, dacă nu ar fi și câteva diferențe, cu siguranță că nu am fi vorbit acum de două implementări. Ce rost are să existe două implementări, dacă nu există nicio diferență între ele? Ca să înțelegem mai bine diferențele, vom studia mai întâi modul în care datele sun organizate în memorie.
Organizarea în memorie a unui ArrayList
Toate elementele unui ArrayList sunt prezente în memorie într-un spațiu continuu. Această proprietate este asigurată de către JVM. Proprietatea este deosebit de importantă pentru a putea asigura un timp de access super rapid la oricare din elementele listei respective. Neajunsul acestei organizări este faptul că de fiecare dată când adăugăm elemente, acestea trebuie să fie într-un spațiu continuu.
Haideți să luăm și un exemplu practic: să zicem că avem o listă cu 5 elemente. Dacă am spus că aceste elemente trebuie să fie într-un spațiu continuu, înseamnă că în memorie lista noastră ar arăta astfel:
În momentul în care lista este creată, adresa listei va pointa către p. Pentru a accesa ultimul element al listei, în cazul unui ArrayList, se va calcula rapid adresa acestuia astfel: p + 4 x sizeof(Integer), unde sizeof(Integer) reprezintă numărul de bytes necesari pentru a stoca o referință către un obiect de tip Integer. Altfel zis, accesul la oricare element din listă se face în timp constant - O(1).
În momentul în care o listă este creată, by default se alocă o capacitate prin care se pot stoca 10 elemente. Cu alte cuvinte, dacă avem 5 elemente de stocat, lista noastră va mai rezerva încă 5 elemente pentru o utilizare viitoare. De ce? Ideea de bază este că o dată creată o instanță de ArrayList, de obicei, vom mai adăuga și alte elemente. Dar ce se întâmplă dacă vrem să adăugăm încă 6 elemente la cele 5 deja existente (să le adăugăm la final)? Răspunsul este simplu: următoarele 5 elemente să adăugă rapid, pentru că avem capacitatea necesară. În momentul în care ajungem la al 6-lea element, va trebui să facem un resize, noua capacitate devenind: 10 + (10 >> 1) = 15. Dar ce se poate întâmpla rău în cazul acestui resize? Păi s-ar putea să nu mai găsim spațiu continuu de memorie în care să fie alocate cele 15 elemente, caz în care o nouă zonă de memorie va fi alocată și întreaga listă va fi mutată acolo. Dacă lista este mare ca și dimensiune, această operație va fi costisitoare.
În exemplul de mai sus, am adăugat elemente la finalul listei. Ce s-ar întâmpla dacă am fi nevoiți să adăugăm un element la începutul sau mijlocul unei ArrayList? Lucrurile sunt cât se poate de intuitive. Primele elemente de la stânga vor rămâne pe poziția lor, iar toate elementele din dreapta poziției de inserare vor fi shiftate cu o poziție. O altă operație consumatoare de timp. În cazul unui delete, lucrurile sunt asemănătoare. Doar dacă ștergem de la final, operația este mai rapidă. Acestea fiind spuse, adăugarea unui element pe o anumită poziție are o complexitate de timp liniară - O(n). La fel și operația de ștergere a unui element de pe o poziție.
De multe ori ne aflăm în situația în care ne dorim să copiem o listă cu N elemente, cu alte cuvinte o listă cu size cunoscut, într-o altă listă de tipul - ArrayList. Pentru a consuma cât mai puțină memorie și a evita operațiile de resize alte capacității, se recomandă să construim lista cu o capacitate predefinită. Acest lucru se poate face prin folosirea constructorului aferent, ce permite definirea unei capacități inițiale.
Organizarea în memorie a unui LinkedList
Față de ArrayList, această implementare de listă nu are elementele într-un spațiu continuu de memorie. Dacă ar fi să lucăm fix exemplul unei liste cu 5 elemente, organizarea în memorie a acestei liste este următoarea:
Se poate observa cu ușurință că pentru a ajunge la ultimul element (cel cu valoarea 5), va trebui să trecem prin fiecare element al listei. De ce? Pentru că în cazul unui LinkedList, fiecare element (nod) din acesta va stoca atât valoarea dorită cât și o referință către adresa următorului nod. Din acest motiv, traversarea listei pentru a obține un anumit element de pe o poziție se face în O(n) - complexitate liniară. Acesta este clar un dezavantaj față de un ArrayList. Un alt dezavantaj se faptul că vom consuma mai multă memorie pentru a stoca N elemente față de a stoca N elemente în ArrayList datorită acelui pointer către next.
Sunt totuși și câteva avantaje în folosirea unui LinkedList. Principalul avantaj este faptul că nu mai avem nevoie de resize atunci când adăugăm elemente. Adăugarea unui element îjn mijlocul listei este destul de simplu de realizat, pentru că doar se vor reface legăturile dintre mai multe noduri. Cu alte cuvinte, dacă avem mai multe operații de inserție în aplicația noastră și destul de puține operații de get, folosirea unui LinkedList poate este mai bună decât a unui ArrayList.
Totuși, în practică, de cele mai multe ori se folosește ArrayList. Sunt foarte rare usecase-urile în care se pretează utilizarea lui LinkedList.
O altă asemănare între cele două tipuri de implementări de liste este faptul că nu sunt thread safe. Ce înseamnă acest lucru? Foarte simplu. Dacă avem mai multe fire de execuții care scriu sau citesc date din aceeași listă, va trebui să implementăm mecanisme de sincronizare pentru a asigura consistența operațiilor. Cea mai simplă modalitatea de a sincroniza accesul la o listă este să folosim keyword-ul sinchronized pe obiectul nostru. Bineînțeles că dacă avem un raport mai mare de citiri în favoarea scrierilor, acest tip de sincronizare va impacta performanța aplicației noastre. În acest caz, poate se pretează mai bine folosirea unei alte implementări de liste - CopyOnWriteArrayList. Vom vorbi despre această implementare în unul din următoarele articole. :D
Concluzii
Acestea fiind spuse, este important să știm cum funcținează cele mai întâlnite două tipuri de implementări în Java. Listele sunt poate cele mai folosite structuri de date din cadrul unei aplicații. Personal, nu am întâlnit nicio aplicație în real life care să nu folosească cel puțin o listă. Am prezentat atât cele mai importante asemănări cât și cele mai importante deosebiri, în așa fel încât să fie ușor de înțeles când ar trebui să fie folosită fiecare din cele două. Capitolul de colecții este deosebit de important în fiecare limbaj de programare și cel mai probabil capitolul cel mai întâlnit la interviuri.
Sper că acest material a fost unul util și în urma urmăririi acestui articol setul dvs. de cunoștiințe s-a îmbogățit semnificativ.
