Lenkede lister

Lenkede strukturer

• I en lenket struktur benyttes referansevariabler til å opprette forbindelser mellom objekter.
• Alternativ til tabell-basert implementasjon av en samling.
• Dynamiske.

Selv-refererende objekter

• Et objekt av klassen Person vist nedenfor har en referansevariabel til et annet Person-objekt.
• Ved å bruke denne klassen, kan vi lage en lenket liste med Person-objekter.
• Ett Person-objekt inneholder en referanse til et annet Person-objekt. Det andre Person-objektet inneholder en referanse til et tredje, og så videre.
• Objekter lagret i en lenket liste refereres ofte til som noder.

 
public class Person
{
    private String navn;
    
    // Peker til et annet Person-objekt: 
    private Person neste; 
    
    // ......
    
}

Sette inn node på begynnelsen av lenket liste

Hvis start er en referanse til første node i listen, kan vi sette inn en ny node ved å:

1. Sette den nye nodens neste-referanse til å peke på første element listen.
2. Sette start referansen til å peke på den nye noden

Hva skjer hvis vi gjør dette i omvendt rekkefølge?

Sette inn node inne i en lenket liste

Å sette inn en ny node i midt i en lenket liste, la oss si etter node A, krever følgende operasjoner:

1. Start på begynnelsen av listen, og finn frem til node A:
    1.1 La p peke på første node i listen
    1.2 Flytt referansen p helt til vi finner node A
2. Sett den nye nodens neste-referanse til å peke på noden som kommer etter A.
3. Sett node A sin neste-referanse til å peke på den nye noden. 

Fjerne første node fra lenket liste

1. Hvis du trenger første node noe annet sted, sett opp en separat referanse til
   denne. 
2. Flytt referansen til begynnelsen av listen flyttes slik at den peker på andre 
   node i listen.

Fjerne node inne i lenket liste

1. Finn frem til noden som kommer foran noden som skal slettes.
   1.1 Bruk to referanser, en til å finne noden som skal fjernes (p), 
       og en til å holde på referansen til noden som kommer rett foran denne
       (q).
   1.2 q.neste = p.neste 

Dummy noder / header noder

• I rutinene for å sette inn og fjerne noder håndteres første node i listen som et spesialtilfelle.
• Mulig å unngå dette ved å sette inn en header-node eller dummy-node som første element. Denne noden representerer ikke egentlig et element i listen, men sørger for at vi ikke trenger å håndtere to ulike tilfeller når vi skal sette inn eller fjerne en noden fra listen.

Node-klasser

• Person-klassen vi så på først, inneholder en referanse til et annet Person-objekt - er selv-refererende.
• En ulempe med dette er at Person-klassen må "vite" at den kan komme til å bli brukt som node i en lenket liste.
• Ønsker generelt ikke at objekter som lagres i en samling skal innholde implementasjons-detaljer fra underliggende datastruktur.
• Lager derfor en klasse Node som typisk inneholder (minst) to referanser: En til objektet som skal lagres og en til neste node i den lenkede listen.