Lister

Lister

I en liste har elementene en posisjon (indeks). I motsetning til stakker og køer har vi tilgang til alle elementene i en liste.

I javabiblioteket definerer grensesnittet java.util.List operasjonene som kan utføres på en liste. To implementasjoner av dette grensesnittet er java.util.ArrayList og java.util.LinkedList.

Eksempel: Sammenlikning av listeimplementasjoner

Metodene byggListe1, byggListe2 og sum vist nedenfor utfører alle operasjoner på lister.

Arbeidsmengde i O-notasjon for hver av metodene når de kalles med henholdsvis en ArrayList og en LinkedList?

    public static void byggListe1(List<Integer> liste, int N){
        liste.clear();
        for (int i=0; i<N; i++){
            liste.add(i);
        }        
    }
    

    
    public static void byggListe2(List<Integer> liste, int N){
        liste.clear();
        for (int i=0; i<N; i++){
            liste.add(0, i);
        }
    }
    

    public static int sum(List<Integer> liste){
        int s =0;
        
        for (int i=0; i <liste.size(); i++){
            s+= liste.get(i); 
        }        
        return s; 
    }
    

For sum-metoden er det get-metoden som gjør metoden ineffektiv for en lenket-liste-implementasjon. Vi så at ved å benytte en itarator kan denne metoden få arbeidsmengde O(N) for begge listeimplementasjonene.

Oppsummering

ArrayList

• Fordeler:
  • Oppslag (se på element på en bestemt posisjon) O(1)
  • Endre verdien til et element O(1)
  • Innsetting eller fjerning av elementer på slutten av lista O(1)
• Ulemper:
  • Innsetting og fjerning av elementer som ikke skjer på slutten av lista: O(N)

LinkedList

• Fordeler
  • Innsetting og fjerning på begynnelsen og slutten av lista: O(1)
• Ulemper
  • Oppslag (se på element på en bestemt posisjon) O(N)
  • Endre verdien til et element: O(N)

Iteratorens remove-metode

• Nedenfor er et utkast til en array-implementasjon av en liste, med en privat iterator-klasse.
• Iterator-klassen inneholder en naiv implementasjon av remove-metoden. Hva skjer hvis listen endres gjennom liste-klassens metoder mens iteratoren er i bruk?
• Hvordan kan man kontrollere at listen ikke er endret av andre metoder enn iteratorens remove-metode mens iteratoren er i bruk?

Josephus problem

• 41 jødiske opprørere fanget i en hule
• Istedenfor å overgi seg, bestemte de seg for å begå selvmord.
• Bestemte seg for å stille seg i en ring, og drepe hver 3. person til det ikke var fler igjen.
• Josephus ønsket ikke å dø, og beregnet hvor han måtte stå for å være den siste gjenlevende.

http://www.cut-the-knot.org/recurrence/flavius.shtml

Algoritme - Josephus problem

Algoritmen nedenfor benytter en indeksert liste til å skrive ut rekkefølgen personene tas ut av ringen.

Listen behandles som om den var sirkulær. I tillegg må vi ta hensyn til at at listen kollapser mens vi er i gang.

Posisjonen til personen som fjernes: p
Avstand mellom personene som fjernes: d
Antall personer igjen: n

1. Posisjonen til første person som skal tas ut av ringen: p = d-1;
2. Så lenge som listen ikke er tom: 
   2.1 Skriv ut p 
   2.2 Antall personer igjen: n = n-1
   2.3 Hvis n > 0 
       Finn posisjonen til neste person som skal tas ut av ringen: 
       p= (p+d-1)%n;        

Oppgave

Lag en algoritme som benytter en kø til å løse Josephus problem!