Øvingsoppgaver - Lister

Oppgavesett 2

Oppgavene blir tema på øvingen fredag 27. januar. Innleveringen skal bestå av en pdf-fil med korte kommentarer og dokumentasjon (utskrifter etc.). Legg også ved godt dokumenterte java filer. Alt pakkes i en zipfil, med navn assignment02-*.zip der * er etternavnene til gruppemedlemmene. Javafilene skal tilhøre en pakke med navn package assignment02.

Fristen for innlevering er tirsdag 31.januar 09:00.

Ta utgangspunkt i liste-klassene vi laget i forelesning nr. 3 og 4. Bruk følgende interface:

package assignment02; public interface MyList<T> { public void append(T elm); public T get(int i); // Insert an element T at position i public void insert(int i, T elm); // Remove and return the element at position i public T remove(int i); }

Oppgave 1

A)

Implementer klassen LinkList<T>, som bruker en lenket liste av noder. Lag en testmetode som viser at metoden virker (husk spesialtilfeller), og legg ved utskrift som dokumentasjon.

B)

Implementer klassen ArrList<T> som bruker en tabell. Lag en testmetode som viser at metoden virker (husk spesialtilfeller), og legg ved utskrift som dokumentasjon.

Det er litt fiklete å opprette en generics array i Java, her er et eksempel:

T[] arr = (T[]) (new Object[42]);

Oppgave 2

Du skal nå teste hvor effektive de to listeimplementasjonene er. Lag et program som gjør følgende:

A)

Bygg opp en liste med 1 million Integer elementer, med tilfeldige verdier mellom 0 og 1000. Dette skal gjøres ved å bruke append metoden (hvis du begynner å få mistanke om at maskinen din ikke takler 1 million elementer, får du bare redusere antallet :-). Du må også kanskje også angi i IDE'n du bruker at du trenger litt mer enn standard minne når du skal kjøre denne testen. Mål tiden det tar å bygge listen, og del på antallet innsettinger for å få ut gjennomsnittlig tid for en innsetting. Gjør dette for både LinkList<T> og ArrList<T>.

Tips: Bruk System.currentTimeMillis(). Vær oppmerksom på at mange operasjoner i Java tar langt under et millisekund, derfor må vi ofte måle et større antall operasjoner og dele på antallet for å få ut gjennomsnittet.

B)

Bruk listene du har bygd opp i forrige deloppgave. Kjør et større antall spørringer av typen get(int i), der i er et tilfeldig tall mellom 0 og 1 million. Mål tiden det tar å gjøre alle disse spørringene, og del på antall spørringer for å få ut gjennomsnittlig tid for en spørring. Gjør dette for både LinkList<T> og ArrList<T>.

C)

Bruk listene du har bygd opp i forrige deloppgave. Tøm listene ved gjentatt bruk av metoden remove. Mål tiden og del på antall slettinger for å få ut gjennomsnittlig tid for en sletting. Gjør dette for både LinkList<T> og ArrList<T>.

D)

Kommenter og forklar resultatene fra A), B) og C).