Oversikt

En lenket liste er en datastruktur der hvert element (node) inneholder data og en referanse (peker) til neste element. I motsetning til arrays har lenkede lister dynamisk storrelse -- du trenger ikke bestemme storrelsen pa forhand, og listen vokser og krymper etter behov. Ulempen er at tilfeldig aksess ("gi meg element nr. 5") er treg: du ma traversere fra starten, noe som tar O(n) tid.

Lenkede lister er den viktigste datastrukturen pa IN1010-eksamen. De dukker opp i nesten alle oppgaver: prioritetskoer (V2018, V2021), kullister (V2019), passasjerlister (V2018), og mange andre sammenhenger. Du ma kunne implementere dem fra bunnen av, uten bruk av Java-bibliotekets samlinger.

Enveis vs. toveis lenket liste

I en enveis lenket liste har hver node bare en neste-peker. Du kan bare traversere fremover, fra forste til siste. I en toveis lenket liste har hver node bade neste og forrige, noe som muliggjor traversering i begge retninger. Toveis lister er mer komplekse a implementere fordi du ma oppdatere flere pekere ved innsetting og sletting.

Pa eksamen V2021 ble det eksplisitt bedt om en toveis lenket liste for prioritetskoen (PrioKo), der innsetting skjer bakfra for a finne riktig posisjon effektivt. Oppgaveteksten spesifiserte at Aktivitet-klassen skulle ha to pekere: en til objektet med lavere tid og en til objektet med hoyere tid. Pa V2018 og V2019 holdt det med enveis lenket liste.

Sortert innsetting

I en sortert lenket liste ma du finne riktig posisjon for det nye elementet. Algoritmen traverserer listen til den finner en node med storre verdi (eller nar slutten), og setter inn foran denne noden. Du ma handtere tre spesialtilfeller:

Tom liste: det nye elementet blir bade forste og siste.
Innsetting forst: ny verdi er mindre enn alle eksisterende.
Innsetting i midten eller sist: traverser til riktig posisjon.

For en toveis liste ma du i tillegg oppdatere forrige-pekeren for noden etter innsettingspunktet, samt siste-referansen hvis du setter inn sist.

Prioritetsko som lenket liste

Pa IN1010-eksamen er prioritetskoen nesten alltid implementert som en sortert lenket liste. Elementet med hoyest prioritet (lavest tall) ligger forst, sa taUt()/hentUt() er O(1) -- du bare fjerner forste element. Innsetting er O(n) i verste fall fordi du ma lete gjennom listen for a finne riktig posisjon. Denne avveiningen (rask uttak, tregere innsetting) er typisk for denne implementasjonen.

Indre klasser for noder

Det er vanlig a definere Node-klassen som en privat indre klasse (inner class) inne i listeklassen. Dette holder Node skjult for omverdenen og gir den tilgang til den ytre klassens felt. Alternativt kan node-funksjonaliteten ligge direkte i dataelementene (som i V2021 der Aktivitet selv hadde neste/forrige-pekere, og i V2019 der Hund hadde en neste-peker for lenket liste i Kull).

Teknikk: traversering med to pekere

Nar du traverserer en lenket liste for a finne riktig innsettingsposisjon, trenger du ofte to pekere: en for naavaerende node og en for forrige node. Alternativt kan du sjekke p.neste i lokken: while (p.neste != null && p.neste.compareTo(ny) < 0) { p = p.neste; }. Etter lokken setter du inn etter p. Denne teknikken ungar behovet for en separat forrige-peker og er enklere a implementere korrekt.

For toveis lister trenger du ikke denne teknikken fordi du alltid har tilgang til forrige node via forrige-pekeren.

Kodeeksempel 1: Toveis prioritetsko (V2021-stil)

class PrioKo {
    private Aktivitet forste;
    private Aktivitet siste;

    void settInn(Aktivitet a) {
        if (forste == null) {
            // Tom ko: a blir bade forste og siste
            forste = a;
            siste = a;
            a.neste = null;
            a.forrige = null;
            return;
        }
        // Let bakfra (fra siste) for a finne riktig plass
        Aktivitet p = siste;
        while (p != null && a.compareTo(p) < 0) {
            p = p.forrige;
        }
        if (p == null) {
            // Sett inn forst (a har lavest tid)
            a.neste = forste;
            a.forrige = null;
            forste.forrige = a;
            forste = a;
        } else {
            // Sett inn etter p
            a.neste = p.neste;
            a.forrige = p;
            if (p.neste != null) p.neste.forrige = a;
            else siste = a;
            p.neste = a;
        }
    }

    Aktivitet hentUt() {
        if (forste == null) return null;
        Aktivitet ut = forste;
        forste = forste.neste;
        if (forste != null) forste.forrige = null;
        else siste = null;
        ut.neste = null;
        ut.forrige = null;
        return ut;
    }
}

Kodeeksempel 2: Sortert enveis liste (V2019-stil)

class KullListe extends Kull implements Iterable<Hund> {
    // Hundene lagres som lenket liste via neste-peker i Hund
    // Listen er sortert: yngste forst (for iteratoren)

    void settInn(Hund ny) {
        if (forsteHund == null
            || ny.compareTo(forsteHund) < 0) {
            // Sett inn forst
            ny.neste = forsteHund;
            forsteHund = ny;
        } else {
            // Finn riktig posisjon
            Hund p = forsteHund;
            while (p.neste != null
                   && p.neste.compareTo(ny) < 0) {
                p = p.neste;
            }
            ny.neste = p.neste;
            p.neste = ny;
        }
    }
}

Studieguide: Lenkede lister

Studieguide: Lenkede lister