Den største enkeltdelen på eksamen

Oppgave 3 er beholderklassen, og den er verdt 20 til 40 poeng av 100 — mer enn noen annen oppgave. Formuleringen går igjen nesten ordrett: «Et tog er en dobbeltlenket liste av Skinnegående-objekter, og du skal bruke instansvariablene i disse objektene til å lage denne listen.» Legg merke til den siste halvdelen. Sensorveiledningen sier det utvetydig: «Det skal ikke brukes Node-objekter.» Pekerne ligger i selve dataobjektene. Du får heller ikke bruke java.util.LinkedList — bare java.lang, pluss Iterator/Iterable og NoSuchElementException.

Beholderen

Beholderklassen inneholder ikke annet enn en peker til første element (og til siste, hvis lista er dobbeltlenket). Det er hele datastrukturen.

class Tog implements Iterable<Skinnegaende> {
    Skinnegaende forste;
    Skinnegaende siste;

    Tog() { forste = null; siste = null; }   // konstruktøren kan være tom
    ...
}

Sensorveiledningen presiserer at «første- og siste-pekerne skal være av typen Skinnegaende» — altså supertypen, ikke en subtype. Det er en billig poengfelle.

Legge til bakerst — O(1) takket være siste-pekeren

void leggTil(Skinnegaende ny) {
    if (siste == null) {            // tom liste
        forste = ny;
        siste = ny;
    } else {
        siste.neste = ny;
        ny.forrige = siste;
        siste = ny;
    }
}

Sensorveiledningen sier: «det er viktig at programmet ikke leter gjennom listen, men bruker siste-pekeren til å sette inn sist». Skriver du en while-løkke som traverserer til enden, taper du poeng selv om resultatet blir riktig — nettopp fordi siste-pekeren finnes for å slippe den løkka. Tilsvarende for innsetting først: bruk forste-pekeren direkte.

Ta ut et element — de fire spesialtilfellene

Dette er den oppgaven flest mister poeng på, og årsaken er alltid den samme: ett av spesialtilfellene er glemt. Et element kan være (1) det eneste i lista, (2) først, (3) sist, eller (4) inne i midten. Skriv dem opp på kladdearket før du begynner å kode.

Skinnegaende taUt(Skinnegaende ut) {
    if (ut.forrige == null) forste = ut.neste;      // var først
    else ut.forrige.neste = ut.neste;

    if (ut.neste == null) siste = ut.forrige;       // var sist
    else ut.neste.forrige = ut.forrige;

    ut.neste = null;                                // rydd opp
    ut.forrige = null;
    return ut;
}

Skrevet slik dekkes alle fire tilfellene av to if-setninger, uten en eneste else if-kjede. Var elementet det eneste i lista, blir både forste og siste satt til null. Å nulle ut neste og forrige til slutt er ikke strengt nødvendig, men det hindrer at et uttatt objekt fortsatt peker inn i lista — en feil som gir merkelig oppførsel hvis objektet legges inn et annet sted senere.

For en enkeltlenket liste finnes ikke forrige, og da må du gå fram til noden foran den du skal fjerne:

Fly taUt(String id) {
    if (forste == null) return null;
    if (forste.hentId().equals(id)) {       // først i lista
        Fly ut = forste;
        forste = forste.neste;
        ut.neste = null;
        return ut;
    }
    Fly p = forste;
    while (p.neste != null && !p.neste.hentId().equals(id)) p = p.neste;
    if (p.neste == null) return null;       // fantes ikke
    Fly ut = p.neste;
    p.neste = ut.neste;
    ut.neste = null;
    return ut;
}

Her er while (p.neste != null && ...) riktig, i motsetning til ved vanlig gjennomløping — vi ser bevisst ett steg framover. Rekkefølgen i && er avgjørende: p.neste != null må stå først, ellers får du NullPointerException på siste element. Java evaluerer && kortsluttet, så høyre side hoppes over når venstre er usann.

Sette inn foran et gitt element

void leggTilForan(Skinnegaende gammel, Skinnegaende ny) {
    ny.neste = gammel;
    ny.forrige = gammel.forrige;
    if (gammel.forrige == null) forste = ny;        // gammel var først
    else gammel.forrige.neste = ny;
    gammel.forrige = ny;
}

Rekkefølgen på tilordningene betyr alt. Setter du gammel.forrige = ny; før du har lest av den gamle verdien, mister du referansen bakover og lista revner. Regelen er: koble den nye noden på først, koble om de gamle etterpå.

Søking

boolean erMed(String id) {
    for (Fly p = forste; p != null; p = p.neste) {
        if (p.hentId().equals(id)) return true;
    }
    return false;
}

Merk equals, ikke ==, og merk at return false står etter løkka, ikke inne i den. En else return false; inne i løkka gjør at metoden alltid svarer på første element alene.

Datastrukturtegning

Tegneoppgavene er verdt 5–10 poeng og kommer i åtte av seksten eksamenssettene jeg har gått gjennom. De ber deg tegne objektene i minnet under kjøring, ikke klassediagrammet. Kriteriene fra sensorveiledningene:

Tegn objekter og variabler, ikke klasser. Skriv på hvert objekt hvilken klasse det er en instans av.
Ikke tegn metoder.
Hver referansevariabel tegnes som en pil til objektet den peker på. Er den null, tegn en strek gjennom boksen eller skriv null.
Beholderobjektet tegnes som en egen boks med forste og siste i.
Er det en array involvert, tegnes den som en rad av ruter der hver rute enten er tom (null) eller har en pil til et objekt.

Typiske varianter: en dobbeltlenket liste med fire objekter av tre forskjellige klasser; en array alleBilene der bare noen av objektene også ligger i den lenkede lista over ledige biler; en array forsteRomEtasje der hvert element peker på starten av en egen liste, og to av etasjene er tomme; en beholder som både har en lenket liste og en hjelpeklasse med en array. Øv på å tegne disse raskt — det er de billigste poengene på hele settet etter oppgave 1.

Innerklasser når oppgaven ber om det

Noen sett (V2022-konte) ber uttrykkelig om en indre nodeklasse, fordi det samme objektet skal kunne ligge i flere lister samtidig. Da er node-objekter riktig svar:

class StedListe {
    StedNode forste, siste;

    class StedNode {
        Sted sted;
        StedNode neste, forrige;
        StedNode(Sted s) { sted = s; }
    }
}

Merk at iteratoren over en slik liste skal gå gjennom node-objektene, men next() skal returnere Sted-objektet inni. Les oppgaveteksten nøye: står det «bruk instansvariablene i disse objektene», skal du ikke lage noder; står det «en indre klasse som gjør at steder kan lenkes sammen», skal du det.

Studieguide: Lenkede lister og datastrukturtegning