Der komplette Quelltext
Hier nun der komplette Quelltext. Die Kommentare wurden wortwörtlich aus den Materialien zum Zentralabitur NRW übernommen, der Java-Code wurde von mir selbst entwickelt. Sie können aber auch gern zum offiziellen Java-Code gehen, der vom Bildungsministerium NRW veröffentlicht wurde.
public class List
{
public class Knoten
{
Object wert;
Knoten nachfolger;
public Knoten(Object w, Knoten n)
{
wert = w;
nachfolger = n;
}
}
private Knoten first, last, act;
public List()
{
first = last = act = null;
}
/**
* Die Anfrage liefert den Wert true, wenn die Liste keine Objekte enthält,
* sonst liefert sie den Wert false.
*/
public boolean isEmpty()
{
return (first == null);
}
/**
* Die Anfrage liefert den Wert true, wenn es ein aktuelles Objekt gibt, sonst
* liefert sie den Wert false.
*/
public boolean hasAccess()
{
return (act != null);
}
/**
* 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 ((!isEmpty()) && (hasAccess()) && (act != last))
act = act.nachfolger;
else
act = null;
}
/**
* Falls die Liste nicht leer ist, wird das erste Objekt der Liste aktuelles
* Objekt. Ist die Liste leer, geschieht nichts.
*/
public void toFirst()
{
if (!isEmpty())
act = 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 (!isEmpty())
act = last;
}
/**
* Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das
* aktuelle Objekt zurückgegeben, andernfalls (hasAccess() == false)
* gibt die Anfrage den Wert null zurück.
*/
public Object getContent()
{
if (hasAccess())
return act.wert;
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 unverändert.
*/
public void setContent(Object x)
{
if ((hasAccess()) && (x != null))
act.wert = x;
}
/**
* Ein neues Objekt pObject wird am Ende der Liste eingefügt. Das aktuelle
* Objekt bleibt unverändert. Wenn die Liste leer ist, wird das Objekt
* pObject in die Liste eingefügt und es gibt weiterhin kein aktuelles Objekt
* (hasAccess() == false). Falls pObject gleich null ist, bleibt die Liste
* unverändert.
*/
public void append(Object x)
{
if (x != null)
{
Knoten neu = new Knoten(x,null);
if (isEmpty())
{
first = last = neu;
}
else
{
last.nachfolger = neu;
last = neu;
}
}
}
/**
* Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird ein neues
* Objekt vor dem aktuellen Objekt in die Liste eingefügt. Das aktuelle Objekt
* bleibt unverändert. Falls die Liste leer ist und es somit kein aktuelles Objekt
* gibt (hasAccess() == false), wird pObject in die Liste eingefügt und
* es gibt weiterhin kein aktuelles Objekt. Falls es kein aktuelles Objekt gibt
* (hasAccess() == false) und die Liste nicht leer ist oder pObject
* gleich null ist, bleibt die Liste unverändert.
*/
public void insert(Object x)
{
if (isEmpty())
{
first = new Knoten(x,null);
last = first;
act = null; // nur zur Verdeutlichung!
}
else if (hasAccess())
{
if (act == first)
{
Knoten neu = new Knoten(x,first);
first = neu;
}
else
{
Knoten help = first;
while (help.nachfolger != act) help = help.nachfolger;
help.nachfolger = new Knoten(x,act);
}
}
}
/**
* Die Liste pList wird an die Liste angehängt. Anschließend wird pList
* eine leere Liste. Das aktuelle Objekt bleibt unverändert. Falls pList null
* oder eine leere Liste ist, bleibt die Liste unverändert.
*/
public void concat(List pList)
{
last.nachfolger = pList.first;
last = pList.last;
pList.first = null;
pList.last = null;
pList = null;
}
/**
* Falls es ein aktuelles Objekt gibt (hasAccess() == true), wird das aktuelle
* Objekt gelöscht und das Objekt hinter dem gelöschten Objekt wird zum
* aktuellen Objekt. Wird das Objekt, das am Ende der Liste steht, gelöscht,
* gibt es kein aktuelles Objekt mehr (hasAccess() == false). Wenn die Liste
* leer ist oder es kein aktuelles Objekt gibt (hasAccess() == false),
* bleibt die Liste unverändert.
*/
public void remove()
{
// Fall 0: Liste ist leer oder es gibt kein aktuelles Element
if ( (isEmpty()) || (!hasAccess())) return;
// Fall 2: Liste besteht aus nur einem Element
if (first == last)
{
first = last = act = null;
return;
}
// Fall 3a: es soll vorne gelöscht werden
if (act == first)
{
act = act.nachfolger;
first = act;
return;
}
// Fall 3b: es soll hinten gelöscht werden
if (act == last)
{
Knoten help = first;
while (help.nachfolger != act) help = help.nachfolger;
help.nachfolger = null;
last = help;
return;
}
// Fall 4: es soll in der Mitte gelöscht werden
// Die Liste besteht aus mindestens drei Elementen
Knoten help = first;
while (help.nachfolger != act) help = help.nachfolger;
act = act.nachfolger;
help.nachfolger = act;
}
/**
* Eine rein interne show()-Methode, damit die Implementation der Liste
* auf Herz und Nieren getestet werden kann.
* Gehört nicht zu den offiziellen Methoden der Klasse Liste!
* Diese Methode funktioniert nur in Zusammenarbeit mit der Klasse Bruch,
* welche zum Testen der Liste erforderlich ist.
*/
public void show(String msg)
{
System.out.println("\n"+msg);
if (isEmpty()) return;
Knoten help = first;
while (help != null)
{
Bruch b = (Bruch) help.wert;
System.out.print(b.zaehler + "/" + b.nenner);
if (help == first) System.out.print(" <=== first");
if (help == last) System.out.print(" <=== last");
if (help == act) System.out.print(" <=== act");
System.out.println();
help = help.nachfolger;
}
}
}
Ausführliche Erläuterungen zu diesem Quelltext finden Sie, wenn Sie auf die einzelnen Methoden klicken.
Ich hoffe, dass ich keine Fehler in den Quelltext eingebaut habe, so ganz sicher ist man sich beim Arbeiten mit Referenzen ja nie. Mein Testprogramm hatte jedenfalls mit diesem Quelltext keine Probleme:
public class Test
{
List l;
public Test()
{
l = new List();
l.append(new Bruch(1,1)); l.append(new Bruch(1,2));
l.append(new Bruch(1,3)); l.append(new Bruch(1,4));
l.append(new Bruch(1,5)); l.append(new Bruch(1,6));
System.out.println();
l.show("Die ursprüngliche Liste:");
l.toFirst();
l.next();
l.next();
l.remove();
l.show("Das dritte Element wird gelöscht:");
l.toFirst();
l.remove();
l.show("Das erste Element wird gelöscht:");
l.toLast();
l.remove();
l.show("Das letzte Element wird gelöscht:");
l.toFirst();
l.remove();
l.show("Das erste Element wird gelöscht:");
l.toLast();
l.remove();
l.show("Das letzte Element wird gelöscht:");
l.toFirst();
l.remove();
l.show("Das erste Element wird gelöscht:");
l.toLast();
l.remove();
l.show("Das letzte Element wird gelöscht:");
}
}
Allerdings habe ich auch nicht alle Methoden ausführlich getestet, sondern nur append, toFirst, toLast, next und remove. Die Methoden insert und concat habe ich in einem zweiten Testprogramm erfolgreich getestet:
public class TestConcat
{
List l1,l2;
public TestConcat()
{
l1 = new List();
l1.append(new Bruch(1,1));
l1.append(new Bruch(1,2));
l1.append(new Bruch(1,3));
l1.append(new Bruch(1,4));
l1.append(new Bruch(1,5));
l1.show("Liste 1");
l1.toFirst();
l1.insert(new Bruch(1,7));
l1.show("Liste 1, nach toFirst() und insert(1/7)");
l1.toLast();
l1.insert(new Bruch(1,8));
l1.show("Liste 1, nach toLast() und insert(1/8)");
l2 = new List();
l2.append(new Bruch(2,1));
l2.append(new Bruch(2,2));
l2.append(new Bruch(2,3));
l2.append(new Bruch(2,4));
l2.append(new Bruch(2,5));
l2.show("Liste 2");
l2.toFirst();
l2.next();
l2.next();
l2.insert(new Bruch(2,7));
l2.show("Liste 2, nach toFirst(), 2 x next() und insert(2/7)");
l1.concat(l2);
l1.show("Liste 1 nach concat()");
l2.show("Liste 2 nach concat()");
}
}
Das will aber alles noch nichts heißen. Es kann ja immerhin sein, dass beispielsweise insert in diesem Testprogramm funktioniert, aber in einem anderen Testprogramm unter anderen Bedingungen nicht. Bei der Implementation von remove ist mir das nämlich so gegangen. Ich hatte nicht daran gedacht, dass das Löschen aus einer Liste, die nur aus einem Element besteht, ein Spezialfall ist.
Für Korrekturen und Verbesserungsvorschläge bin ich immer offen.
Zum Vergleich: der offizielle Quelltext der NRW-Liste.