Java/List

Aus ZUM-Unterrichten

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

Anwendungsbeispiele

Unterseiten zu List

{{{1}}}


Siehe auch