Denne oppgaven er en innlevering i Algoritmer og Datastrukturer. Oppgaven er levert av følgende student:
- Alexander Hagen Huse, s354599, [email protected]
Hele denne obligen har blitt løst av Alexander.
Her følger en kort beskrivelse av de ulike oppgaveløsningene. For mer detaljer, se kommentarer i kildekoden.
Metoden antall()
returnerer antallet som er telt opp, mens tom()
sjekker om listen er tom.
I DobbeltLenketListe(T[] a)
brukes en for
-løkke som løper fra bakerste posisjon i arrayet og fram til første posisjon,
og som kun legger til en ny node hvis indeksen som mates inn (a[i]
) ikke har verdien null. Antallet og endringer
økes med én for hver node som legges til.
I metoden toString()
og omvendtString()
benyttes StringBuilder
for å akkumulere tegn og verdier til en hel streng. Etter å
ha lagt til klammeparentes [
, så sjekkes det om listen er tom. Hvis ikke den er tom, så legges hode-/haleverdien til,
for så å bruke en while
-løkke til å traversere gjennom resten (hvis det er noe mer) med node.neste
/node.forrige
fram til hale-/hodenoden. Til slutt legges avsluttende klammeparentes ]
på.
For metoden leggInn(T verdi)
så legges en ny node med innkommende verdi bakerst i lista og returnere true
.
Hvis tom liste, så settes både hode- og halepeker på den nye noden. Ellers settes tilordnes hale sin neste verdien til
den nye noden, den nye noden sin forrige tilordnes hale sin verdi og halepekeren flyttes bakerst.
Den private hjelpemetoden finnNode(int indeks)
sjekker først om parameteret indeks er mindre enn antall/2,
i så fall letes det etter noden fra hode. Hvis indeksen er lik eller større enn antall/2, så letes det etter noden
fra halen.
Metoden hent(int indeks)
bruker finnNode
-metoden, og returnerer den aktuelle nodens verdi.
oppdater(int indeks, T nyverdi)
finner også den aktuelle noden ved hjelp av parameteren indeks
som sendes til
metoden finnNode
. Når noden er funnet lagres den gamle verdien i en variabel, mens nodens verdi oppdateres til
ny verdi ved hjelp av parameteren T nyverdi
. Endringer økes og gammel verdi returneres.
Metoden Liste<T> subliste(int fra, int til)
oppretter en instans av klassen DobbeltLenketListe
. Det benyttes
en for
-løkke til å hente ut aktuelle verdier fra og med den oppgitte indeksen i fra
-parameteren og til
den oppgitte indeksen i til
-parameteren. Herunder brukes metodene finnNode()
og leggInn()
.
Kildekoden til metoden indeksTil(T verdi)
er hentet fra kompendiet under "Løsningsforslag - oppgaver i Avsnitt 3.3.3".
Metoden sjekker først om verdi
er null, og returnerer da -1
. Ellers starter letingen ved hode. En for
-løkke
løper gjennom og sammenlikner verdi
-parameteren med node.verdi
ved å bruke equals()
. Finnes ikke verdien
i lista, så returneres -1
, ellers returneres den første verdien fra venstre som er lik verdien det søkes etter.
inneholder(T verdi)
returnerer true
hvis lista inneholder verdien som søkes etter. Dette ved hjelp av overnevte metode.
Ellers returneres false
hvis indeksTil
returnerer -1
.
I denne oppgaven har jeg laget metoden leggInn(int indeks, T verdi)
. Denne metoden fungerer slik at først
sjekkes det om verdien som legges inn er null ved hjelp av Objects.requireNonNull()
. Deretter sjekkes det om
indeksen som er oppgitt er lovlig ved hjelp av indeksKontroll()
. Ny node opprettes så med innkommende verdi
.
Det brukes if
og else
-setninger, samt en for
-løkke for å avgjøre hvor noden skal ligge.
Endringer og antall økes ved vellykket innlegging.
I metodene fjern(T verdi)
og fjern(int indeks)
så benyttes if
- og else
-setninger for å avgjøre hvilken
node som skal fjernes. Hvis hode- eller hale-noden skal fjernes, så gjøres dette ved å flytte pekeren en til siden.
Ellers løpes det gjennom en løkke for å finne riktig node, for så å koble fra noden som skal fjernes, og kobler nodene
på hver side til hverandre. I fjern(T verdi)
brukes equals()
for å sammenlikne innekommende parameter verdi
med verdien til nodene i listen. Antall reduseres med én og endringer øker med én ved vellykket fjerning.
T next()
-metoden er delvis hentet fra kompendiet, programkode 3.2.5 e). Det blir sjekket om iteratorendringer
er lik endringer. Så blir det sjekket om det er flere igjen i listen. For så å ta vare på naboverdien og
flytte den til neste node.
Iterator<T> iterator()
returnerer en ny instans av DobbeltLenketListeIterator()
.
I private DobbeltLenketListeIterator(int indeks)
settes denne
til verdien til noden med innkommende indeks.
Dette gjøres ved å løpe gjennom en løkke og opprette en node med riktig verdi.
Oppgave avsluttes med å lage Iterator<T> iterator(int indeks)
som returnerer en ny instans av DobbeltLenketListeIterator()
med indeks
-parameteren som parameter.