Abiturklassen

BinarySearchTree.java

package abiturklassen.baumklassen;

/**
 * <p>Materialien zu den zentralen
 * Abiturpruefungen im Fach Informatik ab 2012 in 
 * Nordrhein-Westfalen.</p>
 * <p>Klasse BinarySearchTree</p>
 * <p>In einem Objekt der Klasse BinarySearchTree werden beliebig viele Objekte in einem Binaerbaum (binaerer Suchbaum)
 * entsprechend einer Ordnungsrelation verwaltet. Ein Objekt der Klasse stellt entweder einen leeren Baum dar oder 
 * verwaltet ein Inhaltsobjekt sowie einen linken und einen rechten Teilbaum, die ebenfalls Objekte der Klasse BinarySearchTree sind. 
 * Dabei gilt:
 * Die Inhaltsobjekte sind Objekte einer Unterklasse von Item, in der durch &uuml;berschreiben der 
 * drei Vergleichsmethoden isLess, isEqual, isGreater (s. Item) eine eindeutige Ordnungsrelation festgelegt sein muss.
 * Alle Objekte im linken Teilbaum sind kleiner als das Inhaltsobjekt des Binaerbaumes.
 * Alle Objekte im rechten Teilbaum sind groeßer als das Inhaltsobjekt des Binaerbaumes.
 * Diese Bedingung gilt auch in beiden Teilbaeumen.</p>
 * 
 * <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur 
 * im Fach Informatik</p>
 * 
 * @version 2011-01-05
 */
public class BinarySearchTree {

   private BinaryTree bintree;
   
   /**
     *Der Konstruktor erzeugt einen leeren Suchbaum. 
     */
   public BinarySearchTree() {
     bintree = new BinaryTree();
   }
   
   /**
     *Diese Anfrage liefert den Wahrheitswert true, wenn der Suchbaum leer ist, sonst liefert sie den Wert false.
     *@return true, wenn der binaere Suchbaum leer ist, sonst false
     */
   public boolean isEmpty() {
     return bintree.isEmpty();
   }
  
    /**
     * Falls ein bezueglich der verwendeten Vergleichsmethode isEqual mit pItem uebereinstimmendes Objekt im geordneten Baum enthalten ist,
     * passiert nichts. Andernfalls wird das Objekt pItem entsprechend der vorgegebenen Ordnungsrelation in den Baum eingeordnet. 
     * Falls der Parameter null ist, aendert sich nichts.
     * @param pItem  einzufuegendes Objekt
     */
   public void insert(Item pItem) {
     if (pItem!=null) {  
       if (bintree.isEmpty()) // wenn der Suchbaum leer ist, dann wird der Suchbaum mit dem Inhalt pItem gefuellt
         bintree=new BinaryTree(pItem);
       else {
         Item lItem = (Item)bintree.getObject();
         if (pItem.isLess(lItem)) { // links Einfuegen
           BinarySearchTree lTree=this.getLeftTree();
           lTree.insert(pItem);
           this.bintree.setLeftTree(lTree.bintree);
         }
         else
           if (pItem.isGreater(lItem)) { // rechts Einfuegen; bei Gleichheit wird nicht noch einmal eingefuegt
             BinarySearchTree rTree=this.getRightTree();
             rTree.insert(pItem);
             this.bintree.setRightTree(rTree.bintree);
           }
        }
      } 
   }
   
   /**
     * Falls ein bezueglich der verwendeten Vergleichsmethode isEqual mit pItem uebereinstimmendes Objekt im binaeren Suchbaum enthalten ist,
     * liefert die Anfrage dieses, ansonsten wird null zurueckgegeben.
     * Falls der Parameter null ist, wird null zurueckgegeben.
     * @param pItem  zu suchendes Objekt
     * @return das gefundene Objekt, bei erfolgloser Suche null
     */
   public Item search(Item pItem) {
     if (bintree.isEmpty() || pItem==null) // Suche war erfolglos oder es gab nichts zum Suchen
       return null;
     else {
       Item lItem = (Item)bintree.getObject();
       if (pItem.isLess(lItem))  // links suchen
         return this.getLeftTree().search(pItem);
       else
         if (pItem.isGreater(lItem)) // rechts suchen
           return this.getRightTree().search(pItem);
         else
           return lItem; // gefunden
      }
   }

   /**
     * Falls ein bezueglich der verwendeten Vergleichsmethode isEqual mit pItem uebereinstimmendes Objekt im binaeren Suchbaum enthalten ist,
     * wird dieses entfernt. 
     * Falls der Parameter null ist, aendert sich nichts.
     * @param pItem  zu entfernendes Objekt
     */
   public void remove(Item pItem)
   {    
     Item lWurzelInhalt;
     BinaryTree lKnoten,lGroessterLinkerKnoten;
     if (!this.isEmpty() && pItem!=null) {
       lWurzelInhalt=(Item) bintree.getObject();
       if (lWurzelInhalt.isEqual(pItem)) {  
         if (bintree.getRightTree().isEmpty() && bintree.getLeftTree().isEmpty()) {
           //Blatt loeschen
           //bintree = new BinaryTree();
           bintree.setEmpty();
         }
         else {
           // kein Blatt loeschen
           if (bintree.getRightTree().isEmpty()) {
              //rechter Teilbaum leer
              lKnoten=bintree.getLeftTree();
              bintree.setObject(lKnoten.getObject());
              bintree.setLeftTree(lKnoten.getLeftTree());
              bintree.setRightTree(lKnoten.getRightTree());
           }
           else {
             if (bintree.getLeftTree().isEmpty()) {
               lKnoten=bintree.getRightTree();
               bintree.setObject(lKnoten.getObject());
               bintree.setLeftTree(lKnoten.getLeftTree());
               bintree.setRightTree(lKnoten.getRightTree());
             }
             else { 
                //beide Teilbaeume links und rechts sind nicht leer
               lGroessterLinkerKnoten=bintree.getLeftTree();
               while (!lGroessterLinkerKnoten.getRightTree().isEmpty())
                 lGroessterLinkerKnoten=lGroessterLinkerKnoten.getRightTree();
               bintree.setObject(lGroessterLinkerKnoten.getObject());
               this.getLeftTree().remove((Item)lGroessterLinkerKnoten.getObject());
             }
           }
         }
       } 
       else
       {
         if (lWurzelInhalt.isLess(pItem)) { // rekursiv loeschen im rechten Teilbaum
           BinarySearchTree lRechterBaum=this.getRightTree();
           lRechterBaum.remove(pItem);
         }
         else { // rekursiv loeschen im linken Teilbaum
           BinarySearchTree lLinkerBaum=this.getLeftTree();
           lLinkerBaum.remove(pItem);
         }
       }
     }
   }
   
   /**
     * Diese Anfrage liefert das Inhaltsobjekt des Suchbaumes. Wenn der Suchbaum leer ist, wird null zurueckgegeben.
     * @return das Inhaltsobjekt bzw. null, wenn der Suchbaum leer ist.
     */
   public Item getItem() {
     if (this.isEmpty())
       return null;
     else  
       return (Item) bintree.getObject();
   }

   /**
     * Diese Anfrage liefert den linken Teilbaum des binaeren Suchbaumes.
     * Der binaere Suchbaum aendert sich nicht. Wenn er leer ist, wird null zurueckgegeben.
     * @return den linken Teilbaum bzw. null, wenn der Suchbaum leer ist.
     */
   public BinarySearchTree getLeftTree() {
     if (this.isEmpty())
       return null;
     else {   
       BinarySearchTree lTree = new BinarySearchTree(); // der linke Teilbaum muss ein Baum der Klasse BinarySearchTree sein
       lTree.bintree=bintree.getLeftTree();
       return lTree;
     }
   }

    /**
     * Diese Anfrage liefert den rechten Teilbaum des binaeren Suchbaumes.
     * Der binaere Suchbaum aendert sich nicht. Wenn er leer ist, wird null zurueckgegeben.
     * @return den rechten Teilbaum bzw. null, wenn der Suchbaum leer ist.
     */
   public BinarySearchTree getRightTree() {
     if (this.isEmpty())
       return null;
     else {    
       BinarySearchTree lTree = new BinarySearchTree(); // der rechte Teilbaum muss ein Baum der Klasse BinarySearchTree sein
       lTree.bintree=bintree.getRightTree();
       return lTree;
     }
   }

   /**
    * Für die Testausgabe
    */
    BinaryTree gibBaum()
   {
     return bintree; 
   }
  
}

BinaryTree.java

package abiturklassen.baumklassen;

 /**
 * <p>Materialien zu den zentralen
 * Abiturpruefungen im Fach Informatik ab 2012 in 
 * Nordrhein-Westfalen.</p>
 * <p>Klasse BinaryTree</p>
 * <p>Mithilfe der Klasse BinaryTree koennen beliebig viele Inhaltsobjekte in einem Binaerbaum verwaltet werden.
 * Ein Objekt der Klasse stellt entweder einen leeren Baum dar oder verwaltet ein Inhaltsobjekt sowie einen 
 * linken und einen rechten Teilbaum, die ebenfalls Objekte der Klasse BinaryTree sind.</p>
 * 
 * <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur 
 * im Fach Informatik</p>
 * 
 * @version 2011-01-05
 */
public class BinaryTree
{
    private Object lContent;
    private BinaryTree lLeftTree, lRightTree;

    /**
     *Nach dem Aufruf des Konstruktors existiert ein leerer Binaerbaum.
     */
    public BinaryTree() {
        lContent = null;
        lLeftTree = null;
        lRightTree = null;
    }   
    
    /**
     *Wenn der Parameter pContent ungleich null ist, existiert nach dem Aufruf des Konstruktors der Binaerbaum und hat pContent als Inhaltsobjekt
     *und zwei leere Teilbaeume. Falls der Parameter null ist, wird ein leerer Binaerbaum erzeugt.
     *@param pContent  Inhaltsobjekt
     */
    public BinaryTree(Object pObject) {
        if (pObject!=null) {
          lContent = pObject;
          lLeftTree = new BinaryTree();
          lRightTree = new BinaryTree();
        }
        else {
          lContent = null;
          lLeftTree = null;
          lRightTree = null;
        }   
    }        
    
    /**
     *Wenn der Parameter pContent ungleich null ist, wird ein Binaerbaum mit pContent als Objekt
     *und den beiden Teilbaeume pLeftTree und pRightTree erzeugt. Sind  pLeftTree oder pRightTree gleich null, wird der entsprechende Teilbaum
     *als leerer Binaerbaum eingefuegt. Wenn der Parameter pContent gleich null ist, wird ein leerer Binaerbaum erzeugt.
     *@param pContent  Inhaltsobjekt 
     *@param pLinkerBaum linker Binaerbaum
     *@param pRechterBaum rechter Binaerbaum
     */
    public BinaryTree(Object pContent, BinaryTree pLinkerBaum, BinaryTree pRechterBaum){
      if (pContent!=null) {
        lContent = pContent; 
        if (pLinkerBaum!=null)
          lLeftTree = pLinkerBaum;
        else
          lLeftTree = new BinaryTree();
        if (pRechterBaum!=null)
          lRightTree = pRechterBaum;
        else
          lRightTree = new BinaryTree();
       }    
       else {    // da der Inhalt null ist, wird ein leerer Baum erzeugt
         lContent = null;
         lLeftTree = null;
         lRightTree = null;
       } 
     
    }    
    
    /**
     *Diese Anfrage liefert den Wahrheitswert true, wenn der Binaerbaum leer ist, sonst liefert sie den Wert false.
     *@return true, wenn der Binaerbaum leer ist, sonst false
     */
    public boolean isEmpty() {
        return (lContent==null);
    } 
    
    /**
     *Wenn der Binaerbaum leer ist, wird der Parameter pObject als Inhaltsobjekt sowie ein leerer linker und rechter Teilbaum eingefuegt.
     *Ist der Binaerbaum nicht leer, wird das Inhaltsobjekt durch pObject ersetzt. Die Teilbaeume werden nicht geaendert.
     *Wenn pObject null ist, bleibt der Binaerbaum unveraendert.
     *@param pObject neues Inhaltsobjekt
     */
    public void  setObject(Object pObject) {   
       if (pObject!=null) {
          if (this.isEmpty()) {
            lLeftTree = new BinaryTree();
            lRightTree = new BinaryTree();
          }
          lContent = pObject;
       }
    }
    
    /**
     *Diese Anfrage liefert das Inhaltsobjekt des Binaerbaums. Wenn der Binaerbaum leer ist, wird null zurueckgegeben.
     *@return Inhaltsobjekt (bzw. null, wenn der Baum leer ist)
     */
    public Object getObject() {
         return lContent  ;
    }
    
    /**
     *Wenn der Binaerbaum leer ist, wird pTree nicht angehaengt.
     *Andernfalls erhaelt der Binaerbaum den uebergebenen Baum als linken Teilbaum. Falls der Parameter null ist, aendert sich nichts.
     *@param pTree neuer linker Teilbaum
     */
    public void setLeftTree(BinaryTree pTree) {
        if (!this.isEmpty() && pTree!=null)
            lLeftTree = pTree;
    }
    
    /**
     *Wenn der Binaerbaum leer ist, wird pTree nicht angehaengt.
     *Andernfalls erhaelt der Binaerbaum den uebergebenen Baum als rechten Teilbaum. Falls der Parameter null ist, aendert sich nichts.
     *@param pTree neuer rechter Teilbaum
     */
    public void setRightTree(BinaryTree pTree) {
        if (! this.isEmpty() && pTree!=null)
            lRightTree = pTree;
    }    
    
    /**
     *Diese Anfrage liefert den linken Teilbaum des Binaerbaumes.
     *Der Binaerbaum aendert sich nicht. Wenn der Binaerbaum leer ist, wird null zurueckgegeben.
     *@return linker Teilbaum
     */
    public BinaryTree getLeftTree() {
        if (! this.isEmpty())
          return lLeftTree;
        else
          return null;
    }
    
    /**
     *Diese Anfrage liefert den rechten Teilbaum des Binaerbaumes.
     *Der Binaerbaum aendert sich nicht. Wenn der Binaerbaum leer ist, wird null zurueckgegeben.
     *@return rechter Teilbaum
     */
    public BinaryTree getRightTree() {
        if (! this.isEmpty())
          return lRightTree;
         else
          return null;   
    }     
    
    /**
     *Der Baum wird durch diesen Auftrag geleert. 
     *Die Anfrage isEmpty liefert danach true zurueck und auf die beiden urspruenglichen Teilbaeume kann nicht mehr zugegriffen werden.
     */
    public void setEmpty() {
        lContent = null;
        lLeftTree = null;
        lRightTree = null;  
    }  
}

Item.java

package abiturklassen.baumklassen;

/**
 * <p>Materialien zu den zentralen
 * Abiturpruefungen im Fach Informatik ab 2012 in 
 * Nordrhein-Westfalen.</p>
 * <p>Klasse Item</p>
 * <p>Die Klasse Item ist abstrakte Oberklasse aller Klassen, deren Objekte in einen Suchbaum (BinarySearchTree) eingef&uuml;gt werden sollen. 
 * Die Ordnungsrelation wird in den Unterklassen von Item durch &Uuml;berschreiben der drei abstrakten Methoden isEqual, isGreater und isLess festgelegt. </p>
 * 
 * <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur 
 * im Fach Informatik</p>
 * 
 * @version 2010-10-20
 */
public abstract class Item {

  /**
     *Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gew&uuml;nschten Ordnungsrelation gr&ouml;ßer als das Objekt pItem ist,
     *wird true geliefert. 
     *Sonst wird false geliefert.
     *@param pItem es wird &uuml;berpr&uuml;ft, ob das aufrufende Objekt gr&ouml;ßer als dieser Parameter pItem ist
     */
  public abstract boolean isGreater (Item pItem);
  
  /**
     *Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gew&uuml;nschten Ordnungsrelation kleiner als das Objekt pItem ist,
     *wird true geliefert. 
     *Sonst wird false geliefert.
     *@param pItem es wird &uuml;berpr&uuml;ft, ob das aufrufende Objekt kleiner als dieser Parameter pItem ist
     */
  public abstract boolean isLess (Item pItem);
  
  /**
     *Wenn festgestellt wird, dass das Objekt, von dem die Methode aufgerufen wird, bzgl. der gew&uuml;nschten Ordnungsrelation gleich dem Objekt pItem ist,
     *wird true geliefert. 
     *Sonst wird false geliefert.
     *@param pItem es wird &uuml;berpr&uuml;ft, ob das aufrufende Objekt gleich dem Parameter pItem ist
     */
  public abstract boolean isEqual (Item pItem);
  
}

List.java

package abiturklassen.listenklassen;

/**
 * <p>Materialien zu den zentralen
 * Abiturpruefungen im Fach Informatik ab 2012 in 
 * Nordrhein-Westfalen.</p>
 * <p>Klasse List</p>
 * <p>Objekte der Klasse List verwalten beliebig viele, 
 * linear angeordnete Objekte. Auf hoechstens ein Listenobjekt, 
 * aktuelles Objekt genannt, kann jeweils zugegriffen werden. 
 * Wenn eine Liste leer ist, vollstaendig durchlaufen wurde oder 
 * das aktuelle Objekt am Ende der Liste geloescht wurde, gibt es 
 * kein aktuelles Objekt. Das erste oder das letzte Objekt einer 
 * Liste koennen durch einen Auftrag zum aktuellen Objekt gemacht werden. 
 * Außerdem kann das dem aktuellen Objekt folgende Listenobjekt 
 * zum neuen aktuellen Objekt werden. Das aktuelle Objekt kann gelesen, 
 * veraendert oder geloescht werden. Ausserdem kann vor dem aktuellen 
 * Objekt ein Listenobjekt eingefügt werden.</p>
 * 
 * <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur 
 * im Fach Informatik</p>
 * 
 * @version 2011-03-31
 */
public class List

{ private Node first, tail, current;

    // Node
  private class Node { 
        private Object contentObj;
        private Node nextNode;

        public Node(Object pContent) { 
            contentObj = pContent;
            nextNode = null;
        }

        public void setContent(Object pContent) { 
            contentObj = pContent; 
        }

        public Object content() { 
            return contentObj; 
        }

        public void setNext(Node pNext) { 
            nextNode = pNext; 
        }

        public Node getNext() { 
            return nextNode; 
        }

    } // Ende der Klasse Node
 
    /**
     * Eine leere Liste wird erzeugt.
     */
    public List() {
        tail = new Node(null); // Dummy
        first = tail;
        tail.setNext(tail);
        /* Der next-Zeiger des hinteren Dummy-Elementes
         * zeigt auf das vorangehende Element.
         */
        current=first;
    }
  
    /**
     * Die Anfrage liefert den Wert true, wenn die Liste 
     * keine Objekte enthaelt, sonst liefert sie den Wert false.
     * @return true, wenn die Liste leer ist, sonst false
     */
    public boolean isEmpty() { 
        return first == tail; 
    }
 
    /**
     * Die Anfrage liefert den Wert true, wenn es ein
     * aktuelles Objekt gibt, sonst 
     * liefert sie den Wert false.
     * @return true, falls Zugriff moeglich, sonst false
     */
    public boolean hasAccess() { 
        return (!this.isEmpty()) && (current != tail);
    }
  
    /**
     * Falls die Liste nicht leer ist, es ein aktuelles 
     * Objekt gibt und dieses nicht das letzte Objekt der 
     * Liste ist, wird das dem aktuellen Objekt in der Liste 
     * folgende Objekt zum aktuellen Objekt, andernfalls gibt 
     * es nach Ausführung des Auftrags kein aktuelles Objekt, 
     * d.h. hasAccess() liefert den Wert false.
     */
    public void next() { 
        if (this.hasAccess())
            current = current.getNext();
    }
 
    /**
     * Falls die Liste nicht leer ist, wird das erste 
     * Objekt der Liste aktuelles Objekt. 
     * Ist die Liste leer, geschieht nichts.
     */
    public void toFirst() {
        if (!this.isEmpty())  
            current = first; 
    }
 
    /**
     * Falls die Liste nicht leer ist, wird das 
     * letzte Objekt der Liste aktuelles Objekt. 
     * Ist die Liste leer, geschieht nichts.
     */
    public void toLast() {
        if (!this.isEmpty())  
            current = tail.getNext(); 
    }

    /**
     * Falls es ein aktuelles Objekt gibt 
     * (hasAccess() == true), wird das aktuelle Objekt 
     * zurueckgegeben, andernfalls (hasAccess()== false) 
     * gibt die Anfrage den Wert null zurueck.
     * @return Inhaltsobjekt
     */
    public Object getObject() {   
        if (this.hasAccess())
            return current.content();
        else 
            return null;
    }
 
    /**
     * Falls es ein aktuelles Objekt gibt (hasAccess() == true)
     * und pObject ungleich null ist, wird das aktuelle Objekt 
     * durch pObject ersetzt. Sonst bleibt die Liste unveraendert.
     * @param pObject Inhaltsobjekt
     */
    public void setObject(Object pObject) { 
        if (pObject != null && this.hasAccess() )
            current.setContent(pObject); 
    }

    /**
     * Ein neues Objekt pObject wird am Ende der Liste eingefuegt. 
     * Das aktuelle Objekt bleibt unveraendert. Wenn die Liste 
     * leer ist, wird das Objekt pObject in die Liste eingefuegt 
     * und es gibt weiterhin kein aktuelles Objekt 
     * (hasAccess() == false). Falls pObject gleich null ist, 
     * bleibt die Liste unveraendert. 
     *@param pObject Inhaltsobject
     */    
    public void append(Object pObject) { 
        if (pObject != null) {  
            Node lNewNode,lPos0;
            lPos0 = current;
            lNewNode = new Node(pObject);
            lNewNode.setNext(tail);
            if (this.isEmpty())
                first = lNewNode;
            else {  
                Node lPrevious = tail.getNext();
                lPrevious.setNext(lNewNode);
            }  
            tail.setNext(lNewNode);
            current = lPos0;
        }
    }  

    /**
     *Falls es ein aktuelles Objekt gibt (hasAccess() == true),
     *wird ein neues Objekt vor dem aktuellen Objekt in die 
     *Liste eingefuegt. Das aktuelle Objekt bleibt unveraendert. 
     *Wenn die Liste leer ist, wird pObject in die Liste eingefuegt
     *und es gibt weiterhin kein aktuelles Objekt 
     *(hasAccess() == false). Falls es kein aktuelles Objekt gibt 
     *(hasAccess() == false) und die Liste nicht leer ist oder 
     *pObject gleich null ist, bleibt die Liste unveraendert.
     *@param pObject Inhaltsobjekt
     */
    public void insert(Object pObject) {
        if (pObject != null) {
          Node lNewNode,lFront,lPos;
          if (this.isEmpty())
            this.append(pObject);
          else 
          if (this.hasAccess() ) {
            lPos = current;
            lNewNode = new Node(pObject);
            lNewNode.setNext(current);
            if (lPos == first )
              first = lNewNode;
            else {
              this.toFirst();
              lFront = current;
              while (this.hasAccess() & !(current == lPos)) {
                 lFront = current;
                 this.next();
              }
              lFront.setNext(lNewNode);  
            }          
            current=lPos;
          }
        }
    }

    /**
     * Die Liste pList wird an die Liste angehaengt. Anschliessend 
     * wird pList eine leere Liste. Das aktuelle Objekt bleibt unveraendert. 
     * Falls pList null oder eine leere Liste ist, bleibt die Liste 
     * unveraendert.
     * @param pList Liste
     */
    public void concat(List pList) {
      Node lCurrent1, lCurrent2, lPos0;
      if (pList != null && !pList.isEmpty() ) {
        if (this.isEmpty() ) {
          first = pList.first;
          tail = pList.tail;
          current = tail;
        }
        else {
          lPos0 = current;
          current = tail.getNext();
          lCurrent1 = current;
          pList.toFirst();
          current = pList.current;
          lCurrent2 = pList.current;
          lCurrent1.setNext(lCurrent2);
          if (lPos0 != tail)
            current = lPos0;
          else
            current = pList.tail;
          tail = pList.tail;
        }
        // pList wird zur leeren Liste
        pList.tail = new Node(null); // Dummy
        pList.first = pList.tail;
        pList.tail.setNext(tail);
        pList.current = pList.tail;
      }
    }

    /**
     * Falls es ein aktuelles Objekt gibt (hasAccess() == true),
     * wird das aktuelle Objekt geloescht und das Objekt hinter 
     * dem gelaeschten Objekt wird zum aktuellen Objekt. Wird das 
     * Objekt, das am Ende der Liste steht, geloescht, gibt es kein 
     * aktuelles Objekt mehr (hasAccess() == false). Wenn die Liste 
     * leer ist oder es kein aktuelles Objekt gibt (hasAccess() == false),
     * bleibt die Liste unveraendert.
     */
    public void remove() { 
        Node lPos, lFront;
        if (this.hasAccess() ) {
            if (current == first ) {
                first = current.getNext();
                if (current.getNext() == tail)
                    tail.setNext(first);
                current = first;  
            }
            else {
                lPos = current;
                this.toFirst();
                lFront = current;
                while (this.hasAccess() && !(current == lPos)) {
                    lFront = current;
                    this.next();
                }
                lFront.setNext(lPos.getNext());
                current = lFront.getNext();
                if (current == tail)
                    tail.setNext(lFront);
            }  
        }
    }  

}

Queue.java

package abiturklassen.listenklassen;

/**
 * <p>Materialien zu den zentralen
 * Abiturpruefungen im Fach Informatik ab 2012 in 
 * Nordrhein-Westfalen.</p>
 * <p>Klasse Queue</p>
 * <p>Objekte der Klasse Queue (Warteschlange) verwalten beliebige
 * Objekte nach dem First-In-First-Out-Prinzip, d.h. das zuerst
 * abgelegte Objekt wird als erstes wieder entnommen.</p>
 * 
 * <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur 
 * im Fach Informatik</p>
 * 
 * @version 2010-10-20
 */
public class Queue
{
    private Node head, tail;

    /**
     * Ein Knoten besteht aus einem Inhaltsobjekt 
     * und einem Nachfolgeknoten.
     */
    private class Node
    {
        private Object content;
        private Node nextNode;

        /**
         * Es wird ein neuer Knoten erzeugt.
         * 
         * @param pContent das Inhaltsobjekt
         * @param pNext der Nachfolgeknoten
         */
        public Node(Object pContent, Node pNext)
        { content = pContent;
            nextNode = pNext;
        }

        /**
         * Das Inhaltsobjekt wird ge&auml;ndert.
         * 
         * @param pContent das neue Inhaltsobjekt
         */
        public void setContent(Object pContent)
        { 
            content = pContent;
        }

        /**
         * Das Inhaltsobjekt wird zur&uuml;ckgegeben.
         * 
         * @return das Inhaltsobjekt
         */
        public Object content()
        {
            return content;
        }

        /**
         * Der Nachfolgeknoten wird ge&auml;dert.
         * 
         * @param pNext der neue Nachfolgeknoten
         */
        public void setNext(Node pNext)
        { 
            nextNode = pNext;
        }

        /**
         * Der Nachfolgeknoten wird zur&uuml;ckgegeben.
         * 
         * @return der Nachfolgeknoten
         */
        public Node next()
        {
            return nextNode;
        }
    }

    /**
     * Eine leere Schlange wird erzeugt.
     */
    public Queue() 
    {
        head = null;
        tail = null;
    }

    /**
     * Die Anfrage liefert den Wert true, wenn die Schlange keine Objekte
     * enthaelt, sonst liefert sie den Wert false.
     * 
     * @return true, falls die Schlange leer ist, sonst false
     */
    public boolean isEmpty(){
        return head == null;
    }

    /**
     * Das Objekt pObjekt wird an die Schlange angehaengt.
     * Falls pObject gleich null ist, bleibt die Schlange
     * unveraendert.
     * 
     * @param pObject das anzuhaengende Objekt
     */
    public void enqueue(Object pObject) 
    { 
        if (pObject != null){
            Node lNewNode = new Node(pObject, null);
            if (this.isEmpty()){
                head = lNewNode;
                tail = lNewNode;
            }
            else{
                tail.setNext(lNewNode);
                tail = lNewNode;
            }
        }  
    }

    /**
     * Das erste Objekt wird aus der Schlange entfernt.
     * Falls die Schlange leer ist, wird sie nicht 
     * veraendert.
     */
    public void dequeue() 
    {
        if (!this.isEmpty()){
            head = head.next();
        }
    }

    /**
     * Die Anfrage liefert das erste Objekt der Schlange.
     * Die Schlange bleibt unveraendert. Falls die 
     * Schlange leer ist, wird null zur&uuml;ck gegeben.
     * 
     * @return das erste Objekt der Schlange oder null, falls 
     * die Schlange leer ist.
     */
    public Object front(){
        if (this.isEmpty())
        {
            return null;
        }
        else{
            return head.content();
        }
    }

}

Stack.java

package abiturklassen.listenklassen;

/**
 * <p>Materialien zu den zentralen
 * Abiturpruefungen im Fach Informatik ab 2012 in 
 * Nordrhein-Westfalen.</p>
 * <p>Klasse Stack</p>
 * <p>Objekte der Klasse Stack (Keller, Stapel) verwalten beliebige
 * Objekte nach dem Last-In-First-Out-Prinzip, d.h. das zuletzt
 * abgelegte Objekt wird als erstes wieder entnommen.</p>
 * 
 * <p>NW-Arbeitsgruppe: Materialentwicklung zum Zentralabitur im Fach Informatik</p>
 * 
 * @version 2010-10-20
 */
public class Stack {
    private Node head;

    // Node
    private class Node {
        private Object content = null;
        private Node nextNode = null;

        public Node(Object pObject) {
            content = pObject;
            nextNode = null;
        }

        public void setNext(Node pNext) {
            nextNode = pNext;
        }

        public Node getNext() {
            return nextNode;
        }

        public Object getContent() {
            return content;
        }
    } // Ende Node

    // Stack
    /**
     * Ein leerer Stapel wird erzeugt.
     */   
    public Stack() { 
         head = null;
    }

    /**
     * Die Anfrage liefert den Wert true, wenn der Stapel 
     * keine Objekte enthaelt, sonst liefert sie den Wert false.
     * @return true, falls der Stapel leer ist, sonst false.
     */
    public boolean isEmpty() {
        return (head == null);
    }

    /**
     * Das Objekt pObject wird oben auf den Stapel gelegt. 
     * Falls pObject gleich null ist, bleibt der Stapel unveraendert.
     * @param pObject ist das einzufuegende Objekt.
     */
    public void push(Object pObject) {
        if (pObject != null) {
            Node lNode = new Node(pObject);
            lNode.setNext(head);
            head=lNode;
        }
    }

    /**
     * Das zuletzt eingefuegte Objekt wird von dem Stapel entfernt. 
     * Falls der Stapel leer ist, bleibt er unveraendert.
     */
    public void pop() {
        if (!isEmpty())
            head = head.getNext();
    }

    /**
     * Die Anfrage liefert das oberste Stapelobjekt. 
     * Der Stapel bleibt unveraendert. 
     * Falls der Stapel leer ist, wird null zurueck gegeben.
     * @return Inhaltsobjekt
     */     
    public Object top() {
        if (!this.isEmpty())
            return head.getContent();
        else
            return null;
    }

}