06 / PROGRAMMERING
Datastrukturer i Java
Tettere på grunnprinsippene med en usortert, enkeltlenket liste og kompleksitetsanalyse.
Målet med prosjektet
Implementere en usortert, enkeltlenket liste i Java og undersøke operasjoner, algoritmer og kompleksitet. Prosjektet knytter en abstrakt datastruktur til en konkret implementasjon og kostnaden ved ulike operasjoner.
Mitt bidrag
- Implementert en usortert, enkeltlenket liste i Java som et studieprosjekt.
- Jobbet med listeoperasjoner og algoritmer.
- Analysert kompleksiteten til operasjonene i datastrukturen.
Tekniske utfordringer og tilnærming
Fra listebegrep til lenkede noder
Jeg implementerte en usortert, enkeltlenket liste i Java. Hver node peker videre til den neste, så operasjonene må bevare lenkene. En tom liste, den første noden og slutten av listen er viktige tilfeller når man vurderer korrekthet. Konkrete testtilfeller er ikke publisert her.
Forstå kostnaden ved en operasjon
Jeg analyserte operasjonene ut fra hvor mye av listen de må gå gjennom. Et søk etter en verdi i en usortert, enkeltlenket liste kan kreve at alle n noder besøkes: O(n) i verste fall. Dette beskriver en egenskap ved datastrukturen, ikke en ytelsesmåling av implementasjonen min.
Faglig utbytte
Prosjektet handler om hvordan lenkede strukturer representerer data, hvordan operasjonene bruker strukturen og hvordan man vurderer beregningsmessig kompleksitet.
Prosjektets omfang
Studiearbeid. Oversikten beskriver den implementerte strukturen og begrepene bak den. Kildekode, en gjennomgang av hver operasjon og testresultater er ikke tilgjengelige i denne porteføljen. Fullstendig oppgavemateriale publiseres ikke.