Oppgave 2

I leggInn-metoden vil en verdi hvis den finnes fra før, bli lagt inn bak (til høyre for) den eller de som ligger i tabellen fra før. Det betyr at like verdier tas ut i motsatt rekkefølge i forhold til hvordan de ble lagt inn. Hvis en i while-løkken i leggInn-metoden endrer ulikhetstegnet > i c.compare(verdi,a[i]) > 0 til >= , vil en verdi bli lagt inn foran (til venstre) for de som måtte være like. Dermed vil like verdier tas ut i samme rekkefølge som de ble lagt inn.

Oppgave 3

  public boolean taUt(T verdi)
  {
    int i = 0;
    for (; i < antall; i++)
    {
      if (c.compare(a[i],verdi) == 0) break;
    }

    if (i == antall) return false;  // fant ikke verdi

    antall--;            // reduserer antallet

    while (i < antall)   // tetter igjen "hullet"
    {
      a[i] = a[i+1];
      i++;
    }

    a[antall] = null;    // klargjør for resirkulering

    return true;
  }

Oppgave 4

import java.util.*;

public class SortertLenketPrioritetsKø<T> implements PrioritetsKø<T>
{
  private static final class Node<T>
  {
    private T verdi;
    private Node<T> neste;

    private Node(T verdi, Node<T> neste)
    {
      this.verdi = verdi; this.neste = neste;
    }
  } // class Node

  private Node<T> hode;
  private Comparator<? super T> c;
  private int antall;

  public SortertLenketPrioritetsKø(Comparator<? super T> c)
  {
    this.c = c;
    hode = null;
    antall = 0;
  }

  public void leggInn(T verdi)
  {
    if (antall == 0 || c.compare(verdi,hode.verdi) >= 0)
      hode = new Node<T>(verdi,hode);
    else
    {
      Node<T> q = null, p = hode;
      while (p != null && c.compare(p.verdi,verdi) > 0)
      {
        q = p;
        p = p.neste;
      }

      q.neste = new Node<T>(verdi,p);
    }
    antall++;
  }

  public T kikk()
  {
    if (antall == 0) throw new NoSuchElementException();

    return hode.verdi;
  }

  public T taUt()
  {
    if (antall == 0) throw new NoSuchElementException();

    T temp = hode.verdi;
    hode = hode.neste;
    antall--;

    return temp;
  }

  public boolean tom()
  {
    return antall == 0;
  }

  public int antall()
  {
    return antall;
  }

  public void nullstill()
  {
    hode = null;
    antall = 0;
  }

  public String toString()
  {
    if (antall == 0) return "[]";

    StringBuilder s = new StringBuilder();
    s.append('['); s.append(hode.verdi);

    for (Node<T> p = hode.neste; p != null; p = p.neste)
    {
      s.append(','); s.append(' '); s.append(p.verdi);
    }
    s.append(']');

    return s.toString();
  }

}  // class SortertLenketPrioritetsKø