Metodesignatur	Forklaring
moveToHead()	Flytter current til listehovudet
moveToTail()	Flytter current til listehalen
first() og last()	Flytter current til fyrste / siste node
advance() og retreat()	Flytter current til neste / forrige
insertBefore(Object x) og insertAfter(Object x)	Set x inn foran / etter current
retrieve()	Returner current-objektet
remove()	Sletter og returnerer current-objektet
isValid()	Returnerer true dersom current er reelt objekt
size()	Returnerer antal objekt

 

Lag så enkelt hovudprogram som testar alle metodane. Programmet treng ikkje ha GUI. Der forklaringa er upresis - gje din presisering

/**
 * Test av programmet
 *
 * Har tatt med utskrifter av hva som skjer, og testet
 * de fleste metoder (dette hovedsakelig for at koden skal være lettere å forstå på eksamen).
 */

public class TestProgram {
    public static void main(String[] args) {
        DoubleLinkedList liste = new DoubleLinkedList();
        
        System.out.print("\n******************************\n");
        System.out.print("* current = head");
        liste.insertAfter("Element1");
        System.out.print("\n* insertAfter(Element1)");
        liste.insertAfter("Element2");
        System.out.print("\n* insertAfter(Element2)");
        System.out.print("\n******************************\n");
        
        /* Utskriften skal vise:
            Innholdet i listen:
            - Element2
            - Element1
            Størrelsen er 2
        */
        System.out.print("Inneholdet i listen er: \n" + liste.toString() + "Størrelsen er: " + liste.size() + "\n");
        
        System.out.print("\n******************************\n");
        System.out.print("* current = head");
        System.out.print("\n* insertBefore(Element3)");
        System.out.print("\n******************************\n");
        try {
            liste.insertBefore("Element3");
        } catch (NoItemException e) {
            /* Utskriften viser
                 Kan ikke legge til objekt før head
            */
            System.out.print(e.getMessage() + "\n");
        }
        
        System.out.print("\n******************************\n");
        liste.advance();
        System.out.print("* advance()");
        System.out.print("\n* current står på Element2");
        liste.insertBefore("Element4");
        System.out.print("\n* insertBefore(Element4)");
        System.out.print("\n******************************\n");
        /* Utskriften skal vise:
            Innholdet i listen:
            - Element4
            - Element2
            - Element1
            Størrelsen er: 3
        */
        System.out.print("Inneholdet i listen er: \n" + liste.toString() + "Størrelsen er: " + liste.size() + "\n");
        
        
        System.out.print("\n******************************\n");
        liste.last();
        System.out.print("* last()");
        System.out.print("\n* current = Element1");
        liste.insertAfter("Element5");
        System.out.print("\n* insertAfter(Element5)");
        System.out.print("\n******************************\n");
        /* Utskriften skal vise
            Inneholdet i listen er:
            - Element4
            - Element2
            - Element1
            - Element5
            Størrelsen er: 4
        */
        System.out.print("Inneholdet i listen er: \n" + liste.toString() + "Størrelsen er: " + liste.size() + "\n");
        
        
        System.out.print("\n******************************\n");
        liste.first();
        System.out.print("* first()");
        System.out.print("\n* current = Element4");
        liste.insertBefore("Element6");
        System.out.print("\n* insertBefore(Element6)");
        System.out.print("\n******************************\n");
        
        /* Utskriften skal vise:
            Inneholdet i listen er:
            - Element6
            - Element4
            - Element2
            - Element1
            - Element5
            Størrelsen er: 5
        */
        System.out.print("Inneholdet i listen er: \n" + liste.toString() + "Størrelsen er: " + liste.size() + "\n");
        
        
        System.out.print("\n******************************\n");
        System.out.print("* moveToHead()");
        System.out.print("\n* current = head");
        System.out.print("\n* insertBefore(Element7)");
        System.out.print("\n******************************\n");

        liste.moveToHead();
        try {
            liste.insertBefore("Element7");
        } catch (NoItemException e) {
            /* Utskriften viser
                Kan ikke legge til objekt før head
            */
            System.out.print(e.getMessage() + "\n");
        }
        
        
        System.out.print("\n******************************\n");
        System.out.print("* moveToTail() ");
        System.out.print("\n* current = tail");
        System.out.print("\n* insertBefore(Element8)");
        System.out.print("\n******************************\n");

        liste.moveToTail();
        try {
            liste.insertAfter("Element8");
        } catch (NoItemException e) {
            /* Utskriften viser
                Kan ikke legge til objekt etter head
            */
            System.out.print(e.getMessage() + "\n");
        }
        
        System.out.print("\n******************************\n");
        System.out.print("* current = tail");
        System.out.print("\n* retrieve()");
        System.out.print("\n******************************\n");
        try {
            Object tmp = liste.retrieve();
            System.out.print("" + tmp + "\n");
        } catch (NoItemException e) {
            /* Utskriften viser
                Current har ingen objekter..
            */
            System.out.print(e.getMessage() + "\n");
        }
        
        System.out.print("\n******************************\n");
        System.out.print("* first()");
        System.out.print("\n* current = Element6");
        System.out.print("\n******************************\n");
        liste.first();
        /* Utskriften viser
            Elementet som er hentet ut: Element6
        */
        System.out.print("Elementet som er hentet ut: " + liste.retrieve() + "\n");
        
        System.out.print("\n******************************\n");
        System.out.print("* current = Element6");
        System.out.print("\n******************************\n");
        /* Utskriften viser
            Inneholdet i listen er:
            - Element6
            - Element4
            - Element2
            - Element1
            - Element5
            Størrelsen er: 5
        */
        System.out.print("Inneholdet i listen er: \n" + liste.toString() + "Størrelsen er: " + liste.size() + "\n");
        
        
        System.out.print("\n******************************\n");
        System.out.print("* current = Element6");
        System.out.print("\n* remove()");
        System.out.print("\n******************************\n");
        Object tmp = liste.remove();
        /* Utskriften viser
            Det slettete elementet er: Element6
        */
        System.out.print("Det slettete elementet er: " + tmp + "\n");
        
        System.out.print("\n******************************\n");
        System.out.print("* current = Element4");
        System.out.print("\n******************************\n");
        
        /* Utskriften skal vise:
            Inneholdet i listen er:
            - Element4
            - Element2
            - Element1
            - Element5
            Størrelsen er: 4
        */
        System.out.print("Inneholdet i listen er: \n" + liste.toString() + "Størrelsen er: " + liste.size() + "\n");
        
        System.out.print("\n******************************\n");
        System.out.print("* current = Element4");
        System.out.print("\n* find(Element1)");
        System.out.print("\n******************************\n");
        liste.find("Element1");
        /* Utskriften skal vise:
            Fant elementet: Element4, last(),insertAfter)
        */
        System.out.print("Fant elementet: " + liste.retrieve() + "\n");
        System.out.print("\n******************************\n");
        System.out.print("* current = Element1");
        System.out.print("\n* emptyList()");
        System.out.print("\n******************************\n");
        
        liste.emptyList();
        
        /* Utskriften skal vise:
            Inneholdet i listen er:
             
        */
        System.out.print("Inneholdet i listen er: \n" + liste.toString() + "\n");
        
    }
}

/**
 * Testprogram for å teste å sende inn objekter direkte i konstruktøren
 * Fant ut at det gikk an å lage konstruktører med variabelt antall variabler,
 * og det var så spennende at jeg måtte teste det ut :)
 */

public class TestProgram2 {

    public static void main(String[] args){
        DoubleLinkedList liste = new DoubleLinkedList("Element1", "Element2", "Element3");
        liste.insertAfter("Element4");
        
        /* Utskriften viser:
            Listen inneholder:
            - Element4
            - Element3
            - Element2
            - Element1
        */
        System.out.print("Listen inneholder: \n" + liste.toString());
    }
}

/**
 * Testprogram som sender argumenter inn via terminalen
 * f.eks: java TestProgram3 Element1 Element2 Element3
 */

public class TestProgram3 {

    public static void main(String[] args){
        DoubleLinkedList liste = new DoubleLinkedList();
        for (String txt : args) {
            liste.insertAfter(txt);
        }
        
        /* Utskrift hvis man skriver: "java TestProgram3 Element1 Element2 Element3"
            Listen inneholder:
            - Element3
            - Element2
            - Element1
         */
        System.out.print("Listen inneholder: \n" + liste.toString());
    }

}

/**
 * Oblig 5
 * Hilde Vestøl (106288)
 *
 * Programmet startes og testes fra TestProgram.java
 */

public class DoubleLinkedList {
    
    private DoubleLinkedNode head, tail, current;
    private int size;
    
    /**
     * Konstruktøren oppretter head og tail nodene
     * deretter initialiseres disse til sine startverdier
     */
    public DoubleLinkedList() {
        this.head = new DoubleLinkedNode();
        this.tail = new DoubleLinkedNode();
        this.initialize();
    }
    
    /**
     * En ekstra konstruktør hvor man kan sende inn objekter
     * som skal være i listen. Tar et variabelt antall argumenter
     */
    public DoubleLinkedList(Object ... args) {
        this();
        for (Object element : args) {
            insertAfter(element);
        }
    }
    
    /**
     * en privat metode som kun setter referansene for next og previous
     * på head og tail nodene, og setter current på head
     */
     private void initialize() {
        head.next = tail;
        tail.prev = head;
        size = 0;
        moveToHead();
    }
    
    /**
     * Flytter current referansen slik at den peker på head
     */
    public void moveToHead() {
        current = head;
    }
    
    /**
     * Flytter current referansen slik at den peker på tail
     */
    public void moveToTail() {
        current = tail;
    }
    
    /**
     * Flytter current referansen til den første faktiske
     * noden. Sjekker først om listen er tom
     * Kaster unntak
     */
    public void first() throws NoItemException {
        if (isEmpty() )
            throw new NoItemException("Listen er tom");
        current = head.next;
    }
    
    /**
     * Flytter current referansen til den siste faktiske
     * noden. Sjekker først om listen er tom
     * Kaster unntak
     */
    public void last() throws NoItemException {
        if (isEmpty() )
            throw new NoItemException("Listen er tom");
        current = tail.prev;
    }
    
    /**
     * har lagt til en ekstra metode for å sjekke om listen er tom
     */
    public boolean isEmpty() {
        return (head.next == tail);
    }
    
    /**
     * Har lagt til en ekstra metode som tømmer listen
     */
    public void emptyList() {
        initialize();
    }
    
    /**
     * Flytter current referansen til å peke på den neste
     * noden i listen. Må sjekke at ikke current peker på tail
     * Kaster unntak.
     */
    public void advance() throws NoItemException {
        if (current == tail)
            throw new NoItemException("Kan ikke avansere, er i enden av listen");
        current = current.next;
    }
    
    /**
     * Flytter current referansen til å peke på den forrige noden i listen.
     * Må sjekke at ikke current peker på head. Kaster unntak.
     */
    public void retreat() throws NoItemException {
        if (current == head)
            throw new NoItemException("kan ikke flytte bakover i listen");
        current = current.prev;
    }
    
    /**
     * Setter inn en node før current. Kaster unntak
     * Sjekker at listen ikke er tom, og at current ikke peker på head.
     * Current blir stående der den var. Om programmerer ønsker å flytte current
     * til den nye noden må man kalle retreat().
     * Ved å gjøre det på denne måten kan man bruke listen som en form for queue
     *
     * @param Object element - elementet som skal settes inn
     */
    public void insertBefore(Object element) throws NoItemException {
        if (current == head)
            throw new NoItemException("Kan ikke legge til objekt før head");

        DoubleLinkedNode newNode = new DoubleLinkedNode(current, current.prev, element);
        current.prev.next = newNode;
        current.prev = newNode;
        size++;
    }
    
    /**
     * Setter inn en node etter current. Kaster unntak
     * Sjekker at listen ikke er tom, og at current ikke peker på tail.
     * Current blir stående der den var. Om programmerer ønsker å flytte current
     * til den nye noden må man kalle advance().
     * Ved å gjøre det slik har man mulighet til å f.eks. bruke listen som en stack
     * ved å sette current på head kan man kalle insertAfter() og "pushe" objekter
     * inn på listen/stacken.
     *
     * @param Object element - elementet som skal settes inn
     */
    public void insertAfter(Object element) throws NoItemException {
        if (current == tail)
            throw new NoItemException("Kan ikke legge til objekt etter head");
        
        DoubleLinkedNode newNode = new DoubleLinkedNode(current.next, current, element); //next, prev, objektet
        current.next.prev = newNode;
        current.next = newNode;
        size++;
    }
    
    
    /**
     * Returnerer current objektet. Kaster unntak.
     * Sjekker at current står på en reell node som faktisk har et objekt å returnere
     */
    public Object retrieve() throws NoItemException {
        if (!isValid() )
            throw new NoItemException("Current har ingen objekter..");
        
        return current.element;
    }
    
    /**
     * Er kanskje fornuftig å ha en metode hvor man kan lete etter et objekt
     * og flytte current pekeren dit.
     */
    public void find(Object searchElement) throws NoItemException {
        DoubleLinkedNode tmp = head.next;
        
        while (tmp != tail) {
            if (tmp.element.equals(searchElement)) {
                // flytter ikke current før jeg vet om jeg har funnet det
                // for å unngå at current plasserer seg på tail ved søk.
                current = tmp;
                return;
            }
            tmp = tmp.next;
        }
        
        throw new NoItemException("Fant ikke elementet du leitet etter..");
    }
    
    
    /**
     * Sletter og returnerer current objektet sjekker at current faktisk peker på et objekt
     * kaster unntak. Flytter current til den neste, hvis listen er tom, så flyttes current
     * til head, da det er naturlig at en tom liste er helt lik som en nyopprettet liste
     * Setter man current til first() så kan man bruke remove() / retrieve() som om dette
     * var en stack/queue
     */
    public Object remove() throws NoItemException {
        if (!isValid() )
            throw new NoItemException("Kan ikke slette, har ingen objekt");
        
        Object tmpElement = current.element;
        current.prev.next = current.next;
        current.next.prev = current.prev;
        size--;
        
        if (current.next == tail)
            current = head; //hvis vi har sletter siste reelle objekt, settes current til head,
        else
            advance(); //hvis ikke flyttes den til neste node
                
        return tmpElement;
    }
    
    /**
     * Sjekker at current faktisk står på en reel node som inneholder et objekt/element
     */
    public boolean isValid() {
        return (current.element != null);
    }
    
    /**
     * Returnerer antall objekter i listen.
     * Her har jeg valgt å ha size som instansevariabel
     * og at denne økes/senkes hver gang man legger til
     * eller sletter en node
     */
    public int size() {
        return size;
    }
    
    /**
     * Alternativ til size som er ovenfor.
     * Da trenger jeg ikke en egen instansevariabel for size
     * men må gå gjennom hele listen for å telle hver gang.
     * Hva jeg ville valgt i praksis avhenger av hvor ofte
     * jeg ville regnet med å bruke size() og hvor stor
     * jeg kunne regne med at listen kan bli..
     */
    public int size2() {
        if (isEmpty() )
            return 0;
            
        DoubleLinkedNode tmp = head.next;
        int size = 0;
        while (tmp != tail) {
            size++;
            tmp = tmp.next;
        }
        return size;
    }

    /**
     * Metode som skriver ut alle objektene i listen
     */
    @Override
    public String toString() {
        String print = "";
        if (!isEmpty() ) {
            DoubleLinkedNode tmp = head.next;
            while (tmp != tail) {
                print += "- " + (String)tmp.element + "\n";
                tmp = tmp.next;
            }
        }
        return print;
    }
    
    /**
     * Privat klasse for nodene
     */
    private class DoubleLinkedNode {
        private DoubleLinkedNode next, prev;
        Object element;
        
        /* En konstruktør som gir deg mulighet til å opprette en tom node */
        public DoubleLinkedNode() {
            this(null, null, null);
        }
    
        public DoubleLinkedNode(DoubleLinkedNode next, DoubleLinkedNode prev, Object element) {
            this.next = next;
            this.prev = prev;
            this.element = element;
        }
    
    } // end class DoubleLinkedNode

}

/**
 * En egen klasse for exception for når et
 * element/node ikke finnes
 * har valgt å bruke RuntimeException fordi da kan man
 * også la være å bruke try/catch når man er helt sikker
 */
 public class NoItemException extends RuntimeException {
 
     /* Standard konstruktør med en standard feilmelding */
     public NoItemException() {
        super("Fant ikke noe element");
     }
     
     public NoItemException(String txt) {
        super(txt);
     }
     
     /**
     * En toString-metode som sender ut kun teksten jeg selv skriver
     * @return
     */
    @Override
    public String toString() {
        return getMessage();
    }
 
 } // end class NoItemException