JD prva faza prakse: pričajmo o Java ArrayList, da li poznajete mehanizam proširenja kapaciteta?
Pošto ArrayList spada među najčešće korišćene klase u okviru kolekcija (ravan je HashMap), posvetićemo mu pažnju u ovom članku.
Već iz imena se vidi da ArrayList implementira List interfejs i da se zasniva na nizovima.
Veličina niza je fiksna — jednom kada se odredi pri kreiranju, ne može se više menjati. Odnosno, ako je niz pun, ne može se dodati nijedan novi element. ArrayList na osnovu niza implementira automatsko proširenje kapaciteta i pruža bogatiji skup predefinisanih metoda od običnog niza (razne operacije dodavanja, brisanja, izmene i pretrage), što je veoma fleksibilno.
Upravo tu se Java razlikuje od drugih programskih jezika, na primer od C-a — u C-u morate sami da implementirate svoj ArrayList, jer ga nema u standardnoj biblioteci.
01. Kreiranje ArrayList
Kako kreirati ArrayList?
ArrayList<String> alist = new ArrayList<String>();Gornjom naredbom kreira se ArrayList tipa String (uglastim zagama se ograničava tip elemenata u ArrayList; ako pokušate da dodate element drugog tipa, dobićete grešku pri kompilaciji). Jednostavniji zapis izgleda ovako:
List<String> alist = new ArrayList<>();Pošto ArrayList implementira List interfejs, tip promenljive alist može biti List; unutar uglastih zagrada posle ključne reči new ne mora se ponovo navoditi tip elementa, jer kompajler može da ga zaključi iz tipa navedenog u uglastim zagama sa leve strane.
Tada se poziva konstruktor bez argumenata (vidi kod ispod) koji kreira prazan niz; vrednost konstante DEFAULTCAPACITY_EMPTY_ELEMENTDATA je {}.
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}Ako ste veoma sigurni u broj elemenata u ArrayList, pri kreiranju možete navesti i početnu veličinu.
List<String> alist = new ArrayList<>(20);Prednost ovog pristupa je što se efikasno izbegava nepotrebno proširenje kapaciteta pri dodavanju novih elemenata.
02. Dodavanje elemenata u ArrayList
Kako dodati element u ArrayList?
Možete koristiti metod add() da dodate element u ArrayList.
alist.add("Chenmo Wang Er");Pratićemo izvorni kod da vidimo šta tačno radi metod add. Tokom praćenja možemo i da „ukrademo zanat” — da vidimo kako autor Java izvornog koda (majstor-programer) elegantno piše kod.
Daću prvo zaključak, kao uvod u detalje.
Prikaz procesa na steku:
add(element)
└── if (size == elementData.length) // provera da li je potrebno proširenje
├── grow(minCapacity) // proširenje
│ └── newCapacity = oldCapacity + (oldCapacity >> 1) // izračunavanje novog kapaciteta niza
│ └── Arrays.copyOf(elementData, newCapacity) // kreiranje novog niza
├── elementData[size++] = element; // dodavanje novog elementa
└── return true; // uspešno dodavanjePogledajmo detaljno, prvo izvorni kod metoda add() (sa detaljnim komentarima):
/**
* Dodaje zadati element na kraj ArrayList
* @param e element koji se dodaje
* @return vraća true ako je dodavanje uspelo
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // osigurava da ArrayList može da primi novi element
elementData[size++] = e; // dodaje zadati element na kraj ArrayList
return true;
}Parametar e je element koji se dodaje, sa vrednošću „Chenmo Wang Er”; size je dužina ArrayList, u ovom trenutku 0.
Idemo dalje, pogledajmo metod ensureCapacityInternal():
/**
* Osigurava da ArrayList može da primi elemente zadatog kapaciteta
* @param minCapacity minimalna vrednost zadatog kapaciteta
*/
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { // ako je elementData još uvek podrazumevani prazan niz
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); // uzima veću od vrednosti DEFAULT_CAPACITY i zadatog kapaciteta
}
ensureExplicitCapacity(minCapacity); // osigurava da kapacitet može da primi elemente zadatog kapaciteta
}U ovom trenutku:
- Parametar minCapacity je 1 (prosleđeno iz size+1)
- elementData je pozadinski niz koji čuva elemente ArrayList; kao što je rečeno pri deklarisanju ArrayList, sada je prazan
{} - DEFAULTCAPACITY_EMPTY_ELEMENTDATA je, kao što je već rečeno,
{}
Dakle if-uslov je sada tačan, pa se izvršava naredba u if-bloku minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity).
DEFAULT_CAPACITY je 10 (vidi kod ispod), pa se nakon izvršenja te linije minCapacity postavlja na 10. Metod Math.max() vraća veću od dve vrednosti.
private static final int DEFAULT_CAPACITY = 10;Zatim se izvršava metod ensureExplicitCapacity(), pogledajmo izvorni kod:
/**
* Proverava i osigurava da je kapacitet kolekcije dovoljan; po potrebi povećava kapacitet.
*
* @param minCapacity potreban minimalni kapacitet
*/
private void ensureExplicitCapacity(int minCapacity) {
// proverava da li je prekoračen opseg niza, osigurava da ne dođe do preliva
if (minCapacity - elementData.length > 0)
// ako je potrebno povećati kapacitet, poziva metod grow
grow(minCapacity);
}U ovom trenutku:
- Parametar minCapacity je 10
- elementData.length je 0 (niz je prazan)
Dakle 10-0>0, if-uslov je tačan, ulazi se u if-blok i poziva metod grow(). Pogledajmo izvorni kod:
/**
* Metod za proširenje ArrayList, osigurava da može da primi elemente zadatog kapaciteta
* @param minCapacity minimalna vrednost zadatog kapaciteta
*/
private void grow(int minCapacity) {
// proverava da li će doći do preliva; oldCapacity je trenutna dužina niza
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1); // proširenje na 1,5 puta veću vrednost
if (newCapacity - minCapacity < 0) // ako je i dalje manje od minimalnog zadatog kapaciteta
newCapacity = minCapacity; // proširuje direktno na minimalni zadati kapacitet
if (newCapacity - MAX_ARRAY_SIZE > 0) // ako prelazi maksimalnu dužinu niza
newCapacity = hugeCapacity(minCapacity); // proširuje na maksimalnu dužinu niza
// kopira trenutni niz u novi niz dužine newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);
}U ovom trenutku:
- Parametar minCapacity je 10
- Promenljiva oldCapacity je 0
Dakle newCapacity je takođe 0, pa je newCapacity - minCapacity jednako -10, što je manje od 0, pa je prvi if-uslov tačan i izvršava se prva if-naredba newCapacity = minCapacity, čime newCapacity postaje 10.
Odmah zatim se izvršava elementData = Arrays.copyOf(elementData, newCapacity);, odnosno vrši se prvo proširenje niza, na dužinu 10.
Vraćamo se na metod add():
public boolean add(E e) {
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}Izvršava se elementData[size++] = e.
U ovom trenutku:
- size je 0
- e je „Chenmo Wang Er”
Dakle prvom elementu niza (indeks 0) dodeljuje se vrednost „Chenmo Wang Er”, zatim se vraća true i prvi poziv metoda add je završen.
PS: Tokom add-a može se naići na operator desnog pomeranja >> koji zbunjuje početnike — iskoristimo ovu priliku da ga objasnimo.
ArrayList se nakon prvog add-a proširuje na 10. Kada se događa drugo proširenje ArrayList?
Odgovor je: pri dodavanju 11. elementa. Možete pokušati sami da analizirate taj proces.
03. Operator desnog pomeranja
oldCapacity je jednako 10, koliko izraz oldCapacity >> 1 daje?
Šta znači >>? >> je operator desnog pomeranja; oldCapacity >> 1 je jednako oldCapacity podeljeno sa 2. U računaru se sve skladišti u binarnom obliku. Binarni zapis broja 10 je 1010, odnosno 0*2^0 + 1*2^1 + 0*2^2 + 1*2^3=0+2+0+8=10 ……
Zašto je to tako? Krenimo najpre od značenja težine pozicije.
Uobičajeno koristimo dekadni sistem, na primer broj 39 nije prosto 3 i 9 — 3 predstavlja 3*10 = 30, a 9 predstavlja 9*1 = 9. Broj 10 kojim se množi 3 i broj 1 kojim se množi 9 upravo su težine pozicije. Težina pozicije zavisi od pozicije cifre: prva pozicija je 10 na nulu (odnosno 10^0=1), druga pozicija je 10 na prvu (10^1=10), treća pozicija je 10 na drugu (10^2=100). Najdesnija pozicija je prva, i tako redom.
Koncept težine pozicije važi i za binarni sistem: prva pozicija je 2 na nulu (odnosno 2^0=1), druga pozicija je 2 na prvu (2^1=2), treća pozicija je 2 na drugu (2^2=4), četvrta pozicija je 2 na treću (2^3=8).
U dekadnom sistemu baza je 10, a u binarnom sistemu baza je 2.
Broj 10 u dekadnom sistemu je 0*10^0+1*10^1=0+10=10.
Binarni zapis broja 10 je 1010, odnosno 0*2^0 + 1*2^1 + 0*2^2 + 1*2^3=0+2+0+8=10.
Zatim operacija pomeranja. Pomeranje se deli na levo i desno; u Javi je operator levog pomeranja <<, a operator desnog pomeranja >>.
Uzmimo oldCapacity >> 1: sa leve strane >> nalazi se vrednost koja se pomera, ovde 10, odnosno binarno 1010; sa desne strane >> nalazi se broj pozicija za pomeranje, ovde 1.
1010 pomeren udesno za jedno mesto daje 101, a najviši bit koji ostane prazan dopunjuje se nulom, što daje 0101.
Zašto se ne dopuni jedinicom? Zato što je u pitanju aritmetičko desno pomeranje, a broj je pozitivan, pa se najviši bit dopunjuje nulom; kada bi broj bio negativan, dopunio bi se jedinicom. 0101 u dekadnom sistemu je upravo 1*2^0 + 0*2^1 + 1*2^2 + 0*2^3=1+0+4+0=5. Ako pomerite još nekoliko brojeva da biste uočili pravilnost, primetićete da pomeranje udesno za jednu poziciju daje polovinu originala, za dve pozicije četvrtinu, i tako dalje.
Odnosno, veličina ArrayList se proširuje na originalna veličina + originalna veličina/2, što je 1,5 puta.
Sada je jasno, zar ne?
Možete to proveriti debugovanjem tako što ćete u ArrayList dodati 11. element.
04. Dodavanje elementa na zadatu poziciju u ArrayList
Pored metoda add(E e), možete koristiti i metod add(int index, E element) da dodate element na zadatu poziciju u ArrayList:
alist.add(0, "Chenmo Wang San");Izvorni kod metoda add(int index, E element) izgleda ovako:
/**
* Umeće element na zadatu poziciju.
*
* @param index pozicija na koju se umeće element
* @param element element koji se umeće
* @throws IndexOutOfBoundsException baca se ako je indeks izvan opsega
*/
public void add(int index, E element) {
rangeCheckForAdd(index); // proverava da li je indeks izvan opsega
ensureCapacityInternal(size + 1); // osigurava dovoljan kapacitet, po potrebi proširuje
System.arraycopy(elementData, index, elementData, index + 1,
size - index); // pomera element na indeksu i sve nakon njega za jedno mesto unazad
elementData[index] = element; // umeće element na zadatu poziciju
size++; // povećava broj elemenata za jedan
}Metod add(int index, E element) poziva jedan veoma važan lokalni metod System.arraycopy(), koji vrši kopiranje niza (elemente sa pozicije umetanja pomera unazad).
Pogledajmo detaljnije.
Ovo je sintaksa metoda arraycopy():
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length);U metodu ArrayList.add(int index, E element) koristi se na sledeći način:
System.arraycopy(elementData, index, elementData, index + 1, size - index);- elementData: izvorni niz koji se kopira, odnosno niz elemenata u ArrayList.
- index: početna pozicija kopiranja u izvornom nizu, odnosno potrebno je pomeriti element na indeksu i sve nakon njega za jedno mesto unazad.
- elementData: odredišni niz u koji se kopira, odnosno niz elemenata u ArrayList.
- index + 1: početna pozicija kopiranja u odredišnom nizu, odnosno pozicija na koju treba smestiti element na indeksu i sve nakon njega nakon pomeranja za jedno mesto unazad.
- size - index: broj elemenata koji se kopiraju, odnosno broj elemenata koje treba pomeriti za jedno mesto unazad (od indeksa do kraja), a iznosi size - index.
Obrati pažnju, nacrtaćemo sliku da to prikažemo.
05. Ažuriranje elemenata u ArrayList
Možete koristiti metod set() da izmenite element u ArrayList; potrebno je da navedete indeks i novi element.
alist.set(0, "Chenmo Wang Si");Pretpostavimo da je na poziciji 0 prvobitno bio element „Chenmo Wang San”; sada ga možemo ažurirati na „Chenmo Wang Si”.
Pogledajmo izvorni kod metoda set():
/**
* Zamenjuje element na zadatoj poziciji zadatim elementom.
*
* @param index indeks elementa koji se zamenjuje
* @param element element koji se skladišti na zadatoj poziciji
* @return element koji se prethodno nalazio na zadatoj poziciji
* @throws IndexOutOfBoundsException baca se ako je indeks izvan opsega
*/
public E set(int index, E element) {
rangeCheck(index); // proverava da li je indeks izvan opsega
E oldValue = elementData(index); // dohvata prethodni element na zadatoj poziciji
elementData[index] = element; // zamenjuje novom vrednošću na zadatoj poziciji
return oldValue; // vraća prethodni element na zadatoj poziciji
}Metod prvo proverava da li je zadati indeks validan (da li je izvan opsega), zatim zamenjuje novu vrednost i vraća staru.
06. Brisanje elemenata iz ArrayList
Metod remove(int index) koristi se za brisanje elementa na zadatom indeksu, a metod remove(Object o) za brisanje elementa zadate vrednosti.
alist.remove(1);
alist.remove("Chenmo Wang Si");Pogledajmo prvo izvorni kod metoda remove(int index):
/**
* Briše element sa zadate pozicije.
*
* @param index indeks elementa koji se briše
* @return element koji se prethodno nalazio na zadatoj poziciji
* @throws IndexOutOfBoundsException baca se ako je indeks izvan opsega
*/
public E remove(int index) {
rangeCheck(index); // proverava da li je indeks izvan opsega
E oldValue = elementData(index); // dohvata element koji se briše
int numMoved = size - index - 1; // izračunava broj elemenata koje treba pomeriti
if (numMoved > 0) // ako je potrebno pomeriti elemente, koristi System.arraycopy
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // postavlja poslednji element niza na null, kako bi GC oslobodio prostor
return oldValue; // vraća obrisani element
}Treba napomenuti da pri brisanju elementa iz ArrayList elementi nakon pozicije brisanja moraju da se pomere za jedno mesto unapred, kako bi se popunila praznina nastala brisanjem. Ako je potrebno pomeriti elemente, koristi se metod System.arraycopy da se elementi nakon pozicije brisanja pomere za jedno mesto unapred. Na kraju se poslednji element niza postavlja na null, kako bi mehanizam za sakupljanje smeća oslobodio prostor koji je taj element zauzimao.
Pogledajmo sada izvorni kod metoda remove(Object o):
/**
* Briše prvo pojavljivanje zadatog elementa u listi (ako postoji).
*
* @param o element koji se briše
* @return vraća true ako lista sadrži zadati element; inače vraća false
*/
public boolean remove(Object o) {
if (o == null) { // ako je element koji se briše null
for (int index = 0; index < size; index++) // obilazi listu
if (elementData[index] == null) { // ako je pronađen null element
fastRemove(index); // poziva metod fastRemove za brzo brisanje elementa
return true; // vraća true, što znači da je brisanje uspelo
}
} else { // ako element koji se briše nije null
for (int index = 0; index < size; index++) // obilazi listu
if (o.equals(elementData[index])) { // ako je pronađen element koji se briše
fastRemove(index); // poziva metod fastRemove za brzo brisanje elementa
return true; // vraća true, što znači da je brisanje uspelo
}
}
return false; // ako element nije pronađen, vraća false
}Ovaj metod pronalazi element koji treba obrisati obilaskom: kada je vrednost null koristi operator ==, a kada nije null koristi metod equals(), a zatim poziva metod fastRemove().
Napomena:
- Ako postoje istovetni elementi, biće obrisan samo prvi.
- Za proveru jednakosti dva elementa možete pogledati Kako Java proverava jednakost dva stringa.
Nastavljamo dalje, pogledajmo metod fastRemove():
/**
* Brzo briše element sa zadate pozicije.
*
* @param index indeks elementa koji se briše
*/
private void fastRemove(int index) {
int numMoved = size - index - 1; // izračunava broj elemenata koje treba pomeriti
if (numMoved > 0) // ako je potrebno pomeriti elemente, koristi System.arraycopy
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // postavlja poslednji element niza na null, kako bi GC oslobodio prostor
}I ovde se poziva metod System.arraycopy() za kopiranje i pomeranje niza.
Chenmo Wang Er"); alist.lastIndexOf("Chenmo Wang Er");
Pogledajmo izvorni kod metoda `indexOf()`:
```java
/**
* Vraća poziciju prvog pojavljivanja zadatog elementa u listi.
* Ako lista ne sadrži taj element, vraća -1.
*
* @param o element koji se traži
* @return pozicija prvog pojavljivanja zadatog elementa u listi; ako lista ne sadrži taj element, vraća -1
*/
public int indexOf(Object o) {
if (o == null) { // ako je element koji se traži null
for (int i = 0; i < size; i++) // obilazi listu
if (elementData[i]==null) // ako je pronađen null element
return i; // vraća indeks elementa
} else { // ako element koji se traži nije null
for (int i = 0; i < size; i++) // obilazi listu
if (o.equals(elementData[i])) // ako je pronađen traženi element
return i; // vraća indeks elementa
}
return -1; // ako element nije pronađen, vraća -1
}Kada je element null koristi se operator „==", inače se koristi metod equals().
Metod lastIndexOf() je sličan metodu indexOf(), ali obilazi listu otpozadi.
/**
* Vraća poziciju poslednjeg pojavljivanja zadatog elementa u listi.
* Ako lista ne sadrži taj element, vraća -1.
*
* @param o element koji se traži
* @return pozicija poslednjeg pojavljivanja zadatog elementa u listi; ako lista ne sadrži taj element, vraća -1
*/
public int lastIndexOf(Object o) {
if (o == null) { // ako je element koji se traži null
for (int i = size-1; i >= 0; i--) // obilazi listu otpozadi
if (elementData[i]==null) // ako je pronađen null element
return i; // vraća indeks elementa
} else { // ako element koji se traži nije null
for (int i = size-1; i >= 0; i--) // obilazi listu otpozadi
if (o.equals(elementData[i])) // ako je pronađen traženi element
return i; // vraća indeks elementa
}
return -1; // ako element nije pronađen, vraća -1
}Metod contains() može da utvrdi da li ArrayList sadrži neki element; interno se oslanja na metod indexOf():
public boolean contains(Object o) {
return indexOf(o) >= 0;
}08. Binarna pretraga
Ako su elementi u ArrayList sortirani, može se koristiti binarna pretraga, koja je efikasnija.
Metod sort() klase Collections može sortirati ArrayList; ovaj metod sortira listu tipa String po abecednom redosledu. Za listu korisnički definisanih tipova može se zadati i Comparator za sortiranje.
Ovde ćemo se upoznati sa osnovama; detaljno ćemo obraditi ovu temu kasnije.
List<String> copy = new ArrayList<>(alist);
copy.add("a");
copy.add("c");
copy.add("b");
copy.add("d");
Collections.sort(copy);
System.out.println(copy);Izlaz izgleda ovako:
[a, b, c, d]Nakon sortiranja možemo koristiti binarnu pretragu:
int index = Collections.binarySearch(copy, "b");09. Vremenska složenost operacija dodavanja, brisanja, izmene i pretrage u ArrayList
dopunim nakon gutljaja vode.
1) Pretraga
Vremenska složenost je O(1), jer ArrayList interno koristi niz za skladištenje elemenata, pa se elementi mogu direktno dohvatati po indeksu.
/**
* Vraća element sa zadate pozicije u listi.
*
* @param index indeks elementa koji se vraća
* @return element sa zadate pozicije u listi
* @throws IndexOutOfBoundsException ako je indeks izvan opsega (index < 0 || index >= size())
*/
public E get(int index) {
rangeCheck(index); // proverava da li je indeks validan
return elementData(index); // poziva metod elementData da dohvati element
}
/**
* Vraća element sa zadate pozicije u listi.
* Ovaj metod ne vrši proveru granica, pa bi trebalo da ga pozivaju samo interni metodi i iteratori.
*
* @param index indeks elementa koji se vraća
* @return element sa zadate pozicije u listi
*/
E elementData(int index) {
return (E) elementData[index]; // vraća element na zadatom indeksu
}2) Umetanje
Vremenska složenost dodavanja elementa (poziv metoda add()) u najboljem slučaju je O(1), a u najgorem O(n).
- Ako se element dodaje na kraj liste, vremenska složenost je O(1).
- Ako se element umeće u sredinu ili na početak liste, potrebno je pomeriti sve elemente nakon pozicije umetanja za jedno mesto unazad, pa je vremenska složenost O(n).
3) Brisanje
Vremenska složenost brisanja elementa (poziv metoda remove(Object)) u najboljem slučaju je O(1), a u najgorem O(n).
- Ako se briše element sa kraja liste, vremenska složenost je O(1).
- Ako se briše element iz sredine ili sa početka liste, potrebno je pomeriti sve elemente nakon pozicije brisanja za jedno mesto unapred, pa je vremenska složenost O(n).
4) Izmena
Izmena elementa (poziv metoda set()) je slična pretrazi — element se može direktno dohvatiti po indeksu, pa je vremenska složenost O(1).
/**
* Zamenjuje element na zadatoj poziciji u listi zadatim elementom.
*
* @param index indeks elementa koji se zamenjuje
* @param element element koji se stavlja u listu
* @return element koji se prethodno nalazio na zadatoj poziciji
* @throws IndexOutOfBoundsException ako je indeks izvan opsega (index < 0 || index >= size())
*/
public E set(int index, E element) {
rangeCheck(index); // proverava da li je indeks validan
E oldValue = elementData(index); // dohvata prethodni element na zadatoj poziciji
elementData[index] = element; // zamenjuje element na zadatoj poziciji novim elementom
return oldValue; // vraća prethodni element na zadatoj poziciji
}10. Zaključak
ArrayList bi se, kada bi imao srpsko ime, mogao nazvati dinamičkim nizom — odnosno nizom koja može da raste, čija se veličina može prilagođavati. Dinamički niz prevazilazi ograničenja statičkog niza, čiji je kapacitet fiksiran i može se zadati samo pri prvom kreiranju. Dinamički niz se automatski prilagođava veličini kako broj elemenata raste, što više odgovara stvarnim razvojnim potrebama.
U učenju okvira kolekcija, ArrayList je prvi čas, ali i važan korak za napredovanje početnika. Da biste u potpunosti savladali ArrayList, morate razumeti mehanizam proširenja kapaciteta — to je i tema koja se često proverava na intervjuima.
Da biste savladali mehanizam proširenja, morate čitati izvorni kod, pa ćete sigurno naići na oldCapacity >> 1. Neki početnici će preskočiti taj deo — iako to neće ometati opšte razumevanje, propustiće priliku za dublje usavršavanje.
Kako računar interno predstavlja dekadne brojeve i šta se događa pri desnom pomeranju — smirite se i istražite to, pa ćete otkriti da je zapravo veoma zanimljivo.