DATS 2300202006

Prev Up Next

Lenkede lister

Denne uken skal vi jobbe med lenkede lister. Lenkede lister er på akkurat samme måte som arrays en måte å lagre data på. På samme måte som vi kan lage et array

int[] values = ...

kan vi også lage en lenket liste

LinkedList values = ...

og bruke dem på liknende måter. Fordelen med et array er at det er veldig raskt å indeksere (en addisjon og en multiplikasjon - se videoen om datamaskinarkitektur hvor jeg går gjennom hvordan arrays fungerer). Ulempen er at vi på forhånd må vite nøyaktig hvor stort arrayet skal være. Vi kan ikke endre størrelse uten å kopiere hele arrayet. Det er nettopp dette en lenket liste fikser: vi kan med en lenket liste starte med 0 elementer, og så utvide med nøyaktig så mange elementer vi ønsker, helt til datamaskinen er tom for minne. 

I denne introduksjonsvideoen går vi kjapt gjennom et par av disse konseptene, samtidig som vi viser hvordan en lenket liste kan implementeres som en node-klasse:

class Node {
    int value;
    Node next;
}

Dobbelt lenket liste

I denne videoen går vi gjennom en dobbelt lenket liste: hvor det er mulig å starte både fra halen (tail) og fra hodet (head) for å søke etter elementer. Fordelen med en dobbelt lenket liste er at det er lett å legge til og fjerne noder både foran og bak, men en ulempe er at den krever en god del mer kildekode og en god del mer lagringsplass (trenger både next og previous peker for å lagre én verdi, value).

Iterativ og rekursiv traversering

I denne videoen går vi gjennom hvordan vi kan gjøre om den rekursive funksjonen vi gikk gjennom i forrige video til en iterativ funksjon. 

Legge til node

I denne videoen går vi gjennom hvordan vi med penn og papir får lagt til en node i en lenket liste, og samtidig hvordan vi omdanner dette til en enkel kildekode. Mer at spesialtilfeller som å legge til en node helt først, eller helt sist, ikke er behandlet. Her er det kun innlegging midt i en lenket liste. Prøv gjerne med penn og papir å tegne ned hvordan vi legger til en node først i en lenket liste, og lag kildekoden for dette (tips: dette vil du få bruk for i oblig 2). 

Fjerne node

I denne videoen går vi gjennom hvordan vi får fjernet en node fra en dobbelt lenket liste. Som den forrige videoen så tar vi ikke for oss spesialtilfellene. Prøv selv å lage tegning og kildekode som fjerner node i begynnelsen og slutten av den lenkede listen. Hint: Husk å oppdatere "head" og "tail" pekerene! Det er veldig lett å glemme disse, og da vil det ikke fungere. 

Forelesning tirsdag

I denne videoen går vi gjennom både lenkede lister og arraylister, og ser på fordeler og ulemper med disse to lineære datastrukturene.