Razlika između ArrayList i LinkedList: kako izabrati?
"Zapravo, nakon analize u prethodna dva odeljka, razlika je već prilično jasna." progunđam.
"Brate, kaži još nešto, zađi malo dublje, važi?"
"Dobro, krenimo onda!"
PS: Da bih se lakše razlikovao od izvornog koda u prethodna dva odeljka, ovde koristim izvorni kod iz Java 11, obratite pažnju na to. Ali u celini, razlika je vrlo mala.
01,Kako je ArrayList implementiran?
ArrayList implementira List interfejs i nasleđuje apstraktnu klasu AbstractList.
Donji sloj je zasnovan na nizu i implementira dinamičko proširenje (kada je potrebno dodati novi element, ako je niz elementData pun, automatski se proširuje, a novi kapacitet će biti 1,5 puta veći od originalnog). Pogledajmo deo izvornog koda ArrayList-a.
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final int DEFAULT_CAPACITY = 10; // podrazumevani kapacitet je 10
transient Object[] elementData; // niz za čuvanje elemenata, tip niza je Object
private int size; // veličina liste, odnosno broj elemenata u listi
}ArrayList takođe implementira RandomAccess interfejs, ovo je interfejs za označavanje:
public interface RandomAccess {
}Unutar njega je prazno, i označava da "klase koje implementiraju ovaj interfejs podržavaju brz (obično konstantan) slučajan pristup". Šta znači brz slučajan pristup? Znači da nije potrebno prelaziti kroz elemente, već se putem indeksa može direktno pristupiti memorijskoj adresi. LinkedList ne implementira ovaj interfejs, što znači da ne podržava efikasan slučajan pristup i da do elemenata treba dolaziti prelaskom kroz listu.
/**
* Vraća element na zadatoj poziciji u listi.
*
* @param index indeks elementa koji treba vratiti
* @return element na zadatoj poziciji u listi
* @throws IndexOutOfBoundsException ako je indeks van granica (index < 0 || index >= size())
*/
public E get(int index) {
Objects.checkIndex(index, size); // proverava da li je indeks van granica
return elementData(index); // poziva metod elementData da bi dohvatio element
}
/**
* Vraća element na zadatoj poziciji u listi.
* Napomena: ovaj metod ne proverava da li je indeks van granica, pre poziva treba proveriti da li je indeks van granica.
*
* @param index indeks elementa koji treba vratiti
* @return element na zadatoj poziciji u listi
*/
E elementData(int index) {
return (E) elementData[index]; // eksplicitno kastovanje, pretvara Object tip u E tip
}ArrayList takođe implementira Cloneable interfejs, što pokazuje da ArrayList podržava kopiranje. ArrayList zaista interno redefiniše clone() metod klase Object.
/**
* Vraća plitku kopiju ove liste.
* (Sam elementi se ne kopiraju.)
*
* @return kopija ove liste
*/
public Object clone() {
try {
ArrayList<?> v = (ArrayList<?>) super.clone(); // poziva clone metod klase Object, dobija plitku kopiju
v.elementData = Arrays.copyOf(elementData, size); // kopira niz elementData, kreira novi niz kao kopiju
v.modCount = 0; // postavlja modCount na 0
return v; // vraća kopiju
} catch (CloneNotSupportedException e) {
// this shouldn't happen, since we are Cloneable
throw new InternalError(e);
}
}ArrayList takođe implementira Serializable interfejs, što je takođe interfejs za označavanje:
public interface Serializable {
}I unutar njega je prazno, i označava da "klase koje implementiraju ovaj interfejs podržavaju serijalizaciju". Šta znači serijalizacija? Java serijalizacija znači pretvaranje objekta u oblik niza bajtova, gde taj niz bajtova sadrži polja i metode objekta. Serijalizovani objekat se može upisati u bazu podataka, u fajl, ili se koristiti za mrežni prenos.
Pažljivi čitaoci možda će primetiti da se ključno polje elementData u ArrayList-u modifikuje pomoću transient ključne reči, čija je uloga da spreči serijalizaciju polja koje modifikuje.
Zar to nije kontradiktorno? Klasa pošto implementira Serilizable interfejs, sigurno želi da bude serijalizovana, zar ne? Onda zašto elementData, koji čuva ključne podatke, ne želi da bude serijalizovan?
Mora se početi od toga da je "ArrayList zasnovan na nizu". Svi znamo da je niz fiksne dužine, što znači da kada se niz jednom deklariše, njegova dužina (kapacitet) je fiksna i ne može se rastezati. To stvara problem: kada se niz jednom napuni, ne može mu se dodati novi element.
ArrayList ne želi da živi kao niz, želi da bude fleksibilan, pa je implementirao dinamičko proširenje. Čim pri dodavanju elementa otkrije da je kapacitet pun s == elementData.length, proširuje niz na 1,5 puta od originalnog (oldCapacity >> 1). Nakon proširenja, originalni niz se kopira na novu dodeljenu memorijsku adresu Arrays.copyOf(elementData, newCapacity).
Ovaj deo izvornog koda smo već vrlo jasno objasnili kada smo pričali o ArrayList-u, pa ćemo ovde samo ukratko proći.
Šta znači dinamičko proširenje?
Znači da stvarna veličina niza možda nikada neće biti popunjena, uvek će ostati višak praznog memorijskog prostora.
Na primer, podrazumevana veličina niza je 10, a kada se doda 11. element, dužina niza se proširuje 1,5 puta, odnosno na 15, što znači da 4 memorijska prostora ostaju neiskorišćena, zar ne?
Prilikom serijalizacije, ako se serijalizuje ceo niz, onda se serijalizuje 4 memorijska prostora više. Kada je broj uskladištenih elemenata vrlo veliki, neiskorišćen prostor je vrlo veliki, i vreme serijalizacije će biti vrlo dugo.
Zato je ArrayList doneo prijatnu i pametnu odluku — interno pruža dva privatna metoda, writeObject i readObject, da završe serijalizaciju i deserijalizaciju.
/**
* Serijalizuje stanje ove instance liste u zadati ObjectOutputStream.
* (Odnosno, čuva ovu instancu liste u tok.)
*
* @param s tok u koji se upisuje
* @throws java.io.IOException ako dođe do izuzetka prilikom upisa u tok
*/
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
s.defaultWriteObject(); // ispisuje podrazumevana polja objekta
// Write out size as capacity for behavioral compatibility with clone()
s.writeInt(size); // ispisuje size
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]); // redom ispisuje elemente iz niza elementData
}
}Iz izvornog koda writeObject metoda se vidi da koristi stvarnu veličinu ArrayList-a, size, umesto dužine niza (elementData.length) kao gornju granicu za serijalizaciju.
Ovde bi trebalo da bude aplauz! Ne za mene, nego za autore Java izvornog koda, zaista su neverovatni — mogu se opisati sa dve fraze: neumorna predanost i težnja ka savršenstvu.
666
Ovo je izvorni kod readObject metoda:
/**
* Iz zadatog ObjectInputStream-a čita stanje ove instance liste.
* (Odnosno, obnavlja ovu instancu liste iz toka.)
*
* @param s tok iz kojeg se čita stanje ove instance liste
* @throws java.io.IOException ako dođe do izuzetka prilikom čitanja toka
* @throws ClassNotFoundException ako se klasa ne pronađe prilikom čitanja toka
*/
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA; // inicijalizuje niz elementData kao prazan niz
// čita podrazumevana polja
s.defaultReadObject();
// čita kapacitet, ova vrednost se ignoriše, jer su u ArrayList-u kapacitet i dužina dva različita pojma
s.readInt();
if (size > 0) {
// dodeljuje novi niz elementData, veličine size
ensureCapacityInternal(size);
Object[] a = elementData;
// redom čita elemente iz ulaznog toka i skladišti ih u nizu
for (int i=0; i<size; i++) {
a[i] = s.readObject(); // čita objekat i skladišti ga u nizu elementData
}
}
}02,Kako je LinkedList implementiran?
LinkedList je dvostruko povezana lista koja nasleđuje AbstractSequentialList, pa se može koristiti i kao stek, red ili dvostruki red.
Pogledajmo deo izvornog koda:
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
transient int size = 0; // polje koje se ne serijalizuje, označava broj čvorova u listi
transient Node<E> first; // polje koje se ne serijalizuje, pokazuje na prvi čvor u listi
transient Node<E> last; // polje koje se ne serijalizuje, pokazuje na poslednji čvor u listi
// ...
}LinkedList interno definiše čvor Node, koji sadrži 3 dela: sadržaj elementa item, prethodnu referencu prev i sledeću referencu next. O ovome smo već pričali kada smo obrađivali LinkedList, pa ćemo preskočiti.
LinkedList takođe implementira Cloneable interfejs, što pokazuje da LinkedList podržava kopiranje.
LinkedList takođe implementira Serializable interfejs, što pokazuje da LinkedList podržava serijalizaciju. Pažljivi čitaoci su možda ponovo primetili da se ključna polja size, first i last u LinkedList-u modifikuju transient ključnom rečju — zar to opet nije kontradiktorno? Da li uopšte želi serijalizaciju ili ne?
Odgovor je da LinkedList želi da se serijalizuje na svoj način, pogledajmo njegov sopstveni writeObject() metod:
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException {
// upisuje podrazumevanu serijalizacijsku oznaku
s.defaultWriteObject();
// upisuje broj čvorova liste
s.writeInt(size);
// u ispravnom redosledu upisuje sve elemente
for (LinkedList.Node<E> x = first; x != null; x = x.next)
s.writeObject(x.item);
}Primetili ste? LinkedList prilikom serijalizacije čuva samo sadržaj elementa item, a ne čuva prethodne i sledeće reference. Tako se štedi prilično memorijskog prostora, zar ne?
Neki čitaoci će se možda zapitati: ako se čuva samo sadržaj elementa, a ne i prethodne i sledeće reference, kako onda da se izvrši deserijalizacija?
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
// čita podrazumevanu serijalizacijsku oznaku
s.defaultReadObject();
// čita broj čvorova liste
int size = s.readInt();
// u ispravnom redosledu čita sve elemente
for (int i = 0; i < size; i++)
linkLast((E)s.readObject()); // čita element i dodaje ga na kraj liste
}
void linkLast(E e) {
final LinkedList.Node<E> l = last;
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null);
last = newNode; // novi čvor postaje krajnji čvor liste
if (l == null)
first = newNode; // ako je lista prazna, novi čvor postaje prvi čvor liste
else
l.next = newNode; // inače se novi čvor povezuje na kraj liste
size++; // povećava broj čvorova
}Obratite pažnju na linkLast() metod u for petlji, on može ponovo da poveže listu, čime se obnavlja redosled liste kakav je bio pre serijalizacije. Vrlo elegantno, zar ne?
U poređenju sa ArrayList-om, LinkedList ne implementira RandomAccess interfejs, zato što memorijske adrese na kojima LinkedList čuva podatke nisu neprekidne, pa ne podržava slučajan pristup.
03,Ko je brži pri dodavanju elemenata?
Dosad smo iz više aspekata upoznali principe implementacije i osobine ArrayList-a i LinkedList-a. Zato hajde da pričamo o tome ko je brži pri dodavanju elemenata — ArrayList ili LinkedList.
1)ArrayList
Dodavanje elemenata u ArrayList ima dva slučaja: jedan je direktno dodavanje elementa na kraj niza, a drugi je umetanje elementa na zadatu poziciju.
Izvorni kod dodavanja na kraj niza (ovo smo već prošli kada smo obrađivali ArrayList, ovde ponavljamo):
public boolean add(E e) {
add(e, elementData, size);
return true;
}
private void add(E e, Object[] elementData, int s) {
if (s == elementData.length)
elementData = grow(); // proširuje niz
elementData[s] = e; // dodaje element na kraj niza
size = s + 1; // povećava broj elemenata
}Vrlo je jednostavno: prvo se proverava da li je potrebno proširenje, a zatim se putem indeksa element dodaje na kraj.
Izvorni kod umetanja na zadatu poziciju:
public void add(int index, E element) {
rangeCheckForAdd(index); // proverava da li je pozicija umetanja van granica
final int s; // trenutni broj elemenata
Object[] elementData; // niz elemenata
if ((s = size) == (elementData = this.elementData).length) // ako je niz pun, proširuje se
elementData = grow();
System.arraycopy(elementData, index,
elementData, index + 1,
s - index); // pomera elemente nakon pozicije umetanja za jedno mesto udesno
elementData[index] = element; // umeće novi element na zadatu poziciju
size = s + 1; // povećava broj elemenata
}Prvo se proverava da li je pozicija umetanja u razumnom opsegu, zatim da li je potrebno proširenje, pa se elementi nakon te pozicije kopiraju na poziciju nakon one na koju se dodaje novi element, i konačno se putem indeksa element dodaje na zadatu poziciju.
2)LinkedList
Dodavanje elemenata u LinkedList takođe ima dva slučaja: jedan je direktno dodavanje na kraj reda, a drugi je umetanje na zadatu poziciju.
Izvorni kod dodavanja na kraj reda:
public boolean add(E e) {
linkLast(e); // dodaje element na kraj liste
return true;
}
void linkLast(E e) {
final LinkedList.Node<E> l = last; // uzima krajnji čvor liste
final LinkedList.Node<E> newNode = new LinkedList.Node<>(l, e, null); // kreira novi čvor
last = newNode; // novi čvor postaje krajnji čvor liste
if (l == null)
first = newNode; // ako je lista prazna, novi čvor postaje prvi čvor liste
else
l.next = newNode; // inače se novi čvor povezuje na kraj liste
size++; // povećava broj čvorova
}Prvo se krajnji čvor last čuva u privremenoj promenljivoj l, zatim se kreira novi Node čvor i dodeljuje last-u; ako je l null, znači da je to prvo dodavanje, pa first postaje novi čvor; inače se novi čvor dodeljuje next-u prethodnog last-a.
Izvorni kod umetanja na zadatu poziciju:
public void add(int index, E element) {
checkPositionIndex(index); // proverava da li je pozicija umetanja van granica
if (index == size)
linkLast(element); // ako je pozicija umetanja kraj liste, element se dodaje na kraj
else
linkBefore(element, node(index)); // inače se element umeće ispred čvora na zadatoj poziciji
}
LinkedList.Node<E> node(int index) {
if (index < (size >> 1)) { // ako je pozicija umetanja u prvoj polovini liste, pretraga kreće od prvog čvora
LinkedList.Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else { // inače pretraga kreće od krajnjeg čvora
LinkedList.Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}
void linkBefore(E e, LinkedList.Node<E> succ) {
final LinkedList.Node<E> pred = succ.prev; // uzima prethodni čvor pozicije umetanja
final LinkedList.Node<E> newNode = new LinkedList.Node<>(pred, e, succ); // kreira novi čvor
succ.prev = newNode; // novi čvor se povezuje sa sledećim čvorom
if (pred == null)
first = newNode; // ako je prethodni čvor null, novi čvor postaje prvi čvor
else
pred.next = newNode; // inače se novi čvor povezuje sa prethodnim čvorom
size++; // povećava broj čvorova
}Prvo se proverava da li je pozicija umetanja u razumnom opsegu, zatim da li je pozicija umetanja kraj reda — ako jeste, dodaje se na kraj; inače se izvršava linkBefore() metod.
Pre izvršavanja linkBefore() metoda, poziva se node() metod da pronađe element na zadatoj poziciji, što zahteva prelazak kroz LinkedList. Ako je pozicija umetanja bliža prednjem delu, pretraga ide od početka ka kraju; inače od kraja ka početku. Drugim rečima, što je pozicija umetanja bliža sredini LinkedList-a, to više vremena oduzima prelazak.
Nakon pronalaska elementa na zadatoj poziciji (parametar succ), počinje izvršavanje linkBefore() metoda: prvo se prethodni čvor (prev) od succ čuva u privremenoj promenljivoj pred, zatim se kreira novi Node čvor (newNode), i prethodni čvor od succ se menja na newNode; ako je pred null, znači da se umeće na početak reda, pa first postaje novi čvor; inače se sledeći čvor od pred menja na newNode.
Nakon analize izvornog koda, da li vam pada na pamet: "Čini se da ArrayList pri dodavanju elemenata nije nužno manje efikasan od LinkedList-a!"
Kada su početne dužine oba iste:
- Ako se element dodaje na početak kolekcije, ArrayList bi trebalo da potroši više vremena od LinkedList-a, jer je potrebno kopirati elemente nakon početka.
Hajde da testiramo:
public class ArrayListTest {
public static void addFromHeaderTest(int num) {
ArrayList<String> list = new ArrayList<String>(num);
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
list.add(0, i + "Chenmo Wang Er");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("Vreme dodavanja elementa na početak kolekcije za ArrayList" + (timeEnd - timeStart));
}
}
/**
* @author WeChat pretraga "Chenmo Wang Er", odgovorite ključnom reči PDF
*/
public class LinkedListTest {
public static void addFromHeaderTest(int num) {
LinkedList<String> list = new LinkedList<String>();
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
list.addFirst(i + "Chenmo Wang Er");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("Vreme dodavanja elementa na početak kolekcije za LinkedList" + (timeEnd - timeStart));
}
}Kada je num 10000, izmereno vreme nakon testa je:
Vreme dodavanja elementa na početak kolekcije za ArrayList595
Vreme dodavanja elementa na početak kolekcije za LinkedList15Ovde ArrayList troši mnogo više vremena od LinkedList-a.
- Ako se element dodaje na srednju poziciju kolekcije, ArrayList bi mogao potrošiti manje vremena od LinkedList-a, jer LinkedList mora da prelazi kroz listu.
Pogledajmo test kod.
public class ArrayListTest {
public static void addFromMidTest(int num) {
ArrayList<String> list = new ArrayList<String>(num);
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
int temp = list.size();
list.add(temp / 2, i + "Chenmo Wang Er");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("Vreme dodavanja elementa na sredinu kolekcije za ArrayList" + (timeEnd - timeStart));
}
}
public class LinkedListTest {
public static void addFromMidTest(int num) {
LinkedList<String> list = new LinkedList<String>();
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
int temp = list.size();
list.add(temp / 2, i + "Chenmo Wang Er");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("Vreme dodavanja elementa na sredinu kolekcije za LinkedList" + (timeEnd - timeStart));
}
}Kada je num 10000, izmereno vreme nakon testa je:
Vreme dodavanja elementa na sredinu kolekcije za ArrayList16
Vreme dodavanja elementa na sredinu kolekcije za LinkedList114ArrayList troši mnogo manje vremena od LinkedList-a.
- Ako se element dodaje na kraj kolekcije, ArrayList bi trebalo da potroši manje vremena od LinkedList-a, jer je niz neprekidan memorijski prostor i nije potrebno kopiranje niza; dok povezana lista mora da kreira nove objekte i preuredi prethodne i sledeće reference.
Pogledajmo test kod:
public class ArrayListTest {
public static void addFromTailTest(int num) {
ArrayList<String> list = new ArrayList<String>(num);
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
list.add(i + "Chenmo Wang Er");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("Vreme dodavanja elementa na kraj kolekcije za ArrayList" + (timeEnd - timeStart));
}
}
public class LinkedListTest {
public static void addFromTailTest(int num) {
LinkedList<String> list = new LinkedList<String>();
int i = 0;
long timeStart = System.currentTimeMillis();
while (i < num) {
list.add(i + "Chenmo Wang Er");
i++;
}
long timeEnd = System.currentTimeMillis();
System.out.println("Vreme dodavanja elementa na kraj kolekcije za LinkedList" + (timeEnd - timeStart));
}
}Kada je num 10000, izmereno vreme nakon testa je:
Vreme dodavanja elementa na kraj kolekcije za ArrayList69
Vreme dodavanja elementa na kraj kolekcije za LinkedList193ArrayList troši nešto manje vremena od LinkedList-a.
Da li se ovakav zaključak ne poklapa sa očekivanjima? ArrayList pri dodavanju elemenata, ako ne uključuje proširenje, u dva slučaja (dodavanje na sredinu i na kraj) ima mnogo bolje performanse od LinkedList-a; samo pri dodavanju na početak je lošiji od LinkedList-a, zbog kopiranja niza.
Naravno, ako uključuje proširenje niza, performanse ArrayList-a nisu tako sjajne, jer i pri proširenju treba kopirati niz.
04,Ko je brži pri brisanju elemenata?
1)ArrayList
Pri brisanju elemenata iz ArrayList-a postoje dva načina: jedan je direktno brisanje elementa (remove(Object)), što prvo zahteva prelazak kroz niz da bi se pronašao indeks elementa; drugi je brisanje po indeksu (remove(int)).
Pogledajmo izvorni kod (zapravo smo i ranije objasnili, ovde ponavljamo):
public boolean remove(Object o) {
final Object[] es = elementData; // uzima elemente niza
final int size = this.size; // uzima veličinu niza
int i = 0;
found: {
if (o == null) {
for (; i < size; i++)
if (es[i] == null)
break found;
} else {
for (; i < size; i++)
if (o.equals(es[i]))
break found;
}
return false;
}
fastRemove(es, i); // poziva metod fastRemove za brzo uklanjanje elementa
return true;
}
public E remove(int index) {
Objects.checkIndex(index, size); // proverava da li je indeks van granica
final Object[] es = elementData; // uzima elemente niza
oldValue = (E) es[index]; // uzima element koji treba obrisati
fastRemove(es, index); // poziva metod fastRemove za brzo uklanjanje elementa
return oldValue; // vraća obrisani element
}Suštinski, oba metoda su ista — na kraju oba pozivaju fastRemove(Object, int) metod.
private void fastRemove(Object[] es, int i) {
final int newSize;
if ((newSize = size - 1) > i) // ako obrisani nije poslednji element
System.arraycopy(es, i + 1, es, i, newSize - i); // pomera elemente nakon obrisanog za jedno mesto unapred
es[size = newSize] = null; // poslednji element se postavlja na null, pomaže sakupljanje smeća
}Iz izvornog koda se vidi da godinje da se osim poslednjeg elementa briše, uvek je potrebno ponovo pomerati niz. Što je pozicija obrisanog elementa bliža početku, to je cena veća.
2)LinkedList
Pri brisanju elemenata iz LinkedList-a postoje četiri uobičajena načina:
remove(int), briše element na zadatoj poziciji
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}Prvo se proverava indeks, zatim se poziva node(int) metod (prelazak kroz prednju i zadnju polovinu, isto kao pri dodavanju) da pronađe čvor Node, a onda se poziva unlink(Node) da ukloni prethodne i sledeće reference čvora, i istovremeno ažurira sledeću referencu prethodnog čvora i prethodnu referencu sledećeg čvora:
E unlink(Node<E> x) {
final E element = x.item; // uzima element čvora koji se briše
final Node<E> next = x.next; // uzima sledeći čvor čvora koji se briše
final Node<E> prev = x.prev; // uzima prethodni čvor čvora koji se briše
if (prev == null) { // ako je čvor koji se briše prvi čvor
first = next; // prvi čvor se ažurira na sledeći čvor čvora koji se briše
} else {
prev.next = next; // sledeća referenca prethodnog čvora čvora koji se briše usmerava na sledeći čvor čvora koji se briše
x.prev = null; // prethodna referenca čvora koji se briše se postavlja na null, pomaže sakupljanje smeća
}
if (next == null) { // ako je čvor koji se briše poslednji čvor
last = prev; // poslednji čvor se ažurira na prethodni čvor čvora koji se briše
} else {
next.prev = prev; // prethodna referenca sledećeg čvora čvora koji se briše usmerava na prethodni čvor čvora koji se briše
x.next = null; // sledeća referenca čvora koji se briše se postavlja na null, pomaže sakupljanje smeća
}
x.item = null; // element čvora koji se briše se postavlja na null, pomaže sakupljanje smeća
size--; // dužina liste se smanjuje za jedan
return element; // vraća obrisani element
}remove(Object), direktno briše element
public boolean remove(Object o) {
if (o == null) { // ako je element koji se briše null
for (LinkedList.Node<E> x = first; x != null; x = x.next) {
if (x.item == null) { // ako je pronađen čvor koji se briše
unlink(x); // poziva metod unlink za brisanje zadatog čvora
return true; // vraća uspeh brisanja
}
}
} else {
for (LinkedList.Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) { // ako je pronađen čvor koji se briše
unlink(x); // poziva metod unlink za brisanje zadatog čvora
return true; // vraća uspeh brisanja
}
}
}
return false; // čvor koji se briše nije pronađen, vraća neuspeh brisanja
}I ovde se prvo prelazi kroz prednju i zadnju polovinu, a nakon pronalaska elementa za brisanje poziva se unlink(Node).
removeFirst(), briše prvi čvor
public E removeFirst() {
final LinkedList.Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
private E unlinkFirst(LinkedList.Node<E> f) {
final E element = f.item; // uzima element čvora koji se briše
final LinkedList.Node<E> next = f.next; // uzima sledeći čvor čvora koji se briše
f.item = null; // element čvora koji se briše se postavlja na null, pomaže sakupljanje smeća
f.next = null; // sledeća referenca čvora koji se briše se postavlja na null, pomaže sakupljanje smeća
first = next; // prvi čvor se ažurira na sledeći čvor čvora koji se briše
if (next == null) // ako je lista već prazna
last = null; // poslednji čvor se postavlja na null
else
next.prev = null; // prethodna referenca sledećeg čvora čvora koji se briše se postavlja na null, pomaže sakupljanje smeća
size--; // dužina liste se smanjuje za jedan
return element; // vraća obrisani element
}Brisanje prvog čvora ne zahteva prelazak kroz listu, samo je potrebno drugi čvor ažurirati kao prvi čvor.
removeLast(), briše poslednji čvor
Brisanje poslednjeg čvora je slično brisanju prvog čvora, samo je potrebno pretposlednji čvor ažurirati kao poslednji čvor.
Vidi se da je LinkedList vrlo efikasan pri brisanju elemenata bližih početku i bližih kraju, ali ako se briše element na sredini, efikasnost je niža.
Ovde nećemo raditi test koda, ako vas zanima, možete sami probati, rezultati su u skladu sa dodavanjem elemenata:
- Pri brisanju elementa s početka kolekcije, ArrayList troši mnogo više vremena od LinkedList-a;
- Pri brisanju elementa sa sredine kolekcije, ArrayList troši mnogo manje vremena od LinkedList-a;
- Pri brisanju elementa s kraja kolekcije, ArrayList troši malo manje vremena od LinkedList-a.
Moji lokalni rezultati merenja su sledeći, možete ih uzeti kao referencu:
Vreme brisanja elementa s početka kolekcije za ArrayList380
Vreme brisanja elementa s početka kolekcije za LinkedList4
Vreme brisanja elementa sa sredine kolekcije za ArrayList381
Vreme brisanja elementa sa sredine kolekcije za LinkedList5922
Vreme brisanja elementa s kraja kolekcije za ArrayList8
Vreme brisanja elementa s kraja kolekcije za LinkedList1205,Ko je brži pri prelasku kroz elemente?
1)ArrayList
Pronalaženje nekog elementa u ArrayList-u se obično radi na dva načina:
get(int), pronalazi element po indeksu
public E get(int index) {
Objects.checkIndex(index, size);
return elementData(index);
}Pošto je ArrayList zasnovan na nizu, pronalaženje elementa po indeksu je veoma brzo — odmah u jednom koraku.
indexOf(Object), pronalazi indeks po elementu
public int indexOf(Object o) {
return indexOfRange(o, 0, size);
}
int indexOfRange(Object o, int start, int end) {
Object[] es = elementData; // uzima niz elemenata iz ArrayList-a
if (o == null) { // ako je element koji se traži null
for (int i = start; i < end; i++) {
if (es[i] == null) { // ako je pronađen traženi element
return i; // vraća indeks elementa u ArrayList-u
}
}
} else {
for (int i = start; i < end; i++) {
if (o.equals(es[i])) { // ako je pronađen traženi element
return i; // vraća indeks elementa u ArrayList-u
}
}
}
return -1; // traženi element nije pronađen, vraća -1
}Pronalaženje indeksa po elementu zahteva prelazak kroz ceo niz, redom od početka do kraja.
2)LinkedList
Pronalaženje nekog elementa u LinkedList-u se obično takođe radi na dva načina:
get(int), pronalazi element na zadatoj poziciji
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}S obzirom na to da je potrebno pozvati node(int) metod, to znači da je potrebno preći kroz prednju i zadnju polovinu.
indexOf(Object), pronalazi poziciju elementa
public int indexOf(Object o) {
int index = 0; // inicijalizuje indeks na 0
if (o == null) { // ako je element koji se traži null
for (LinkedList.Node<E> x = first; x != null; x = x.next) { // prelazi kroz listu od prvog čvora
if (x.item == null) // ako je pronađen traženi element
return index; // vraća indeks elementa u LinkedList-u
index++; // indeks se povećava za jedan
}
} else {
for (LinkedList.Node<E> x = first; x != null; x = x.next) { // prelazi kroz listu od prvog čvora
if (o.equals(x.item)) // ako je pronađen traženi element
return index; // vraća indeks elementa u LinkedList-u
index++; // indeks se povećava za jedan
}
}
return -1; // traženi element nije pronađen, vraća -1
}Potrebno je preći kroz celu listu, slično kao indexOf() kod ArrayList-a.
Prilikom prelaska kroz kolekciju obično postoje dva pristupa: jedan je upotreba for petlje, drugi je upotreba iteratora (Iterator).
Ako se koristi for petlja, jasno je da će LinkedList pri get-u imati vrlo loše performanse, jer pri svakoj spoljašnjoj for petlji mora jednom izvršiti node(int) metod za prelazak kroz prednju i zadnju polovinu.
LinkedList.Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) { // ako se traži element u prvoj polovini liste
LinkedList.Node<E> x = first; // prelazi kroz listu od prvog čvora
for (int i = 0; i < index; i++) // petljom pronalazi element
x = x.next;
return x; // vraća čvor traženog elementa
} else { // ako se traži element u drugoj polovini liste
LinkedList.Node<E> x = last; // prelazi kroz listu od krajnjeg čvora
for (int i = size - 1; i > index; i--) // petljom pronalazi element
x = x.prev;
return x; // vraća čvor traženog elementa
}
}A šta ako se koristi iterator?
LinkedList<String> list = new LinkedList<String>();
for (Iterator<String> it = list.iterator(); it.hasNext();) {
it.next();
}Iterator će pozvati node(int) samo jednom, i to pri izvršavanju list.iterator(): prvo se poziva iterator() metod klase AbstractSequentialList, zatim listIterator() metod klase AbstractList, pa listIterator(int) metod klase LinkedList, kao što je prikazano na slici.
Na kraju se vraća objekat unutrašnje privatne klase ListItr iz LinkedList-a:
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index); // proverava da li je indeks u važećem opsegu
return new LinkedList.ListItr(index); // kreira novi ListItr objekat i vraća ga
}
private class ListItr implements ListIterator<E> {
private LinkedList.Node<E> lastReturned; // prethodni vraćeni čvor
private LinkedList.Node<E> next; // sledeći čvor
private int nextIndex; // indeks sledećeg čvora
private int expectedModCount = modCount; // broj izmena liste
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index); // ako je index jednako size, next je null, inače vraća node(index)
nextIndex = index; // postavlja nextIndex na index
}
public boolean hasNext() {
return nextIndex < size; // ako je indeks sledećeg čvora manji od dužine liste, vraća true, inače false
}
public E next() {
checkForComodification(); // proverava da li je lista izmenjena
if (!hasNext()) // ako nema sledećeg čvora, baca NoSuchElementException izuzetak
throw new NoSuchElementException();
lastReturned = next; // sledeći čvor se postavlja kao prethodni vraćeni čvor
next = next.next; // sledeći čvor se postavlja na sledeći čvor trenutnog čvora
nextIndex++; // indeks sledećeg čvora se povećava za 1
return lastReturned.item; // vraća element prethodno vraćenog čvora
}
}Pri izvršavanju konstruktora ListItr-a poziva se jednom node(int) metod, koji vraća prvi čvor. Nakon toga, iterator izvršava hasNext() da proveri da li postoji sledeći, i next() metod za sledeći čvor.
Otuda se može izvući zaključak: Kada prelazite kroz LinkedList, nikako ne koristite for petlju, koristite iterator.
Drugim rečima, pri prelasku pomoću for petlje, ArrayList troši znatno manje vremena od LinkedList-a; pri prelasku pomoću iteratora, performanse oba su približno iste.
06,Scenariji upotrebe oba
Kada je potrebno često slučajno pristupati elementima, npr. čitanje velike količine podataka i obrada, ili scenariji u kojima je potrebno sortirati ili pretraživati podatke, može se koristiti ArrayList. Na primer, sistem upravljanja studentima u kojem je potrebno sortirati ili pretraživati listu studenata, može koristiti ArrayList za čuvanje podataka o studentima, radi brzog pristupa i obrade.
Kada je potrebno često dodavati i brisati elemente, npr. implementacija reda ili steka, ili scenariji u kojima je potrebno umetati ili brisati elemente na sredini, može se koristiti LinkedList. Na primer, sistem razgovora u realnom vremenu u kojem je potrebno implementirati red poruka, može koristiti LinkedList za čuvanje poruka, radi brzog umetanja i brisanja poruka.
U nekim posebnim scenarijima možda je potrebno istovremeno podržati i slučajan pristup i umetanje/brisanje. Na primer, sistem za onlajn igre u kojem je potrebno implementirati listu igrača, podržati brzo pretraživanje i prelazak kroz igrače, ali i pridruživanje i napuštanje igrača. U tom slučaju se može koristiti kombinacija LinkedList-a i ArrayList-a — npr. LinkedList za čuvanje igrača radi brzog umetanja i brisanja igrača, a ArrayList za čuvanje liste igrača radi brzog pretraživanja i prelaska kroz igrače.
"Dobro, Erge."