Java/List
Aus ZUM-Unterrichten
< Java
Erster Implementierungsansatz
- ??? Wahrscheinlich ist der Positionszähler nicht so gemeint. Er soll anscheinend selbst ein Listenelement sein. Besitzt jemand einen stimmigen Quelltext?
Mögliche Interpretation
Realisiert mit ArrayList:
import java.util.ArrayList;
public class List {
private ArrayList liste;
private int positionszeiger;
public List(){
liste = new ArrayList(); // die Liste ist leer
positionszeiger=-1; // der Positionszeiger steht vor der Liste
}
public void insertBefore (Object pObject){
liste.add(positionszeiger, pObject);
positionszeiger--;
}
public void insertBehind (Object pObject){
liste.add(positionszeiger+1, pObject);
}
public void update (Object pObject){
liste.set(positionszeiger, pObject);
}
public void delete (){
liste.remove(positionszeiger);
}
public void next(){
if (positionszeiger!=liste.size()) positionszeiger++;
}
public void previous(){
if (positionszeiger>-1) positionszeiger--;
}
public void toFirst(){
positionszeiger=0;
}
public void toLast(){
positionszeiger=liste.size()-1;
}
public Object getItem(){
if (liste.size()==0 || positionszeiger==-1 || positionszeiger>=liste.size())
return null;
else return liste.get(positionszeiger);
}
public boolean isEmpty (){
return (liste.size()==0);
}
public boolean isBefore (){
return (positionszeiger<0);
}
public boolean isBehind (){
return (positionszeiger>=liste.size());
}
}
- Korrekturen
11.09. - insertBehind: Positionszeiger wird vor und zurück gestellt http://informatik.zum.de/pieper/blog/index.php?entry=entry060828-105313
Zweiter Implementierungsansatz OOP pur
- ??? Wahrscheinlich ist der Positionszeiger aus Delphi entlehnt und nicht sauber auf Java übertragbar. Hier mein Versuch es mit möglichst reinem OOP zu versuchen (bitte auf die Basisklasse ListElement achten).
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
/**
* '''Bestandteil des Zentralabiturs 2009'''<br>
* <br>
* Objekte der Klasse List verwalten beliebige Objekte nach einem Listenprinzip. Ein
* interner Positionszeiger wird durch die Listenstruktur bewegt, seine Position markiert
* ein aktuelles Objekt. Die Lage des Positionszeigers kann abgefragt, verändert und die
* Objektinhalte an den Positionen können gelesen oder verändert werden. Die Klasse Stack
* stellt Methoden in folgender Syntax zur Verfügung:
* <ul>
* <li>public List()</li>
* <li>public boolean isEmpty()</li>
* <li>public boolean isBefore()</li>
* <li>public boolean isBehind()</li>
* <li>public void next()</li>
* <li>public void previous()</li>
* <li>public void toFirst()</li>
* <li>public void toLast()</li>
* <li>public Object getItem()</li>
* <li>public void update (Object pObject)</li>
* <li>public void insertBefore (Object pObject)</li>
* <li>public void insertBehind (Object pObject)</li>
* <li>public void delete()</li>
* </ul>
* ''' Nicht Bestandteil des Zentralabiturs 2009''' - dient der praktischen Anwendung<br>
* <ul>
* <li>public clone()</li>
* <li>public load(String fileName)</li>
* <li>public save(String fileName)</li>
* </ul>
*
* @author <a href="mailto:schule@dinro.de">DiNaro</a>
* @version 1.0z+ 2006-09-12
*/
public class List implements Cloneable, Serializable
{
/**
* Attribut dient zur Serialisierung.
*/
private static final long serialVersionUID = 1087406856309777647L;
/**
* Attribut der Positionszeiger befindet sich vor der Liste (Flag).
*/
private boolean before;
/**
* Attribut der Positionszeiger befindet sich hinter der Liste (Flag).
*/
private boolean behind;
/**
* Attribut aktuelles Element.
*/
private ListElement current;
/**
* Attribut erstes Element der Liste
*/
private ListElement first;
/**
* Attribut letztes Element der Liste.
*/
private ListElement last;
/**
* Der Konstruktor erzeugt eine leere lineare Liste.<br>
* <br>
*
* <pre>
* Konstruktor List()
* <br>
* Nachher Eine leere Liste ist angelegt.
* Der interne Positionszeiger steht vor der leeren Liste.
* </pre>
*/
public List()
{
this.first = null;
this.last = null;
this.current = null;
this.before = true;
this.behind = false;
}
/**
* Kopiert die Liste - '''Nicht Bestandteil des Zentralbiturs 2009!!!'''<br>
* ("shallow copy" nach dem Handbuch der Java Programmierung Kapitel 9.4.2).
*
* @return kopierte lineare Liste
* @throws CloneNotSupportedException kann nicht auftreten, aber der Compiler will es
* so...
*/
@Override
public List clone() throws CloneNotSupportedException
{
try
{
return (List) super.clone();// "shallow copy"
}
catch (CloneNotSupportedException e)
{ // Kann nicht auftreten, aber der Compiler will es so...
throw new CloneNotSupportedException(e.toString());
}
}
/**
* Löscht des aktuellen Listenelement.<br>
* <br>
*
* <pre>
* Auftrag delete()
* Vorher Der Positionszeiger steht nicht vor oder hinter der Liste.
* Nachher Das aktuelle Listenelement ist gelöscht. Der Positionszeiger steht auf
* dem Element hinter dem gelöschten Element, bzw. hinter der Liste,
* wenn das gelöschte Element das letzte Listenelement war.
* </pre>
*/
public void delete()
{
if (!this.before && !this.behind)
{ // Zeiger des Vorgängerelementes setzen
if (this.current == this.first)
{ // Vorgänger existiert nicht - Kopfzeiger korregieren
this.first = this.current.getNext();
}
else
{ // Vorgänger existiert
this.current.getPrevious().setNext(this.current.getNext());
}
// Zeiger des Nachfolgerelementes setzen
if (this.current == this.last)
{ // Nachfolger existiert nicht - Scxhwanzzeiger korreegieren
this.last = this.current.getPrevious();
}
else
{ // Nachfolger existiert
this.current.getNext().setPrevious(this.current.getPrevious());
}
// aktuelles Element setzen
this.current = this.current.getNext();
// Flag für Positionszeiger befindet sich hinter der Liste setzen
this.behind = this.current == null;
}
}
/**
* Gibt den Inhalt des aktuellen Listenelementes zurück, ohne die Liste zu verändern.<br>
* <br>
*
* <pre>
* Anfrage getItem(): Object
* Nachher Die Anfrage liefert den Wert des aktuellen Listenelements bzw. null,
* wenn die Liste keine Elemente enthält, bzw. der Positionszeiger
* vor oder hinter der Liste steht.
* </pre>
*
* @return item Inhalt des aktuellen Listenelementes.
*/
public Object getItem()
{
if (this.current != null)
{
return this.current.getItem();
}
else
{
return null;
}
}
/**
* Einfügen eines Listenelementes vor das aktuelle.<br>
* <br>
*
* <pre>
* Auftrag insertBefore (Object pObject)
* Vorher Der Positionszeiger steht nicht vor der Liste.
* Nachher Ein neues Listenelement mit dem entsprechenden Objekt ist angelegt und
* vor der aktuellen Position in die Liste eingefügt worden.
* Der Positionszeiger steht hinter dem eingefügten Element.
* </pre>
*
* @param pObject Inhalt des Listenelementes.
*/
public void insertBefore(Object pObject)
{
if (!this.before)
{ // Der Positionszeiger steht nicht vor der Liste.
ListElement newElement;
if (this.isEmpty())
{ // Erstes und einziges Element in die Liste einfügen
newElement = new ListElement(pObject, null, null);
this.first = newElement;
this.last = newElement;
this.behind = true;
this.current = null;
}
else
{ // Die Liste ist nicht leer
if (this.behind)
{ // Der Positionszeiger steht hinter der Liste
newElement = new ListElement(pObject, this.last, null);
this.last.setNext(newElement);
this.last = newElement;
this.behind = true;
this.current = null;
}
else
{ // Der Positionszeiger steht mitten in der Liste
newElement = new ListElement(pObject, this.current.getPrevious(), this.current);
if (this.current == this.first)
{ // Vorgänger existiert nicht - Kopfzeiger korregieren
this.first = newElement;
}
else
{ // Vorgänger koregieren
this.current.getPrevious().setNext(newElement);
}
// Nachfolger korregieren
this.current.setPrevious(newElement);
// Aktuelles Element bleibt aktuelles Element
}
}
}
}
/**
* Einfügen eines Listenlementes hinter das aktuelle.<br>
* <br>
*
* <pre>
* Auftrag insertBehind (Object pObject)
* Vorher Der Positionszeiger steht nicht hinter der Liste.
* Nachher Ein neues Listenelement mit dem entsprechenden Objekt ist angelegt
* und hinter der aktuellen Position in die Liste eingefügt worden. Der
* Positionszeiger steht vor dem eingefügten Element.
* </pre>
*
* @param pObject Inhalt des Listenelementes.
*/
public void insertBehind(Object pObject)
{
if (!this.behind)
{ // Der Positionszeiger steht nicht hinter der Liste.
ListElement newElement;
if (this.isEmpty())
{// Erstes und einziges Element in die Liste einfügen
newElement = new ListElement(pObject, null, null);
this.first = newElement;
this.last = newElement;
this.before = true;
this.current = null;
}
else
{ // Die Liste ist nicht leer
if (this.before)
{ // Der Positionszeiger steht vor der Liste.
newElement = new ListElement(pObject, null, this.first);
this.first.setPrevious(newElement);
this.first = newElement;
this.before = true;
this.current = null;
}
else
{ // Der Positionszeiger steht mitten in der Liste.
newElement = new ListElement(pObject, this.current, this.current.getNext());
if (this.current == this.last)
{ // Nachfolger existiert nicht - Schwanzzeiger korregieren
this.last = newElement;
}
else
{ // Nachfolger korregieren
this.current.getNext().setPrevious(newElement);
}
// Vorgänger koregieren
this.current.setNext(newElement);
// Aktuelles Element bleibt aktuelles Element
}
}
}
}
/**
* Steht der Positionszeiger vor der Liste?<br>
* <br>
*
* <pre>
* Anfrage isBefore(): boolean
* Nachher Die Anfrage liefert den Wert true, wenn der Positionszeiger vor dem
* ersten Listenelement oder vor der leeren Liste steht, sonst liefert
* sie den Wert false.
* </pre>
*
* @return liefert den Wert true, wenn der Positionszeiger vor dem ersten Listenelement
* oder vor der leeren Liste steht, sonst liefert sie den Wert false.
*/
public boolean isBefore()
{
return this.before;
}
/**
* Steht der Positionszeiger hinter der Liste?<br>
* <br>
*
* <pre>
* Anfrage isBehind(): boolean
* Nachher Die Anfrage liefert den Wert true, wenn der Positionszeiger hinter dem
* letzten Listenelement oder hinter der leeren Liste steht, sonst liefert
* sie den Wert false.
* </pre>
*
* @return liefert den Wert true, wenn der Positionszeiger hinter dem letzten
* Listenelement oder hinter der leeren Liste steht, sonst liefert sie den Wert
* false.
*/
public boolean isBehind()
{
return this.behind;
}
/**
* Enthält die Liste keine Elemente?<br>
* <br>
*
* <pre>
* Anfrage isEmpty(): boolean
* Nachher Die Anfrage liefert den Wert true, wenn die Liste keine Elemente
* enthält, sonst liefert sie den Wert false.
* </pre>
*
* @return liefert den Wert true, wenn die Liste keine Elemente enthält, sonst liefert
* sie den Wert false.
*/
public boolean isEmpty()
{
return this.first == null;
}
/**
* Lädt die gesamte Liste als Objekt aus einer Datei - <b>Nicht Bestandteil des
* Zentralbiturs 2009!!!</b><br>
* Neues aktuelles Element wird das erste Listenelement(Setzung!).
*
* @param fileName [Laufwerk][Pfad]Dateiname,
* @throws ClassNotFoundException Erwartete Klasse nicht vorhanden
* @throws IOException Fehler beim Laden der Datei
*/
public void load(final String fileName) throws ClassNotFoundException, IOException
{
try
{
final ObjectInputStream stream = new ObjectInputStream(
new FileInputStream(fileName));
final List dummy = (List) stream.readObject();
this.first = dummy.first;
this.last = dummy.last;
this.before = dummy.before;
this.behind = dummy.behind;
this.toFirst(); // Als neues aktuelles Element wird das erste Listenelement gesetzt!
stream.close();
}
catch (final ClassNotFoundException e)
{ // Erwartete Klasse nicht vorhanden.
throw new ClassNotFoundException(e.toString());
}
catch (final IOException e)
{ // Fehler beim Laden der Datei.
throw new IOException(e.toString());
}
}
/**
* Setze das aktuelle Listenelement auf das nächste. <br>
* <br>
*
* <pre>
* Auftrag next()
* Nachher Der Positionszeiger ist um eine Position in Richtung Listenende weiter-
* gerückt, d.h. wenn er vor der Liste stand, wird das Element am
* Listenanfang zum aktuellen Element, ansonsten das jeweils nachfolgende
* Listenelement. Stand der Positionszeiger auf dem letzten Listenelement,
* befindet er sich jetzt hinter der Liste. Befand er sich hinter der
* Liste, hat er sich nicht verändert.
* </pre>
*/
public void next()
{
if (!this.isEmpty())
{
if (this.before)
{ // Der Positionszeiger steht vor der Liste; das erste Element wird aktuelles
this.current = this.first;
this.before = false;
}
else
{ // der Positionszeiger steht nicht vor der Liste
if (this.current != null)
{ // das jeweils nachfolgende Listenelement wird aktuelles
this.current = this.current.getNext();
if (this.current == null)
{ // Der Positionszeiger zeigt hinter das letzte Element
this.behind = true;
}
}
} // Der Positionszeiger befindet sich hinter der Liste und bleibt unverändert
}
}
/**
* Setze das aktuelle Listenelement auf das vorherige.<br>
* <br>
*
* <pre>
* Auftrag previous()
* Nachher Der Positionszeiger ist um eine Position in Richtung Listenanfang
* weitergerückt, d.h. wenn er hinter der Liste stand, wird das Element am
* Listenende zum aktuellen Element, ansonsten das jeweils vorhergehende
* Listenelement. Stand der Positionszeiger auf dem ersten Listenelement,
* befindet er sich jetzt vor der Liste. Befand er sich vor der Liste, hat
* er sich nicht verändert.
* </pre>
*/
public void previous()
{
if (!this.isEmpty())
{ /// Der Positionszeiger bleibt unverändert, wenn die Liste leer ist
if (this.behind)
{ // Der Positionszeiger steht hinter der Liste; das letzte Element wird aktuelles
this.current = this.last;
this.behind = false;
}
else
{// Der Positionszeiger steht nicht hinter der Liste
if (this.current != null)
{ // das jeweils vorhergehende Listenelement wird aktuelles
this.current = this.current.getPrevious();
if (this.current == null)
{ // Der Positionszeiger zeigt vor das erste Element
this.before = true;
}
}
} // Der Positionszeiger befindet sich vor der Liste und bleibt unverändert
}
}
/**
* Speichert die gesamte Liste als Objekt in einer Datei - <b>Nicht Bestandteil des
* Zentralbiturs 2009!!!</b><br>
* Das aktuelles Element bleibt erhalten!
*
* @param fileName [Laufwerk][Pfad]Dateiname.
* @throws IOException Fehler beim Speichern der Datei
*/
public void save(String fileName) throws IOException
{
try
{
ObjectOutputStream stream = new ObjectOutputStream(new FileOutputStream(fileName));
stream.writeObject(this);
stream.close();
}
catch (IOException e)
{ // Fehler beim Speichern der Datei.
throw new IOException(e.toString());
}
}
/**
* Setzt das aktuelle Listenelement auf das erste zurück.<br>
* <br>
*
* <pre>
* Auftrag toFirst()
* Nachher Der Positionszeiger steht auf dem ersten Listenelement.
* Falls die Liste leer ist befindet er sich jetzt hinter der Liste.
* </pre>
*/
public void toFirst()
{
this.current = this.first;
this.before = false;
this.behind = this.isEmpty();
}
/**
* Setzt das aktuelle Listenelement auf das letzte zurück.<br>
* <br>
*
* <pre>
* Auftrag toLast()
* Nachher Der Positionszeiger steht auf dem letzten Listenelement.
* Falls die Liste leer ist befindet er sich jetzt vor der Liste.
* </pre>
*/
public void toLast()
{
this.current = this.last;
this.behind = false;
this.before = this.isEmpty();
}
/**
* <pre>
* Auftrag update (Object pObject)
* Vorher Die Liste ist nicht leer. Der Positionszeiger steht nicht vor oder
* hinter der Liste.
* Nachher Der Wert des Listenelements an der aktuellen Position ist durch pObject
* ersetzt.
* </pre>
*
* @param pObject neuer Wert des Listenelements
*/
public void update(Object pObject)
{ // Die Liste ist nicht leer. Der Positionszeiger steht nicht vor oder hinter der
// Liste.
if (!this.isEmpty() && !this.before && !this.behind)
{ // Die Liste ist nicht leer. Der Positionszeiger steht nicht vor oder hinter der Liste.
this.current.setItem(pObject);
}
}
}
////////////////////////////////// Basisklasse ListElement /////////////////////////////////
import java.io.Serializable;
/**
* Datei ListElement.java (Klasse Listelement mit generalisiertem Datentyp Object).<br>
* <br>
* Die Klasse ListElement ist die '''Basisklasse für doppelt verkette Listen'''.<br>
* <br>
* Ein ListElement enthält eine Date, einen Verweis auf den Vorgänger und einen Verweis
* auf den Nachfolger. <br>
*
* Die Klasse ist wegen der Speicherbarkeit der Oberklasse serialisiert.<br>
* '''Die Klasse ist nicht Bestandteil des Zentralabiturs 2009, aber notwendig!!!'''
*
* @author <a href="mailto:schule@dinro.de">DiNaro</a>
* @version 1.0z+ 2006-09-11
*/
public class ListElement implements Serializable
{
/**
* Attribut dient zur Serialisierung.
*/
private static final long serialVersionUID = 8626283657638014888L;
/**
* Attribut Date des Listenelements.
*/
private Object item;
/**
* Attribut Nachfolger des Listenelements.
*/
private ListElement next;
/**
* Attribut Vorgänger des Listenelements.
*/
private ListElement previous;
/**
* Der Konstruktor erzeugt ein Listenelement mit Date, Vorgänger und Nachfolger.
*
* @param item Date des Listenelements.
* @param previous Vorgänger des Listenelements
* @param next Nachfolger des Listenelemente.
*/
public ListElement(Object item, ListElement previous, ListElement next)
{ this.item = item;
this.previous = previous;
this.next = next;
}
/**
* Gibt die Date des Elements zurück.
* @return Date des Listenelements.
*/
public Object getItem()
{ return this.item;
}
/**
* Gibt den Nachfolger des Listenelements zurück.
* @return Nachfolger des Listenelements.
*/
public ListElement getNext()
{ return this.next;
}
/**
* Gibt den Vorgänger des Listenelements zurück.
* @return Vorgänger des Listenelements.
*/
public ListElement getPrevious()
{ return this.previous;
}
/**
* Setzt die Date des Listenelements.
* @param item neue Date des Listenelements.
*/
public void setItem(Object item)
{ this.item = item;
}
/**
* Setzt den Nachfolger des Listenelements.
* @param next neuer Nachfolger des Listenelements.
*/
public void setNext(ListElement next)
{ this.next = next;
}
/**
* Setzt den Vorgänger des Listenelements.
* @param previous neuer Vorgänger des Listenelements.
*/
public void setPrevious(ListElement previous)
{ this.previous = previous;
}
}
Probleme mit der Implementierung
- Hier sind offene Fragen und Kommentare zusammengefasst.
- Aufruf zur Diskussion
Anwendungsbeispiele
- Quiz mit Hilfe einer Liste + Arbeitsblatt
- Liste mit Zahlen (Informatik)
Unterseiten zu List
{{{1}}}
