Preskoči na glavni sadržaj

LinkedList se žali: čak me i otac ne prihvata!

Chenmo Wang ErJava jezgroOkvir kolekcija (kontejneri)3017 reči10 minuta

Ovaj članak ima drugačiji izrazajni stil — uživajmo zajedno u njemu.

Zdravo svima, ja sam LinkedList; sa ArrayList sam iz iste škole, ali vežbamo potpuno različite unutrašnje veštine. Stariji drug vežba dinamički niz, a ja vežbam povezanu listu.

Postaviću vam jedno pitanje — da li znate zašto vežbam unutrašnju veštinu povezane liste?

Uzmimo primer: zamislite da na raspolaganju imate gomilu računa kojima morate da upravljate — možda jedan, a možda i sto miliona.

Šta činiti?

Da zauzmete veliki niz od 10 GB i čekate? A šta ako računa bude samo 100?

Da zauzmete niz podrazumevane veličine koji se širi kako podaci rastu? Imajte na umu da proširenje zahteva ponovno kopiranje niza, što jako puno vremena.

Ključni problem niza je sledeći: ako sada imate 5 miliona računa i želite da obrišete jedan iz sredine, morate da pomerite 2,5 miliona računa za jedno mesto unapred.

U takvim situacijama moj stariji drug gotovo gubi živce i jako mu je teško. Učitelj nije mogao da gleda kako drug tako pati, pa od dana kad sam ušao u školu primorao me je da vežbam unutrašnju veštinu povezane liste. U početku nisam razumeo; plašio sam se da učitelj favorizuje druga i da mi ne prenese najsnažniju veštinu škole.

Sve dok jednog dana nisam svojim očima video kako moj drug jedva nije izgubio razum pomerajući podatke — tek tada sam shvatio dobrotu učiteljeve namere. Od tada sam marljivo vežbao unutrašnju veštinu „povezane liste” i postigao zapažen napredak; i učitelj i drug su hvalili da imam dara.

Unutrašnja veština povezane liste grubo se deli na tri nivoa:

  • Prvi nivo se zove „jednostruko povezana lista” — imam samo jedan pokazivač unazad, koji pokazuje na sledeći podatak;
  • Drugi nivo se zove „dvostruko povezana lista” — imam dva pokazivača: pokazivač unapred pokazuje na sledeći podatak, a pokazivač unazad na prethodni podatak.
  • Treći nivo se zove „binarno stablo” — uklanja se pokazivač unapred i zamenjuje levim i desnim pokazivačem.

Ali moja moć još uvek ne doseže treći nivo, mada učitelj kaže da imam potencijala i da je samo pitanje vremena kada ću savladati tu veštinu. Tužno je jedino što me otac i dalje ne prihvata.

Josh Bloch je autor Java okvira kolekcija
Josh Bloch je autor Java okvira kolekcija

01. Unutrašnja veština LinkedList

Dobro, nakon ovakvog ispovedanja vi me verovatno već dobro poznajete. Sada ću vam pokazati svoju unutrašnju veštinu.

Moja unutrašnja veština uglavnom je privatna statička unutrašnja klasa koja se zove Node, odnosno čvor.

/**
 * Klasa čvora u povezanoj listi.
 */
private static class Node<E> {
    E item; // element koji se čuva u čvoru
    Node<E> next; // pokazivač na sledeći čvor
    Node<E> prev; // pokazivač na prethodni čvor

    /**
     * Konstruiše novi čvor.
     *
     * @param prev prethodni čvor
     * @param element element koji se čuva u čvoru
     * @param next sledeći čvor
     */
    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element; // čuva element
        this.next = next; // postavlja sledeći čvor
        this.prev = prev; // postavlja prethodni čvor
    }
}

Sastoji se iz tri dela:

  • element u čvoru
  • sledeći čvor
  • prethodni čvor

Nacrtaću vam sliku da to prikažem.

  • Za prvi čvor prev je null;
  • Za poslednji čvor next je null;
  • Za sve ostale čvorove prev pokazuje na prethodni, a next na sledeći.

Moja unutrašnja veština je toliko jednostavna da sam je odavno naučio napamet. Ali učitelj mi je naložio da svakog jutra kada se probudim i svake večeri pre spavanja moram je u sebi da ponovim. Iako mi je to nekako dosadno, uvek bespogovorno slušam učiteljeve pouke.

02. Potezi LinkedList

Kao i moj stariji drug ArrayList, i moji potezi se svode na četiri kategorije: „dodavanje, brisanje, izmena, pretraga”. Pre toga moramo da izvršimo inicijalizaciju.

LinkedList<String> list = new LinkedList();

Stariji drug pri inicijalizaciji može da zada veličinu, ali i da je ne zada, pa da se prvo proširenje dogodi pri dodavanju prvog elementa. Ja nemam veličinu — dokle god ima memorije, mogu da rastem bez granica.

1) Potez jedan: dodavanje

Možete pozvati metod add da dodate element:

list.add("Chenmo Wang Er");
list.add("Chenmo Wang San");
list.add("Chenmo Wang Si");

Metod add interno zapravo poziva metod linkLast:

/**
 * Dodaje zadati element na kraj liste.
 *
 * @param e element koji se dodaje u listu
 * @return uvek vraća true (prema specifikaciji Java okvira kolekcija)
 */
public boolean add(E e) {
    linkLast(e); // dodaje element na kraj liste
    return true; // dodavanje uspelo, vraća true
}

linkLast, kako mu i ime kaže, dodaje element na kraj povezane liste:

/**
 * Dodaje zadati element na kraj liste.
 *
 * @param e element koji se dodaje u listu
 */
void linkLast(E e) {
    final Node<E> l = last; // dohvata poslednji čvor liste
    final Node<E> newNode = new Node<>(l, e, null); // kreira novi čvor i postavlja ga kao poslednji čvor liste
    last = newNode; // postavlja novi čvor kao poslednji čvor liste
    if (l == null) // ako je lista prazna, novi čvor se postavlja kao prvi čvor
        first = newNode;
    else
        l.next = newNode; // inače se novi čvor povezuje na kraj liste
    size++; // povećava broj elemenata liste
}
  • Pri dodavanju prvog elementa i first i last su null.
  • Zatim se kreira novi čvor newNode čiji su i prev i next null.
  • Zatim se i last i first postavljaju na newNode.

U ovom trenutku to se još uvek ne može nazvati povezanom listom, jer su veze sa prethodnim i sledećim čvorom prekinute.

  • Pri dodavanju drugog elementa i first i last pokazuju na prvi čvor.
  • Zatim se kreira novi čvor newNode čiji prev pokazuje na prvi čvor, a next je null.
  • Zatim se next prvog čvora postavlja na newNode.

Lista u ovom trenutku još uvek nije potpuna.

  • Pri dodavanju trećeg elementa first pokazuje na prvi čvor, a last pokazuje na poslednji čvor.
  • Zatim se kreira novi čvor newNode čiji prev pokazuje na drugi čvor, a next je null.
  • Zatim se next drugog čvora postavlja na newNode.

Lista je sada potpuna.

Ovaj moj potez dodavanja može se preinačiti u još dve verzije:

  • Metod addFirst() dodaje element na prvo mesto;
  • Metod addLast() dodaje element na kraj.

addFirst interno zapravo poziva linkFirst:

/**
 * Dodaje zadati element na početak liste.
 *
 * @param e element koji se dodaje u listu
 */
public void addFirst(E e) {
    linkFirst(e); // dodaje element na početak liste
}

linkFirst postavlja novi čvor kao first i ažurira next novog first-a na prethodni first.

/**
 * Dodaje zadati element na početak liste.
 *
 * @param e element koji se dodaje u listu
 */
private void linkFirst(E e) {
    final Node<E> f = first; // dohvata prvi čvor liste
    final Node<E> newNode = new Node<>(null, e, f); // kreira novi čvor i postavlja ga kao prvi čvor liste
    first = newNode; // postavlja novi čvor kao prvi čvor liste
    if (f == null) // ako je lista prazna, novi čvor se postavlja i kao poslednji čvor
        last = newNode;
    else
        f.prev = newNode; // inače se novi čvor povezuje na početak liste
    size++; // povećava broj elemenata liste
}

Jezgro addLast-a je zapravo slično addFirst-u; interno poziva metod linkLast koji smo već analizirali.

/**
 * Dodaje zadati element na kraj liste.
 *
 * @param e element koji se dodaje u listu
 * @return uvek vraća true (prema specifikaciji Java okvira kolekcija)
 */
public boolean addLast(E e) {
    linkLast(e); // dodaje element na kraj liste
    return true; // dodavanje uspelo, vraća true
}

2) Potez dva: brisanje

Imam prilično puno poteza brisanja:

  • remove(): briše prvi čvor
  • remove(int): briše čvor na zadatoj poziciji
  • remove(Object): briše čvor sa zadatim elementom
  • removeFirst(): briše prvi čvor
  • removeLast(): briše poslednji čvor

remove() interno poziva removeFirst(), pa ta dva poteza imaju isto dejstvo.

remove(int) interno zapravo poziva metod unlink.

/**
 * Briše element sa zadate pozicije.
 *
 * @param index indeks elementa koji se briše
 * @return element koji je obrisan iz liste
 * @throws IndexOutOfBoundsException ako je indeks izvan opsega (index &lt; 0 || index &gt;= size())
 */
public E remove(int index) {
    checkElementIndex(index); // proverava da li je indeks izvan opsega
    return unlink(node(index)); // briše čvor na zadatoj poziciji i vraća njegov element
}

Metod unlink je zapravo lako razumljiv — ažurira next i prev trenutnog čvora, a zatim postavlja element trenutnog čvora na null.

/**
 * Briše zadati čvor iz povezane liste.
 *
 * @param x čvor koji se briše
 * @return element čvora koji je obrisan iz povezane liste
 */
E unlink(Node<E> x) {
    final E element = x.item; // dohvata element čvora koji se briše
    final Node<E> next = x.next; // dohvata sledeći čvor čvora koji se briše
    final Node<E> prev = x.prev; // dohvata prethodni čvor čvora koji se briše

    if (prev == null) { // ako je čvor koji se briše prvi čvor
        first = next; // postavlja sledeći čvor kao prvi čvor liste
    } else {
        prev.next = next; // prethodni čvor čvora koji se briše pokazuje na njegov sledeći čvor
        x.prev = null; // prethodni čvor čvora koji se briše postavlja na null
    }

    if (next == null) { // ako je čvor koji se briše poslednji čvor
        last = prev; // postavlja prethodni čvor kao poslednji čvor liste
    } else {
        next.prev = prev; // sledeći čvor čvora koji se briše pokazuje na njegov prethodni čvor
        x.next = null; // sledeći čvor čvora koji se briše postavlja na null
    }

    x.item = null; // element čvora koji se briše postavlja na null
    size--; // smanjuje broj elemenata liste
    return element; // vraća element obrisanog čvora
}

I remove(Object) interno poziva metod unlink, ali pre toga mora da pronađe čvor u kojem se nalazi element:

/**
 * Briše zadati element iz povezane liste.
 *
 * @param o element koji se briše iz povezane liste
 * @return vraća true ako povezana lista sadrži zadati element; inače vraća false
 */
public boolean remove(Object o) {
    if (o == null) { // ako element koji se briše nije null
        for (Node<E> x = first; x != null; x = x.next) { // obilazi povezanu listu
            if (x.item == null) { // ako je element čvora null
                unlink(x); // briše čvor
                return true; // vraća true što znači da je brisanje uspelo
            }
        }
    } else { // ako element koji se briše nije null
        for (Node<E> x = first; x != null; x = x.next) { // obilazi povezanu listu
            if (o.equals(x.item)) { // ako element čvora odgovara elementu koji se briše
                unlink(x); // briše čvor
                return true; // vraća true što znači da je brisanje uspelo
            }
        }
    }
    return false; // ako povezana lista ne sadrži element koji se briše, vraća false što znači da brisanje nije uspelo
}

Kada je element null, mora se koristiti == za proveru; kada element nije null, koristi se equals.

removeFirst interno poziva metod unlinkFirst:

/**
 * Briše prvi element iz povezane liste i vraća ga.
 * Ako je povezana lista prazna, baca NoSuchElementException.
 *
 * @return prvi element obrisan iz povezane liste
 * @throws NoSuchElementException ako je povezana lista prazna
 */
public E removeFirst() {
    final Node<E> f = first; // dohvata prvi čvor liste
    if (f == null) // ako je lista prazna
        throw new NoSuchElementException(); // baca NoSuchElementException
    return unlinkFirst(f); // poziva metod unlinkFirst koji briše prvi čvor i vraća njegov element
}

unlinkFirst briše sve tragove prvog čvora i pritom postavlja prev sledećeg čvora na null.

/**
 * Briše prvi čvor u povezanoj listi i vraća njegov element.
 *
 * @param f prvi čvor koji se briše
 * @return element obrisanog čvora
 */
private E unlinkFirst(Node<E> f) {
    final E element = f.item; // dohvata element čvora koji se briše
    final Node<E> next = f.next; // dohvata sledeći čvor čvora koji se briše
    f.item = null; // element čvora koji se briše postavlja na null
    f.next = null; // sledeći čvor čvora koji se briše postavlja na null
    first = next; // sledeći čvor čvora koji se briše postavlja kao prvi čvor liste
    if (next == null) // ako lista ima samo jedan čvor
        last = null; // poslednji čvor liste se postavlja na null
    else
        next.prev = null; // prethodni čvor sledećeg čvora čvora koji se briše postavlja na null
    size--; // smanjuje veličinu liste
    return element; // vraća element obrisanog čvora
}

3) Potez tri: izmena

Možete pozvati metod set() da ažurirate element:

list.set(0, "Chenmo Wang Wu");

Pogledajmo metod set():

/**
 * Zamenjuje element na zadatoj poziciji u povezanoj listi zadatim elementom i vraća prethodni element.
 *
 * @param index pozicija elementa koji se zamenjuje (počinje od 0)
 * @param element element koji se umeće
 * @return element pre zamene
 * @throws IndexOutOfBoundsException ako je indeks izvan opsega (index < 0 || index >= size())
 */
public E set(int index, E element) {
    checkElementIndex(index); // proverava da li je indeks izvan opsega
    Node<E> x = node(index); // dohvata čvor koji se zamenjuje
    E oldVal = x.item; // dohvata element čvora koji se zamenjuje
    x.item = element; // postavlja element čvora koji se zamenjuje na zadati element
    return oldVal; // vraća element pre zamene
}

Pogledajmo metod node:

/**
 * Dohvata čvor na zadatoj poziciji u povezanoj listi.
 *
 * @param index pozicija čvora (počinje od 0)
 * @return čvor na zadatoj poziciji
 * @throws IndexOutOfBoundsException ako je indeks izvan opsega (index < 0 || index >= size())
 */
Node<E> node(int index) {
    if (index < (size >> 1)) { // ako je indeks u prvoj polovini liste
        Node<E> x = first;
        for (int i = 0; i < index; i++) // obilazi listu unapred od prvog čvora do čvora na zadatoj poziciji
            x = x.next;
        return x; // vraća čvor na zadatoj poziciji
    } else { // ako je indeks u drugoj polovini liste
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) // obilazi listu unazad od poslednjeg čvora do čvora na zadatoj poziciji
            x = x.prev;
        return x; // vraća čvor na zadatoj poziciji
    }
}

size >> 1: pomeranje udesno za jedno mesto, ekvivalentno deljenju sa 2. Za računar je pomeranje efikasnije od deljenja, jer se podaci interno skladište u binarnom obliku.

Drugim rečima, metod node vrši preliminarnu procenu indeksa: ako je bliže prvoj polovini, obilazi se od indeksa 0; ako je bliže drugoj polovini, obilazi se od kraja, čime se povećava efikasnost — najviše za polovinu.

Kada se pronađe čvor sa zadatim indeksom, jednostavno se element tog čvora zameni novim — prev i next ne treba da se menjaju.

4) Potez četiri: pretraga

Ovaj moj potez pretrage može se podeliti u dve vrste:

  • indexOf(Object): pronalazi poziciju na kojoj se nalazi neki element
  • get(int): pronalazi element na nekoj poziciji

Pogledajmo izvorni kod metoda indexOf.

/**
 * Vraća poziciju prvog pojavljivanja zadatog elementa u povezanoj listi; ako element ne postoji, vraća -1.
 *
 * @param o element koji se traži
 * @return pozicija prvog pojavljivanja zadatog elementa; ako element ne postoji, vraća -1
 */
public int indexOf(Object o) {
    int index = 0; // inicijalizuje indeks na 0
    if (o == null) { // ako je element koji se traži null
        for (Node<E> x = first; x != null; x = x.next) { // obilazi povezanu listu unapred od prvog čvora
            if (x.item == null) // ako je pronađen traženi element
                return index; // vraća indeks tog elementa
            index++; // uvećava indeks za 1
        }
    } else { // ako element koji se traži nije null
        for (Node<E> x = first; x != null; x = x.next) { // obilazi povezanu listu unapred od prvog čvora
            if (o.equals(x.item)) // ako je pronađen traženi element
                return index; // vraća indeks tog elementa
            index++; // uvećava indeks za 1
        }
    }
    return -1; // ako traženi element nije pronađen, vraća -1
}

Jezgro metoda get je zapravo ponovo metod node, koji je već objašnjen, pa ga ovde preskačemo.

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

U stvari, potez pretrage može se preinačiti i u neke druge metode, na primer:

  • Metod getFirst() dohvata prvi element;
  • Metod getLast() dohvata poslednji element;
  • Metodi poll() i pollFirst() brišu i vraćaju prvi element (iako im se imena razlikuju, tela metoda su potpuno ista);
  • Metod pollLast() briše i vraća poslednji element;
  • Metod peekFirst() vraća, a ne briše, prvi element.

03. Izazovi LinkedList

Iskreno, ne volim mnogo da me poredi sa starijim drugom ArrayList, jer vežbamo različite unutrašnje veštine i nema ko kome nadmoćniji.

Iako me stariji drug često zove mlađim drugom, među nama je zapravo prilično skladno. Ali znam da u očima drugih učenici iz iste škole uvek moraju da se takmiče.

Na primer, vremenska složenost naših operacija dodavanja, brisanja, izmene i pretrage.

Možda je to sudbina — od dana kada sam ušao u školu, ta rasprava nikada nije prestala.

Kako god drugi gledali na nas, u mojim očima je stariji drug uvek prvi; poštujem ga, a i on želi da me zaštiti.

Najbolje tek dolazi, sačekajte i videćete.

Ovde ću samo ukratko pomenuti, kao uvod u dublju raspravu.

Zamislite da igrate igru u kojoj postoji inventar predmeta i da u njega stalno dodajete i brišete predmete. Ako koristite mog starijeg druga ArrayList, pri svakom dodavanju ili brisanju predmeta potrebno je pomeriti preostale predmete unapred ili unazad, što jako puno vremena oduzima. Ako pak koristite mene, LinkedList, dovoljno je novi predmet umetnuti na zadatu poziciju u povezanoj listi ili obrisati predmet iz liste, čime se inventar brzo ažurira.

Pored inventara u igrama, ja LinkedList mogu se koristiti i za implementaciju algoritma izbacivanja LRU (Least Recently Used) keša. Algoritam izbacivanja LRU keša je često korišćena strategija; osnovna ideja je da kada prostor u kešu ponestane, prvo se izbacuju podaci iz keša koji su najređe korišćeni. Pri implementaciji algoritma izbacivanja LRU keša možete koristiti mene, LinkedList, za skladištenje podataka keša — pri svakom pristupu podacima keša taj podatak se uklanja iz povezane liste i premešta na njen početak, tako da je na kraju liste onaj podatak iz keša koji je najređe korišćen. Kada prostor u kešu ponestane, dovoljno je izbaciti podatak sa kraja povezane liste.

Ukratko, svako ima svoje vrline — idemo dalje i cenimo ono što imamo.

04. Primena LinkedList

Ako želite da sa mnom malo vežbate, preporučujem da pokušate da rešite LeetCode zadatke 002. Sabiranje dva broja i 019. Brisanje N-tog čvora iz povezane liste; linkove ka rešenjima sam ostavio na tehnološkom portalu: