Inhalt dieser Seite
Projektidee
Wir wollen eine dynamische Liste von int-Zahlen programmieren, in der die Zahlen gleich beim Einfügen aufsteigend einsortiert werden. Hier ein Beispiel:
Vor dem Einfügen bestand die Liste aus vier sortierten Zahlen, nach dem Einfügen der 7 besteht sie aus fünf sortierten Zahlen, und die 7 wurde korrekt zwischen die 5 und die 9 eingefügt.
Grundüberlegung zum Einfügen
Schauen wir uns das Einfügen der Zahl 7 mal konkreter an, dabei konzentrieren wir uns um das sogenannte "Zeigerumbiegen", wie die Informatiker es nennen.
Schritt 1: neuen Knoten erzeugen
Zunächst wird das neue Element mit der 7 erzeugt. Dazu legen wir einen Hilfszeiger neu an, der auf Objekte der Klasse Node zeigt. Mit
Node neu = new Node(7);
erzeugen wir dann einen neuen Knoten mit dem Wert 7. Allgemein würde man im Quelltext der Klasse natürlich schreiben:
Node neu = new Node(x);
wobei x der Parameter ist, der der Methode zum Einfügen übergeben wird. Der next-Zeiger des Knoten hat den Wert null.
Schritt 2: Einfügeposition finden
Jetzt muss die Einfügeposition für den neuen Knoten gefunden werden. In unserem Beispiel muss der Knoten zwischen der 5 und der 9 eingefügt werden. Der Hilfszeiger pos zeigt dann auf die 5, die sich vor der Einfügeposition befindet. Wie das Suchen der Einfügeposition genau erfolgt, wird weiter unten ausgeführt.
Schritt 3: Verknüpfen, Teil 1
Im Schritt 3 wird dann der next-Zeiger des neuen Knotens auf den Knoten mit dem Wert 9 gesetzt. Gespeichert ist die Adresse dieses Knotens im next-Zeiger des Elementes 5, auf das der Hilfszeiger pos gerade zeigt.
Der folgende Java-Quelltext zeigt, wie man das neue Element mit der bisherigen Liste korrekt verbindet:
neu.next = pos.next;
Der Hilfszeiger pos zeigt auf das Element 5, und der next-Zeiger von 5 zeigt auf die 9. Daher zeigt pos.next ebenfalls auf die 9, und mit neu.next = pos.next wird der next-Zeiger des neu hinzugefügten Elements auf den richtigen Nachfolger gesetzt, nämlich die 9.
Hier das Ganze noch einmal als Graphik, die beiden wichtigen Zeiger neu.next und pos.next sind hier hervorgehoben:
Schritt 4: Verknüpfen, Teil 2
Der Nachfolger des Elementes 5 ist immer noch das Element 9. Das muss jetzt geändert werden; die 5 muss auf das neue Element 7 verweisen. Das könnte mit dem Java-Quelltext
pos.next = neu;
geschehen.
Finden der Einfügestelle Seitenanfang
Wie kann man nun die Stelle finden, an der der neue Knoten in die bereits bestehende Liste eingefügt wird? Man muss die Liste von vorne nach hinten durchgehen, bis man ein Element findet, dessen Wert größer ist als der Parameter x. In unserem Beispiel muss man also ein Element finden, dessen Wert größer ist als 7.
Folgende Konstruktion würde dies ermöglichen:
Node pos = first; while (pos.next.value <= x) pos = pos.next;
Spielen wir die Schleife einmal durch. Zunächst zeigt pos auf die 3, und pos.next.value hat den Wert 5. Weil die Bedingung 5 <= 7 erfüllt ist (true) wird der Zeiger um ein Element weiter gesetzt. Also zeigt pos jetzt auf die 5. Da die Bedingung 9 <= 7 nicht erfüllt ist (false), wird pos nicht mehr weiter gesetzt und bleibt auf dem Knoten mit der 5 stehen.
Einfügen ganz vorne oder ganz hinten Seitenanfang
Einfügen ganz vorne
Angenommen, wir wollen die Zahl 2 in die Liste einfügen.
Die while-Schleife, die wir eben besprochen haben, würde nicht funktionieren. Die Schleifenbedingung lautet: pos.next.value <= x. Da wir pos vorher auf first gesetzt hatten, hat pos next.value den Wert 5, während das neue Element den Wert 2 hat. Also ist die Bedingung pos.next.value <= x nicht erfüllt, und pos würde auf der 3 stehen bleiben. Dann wäre aber die Anweisung
pos.next = neu;
völlig falsch, weil die 2 hinter der 3 eingefügt würde und nicht vor der 3.
Außerdem muss der Zeiger first auf das neue Element gesetzt werden, was auch nicht passiert, wenn wir den Quelltext von eben verwenden.
Wir müssen also eine Fallunterscheidung in die inser()-Methode einbauen. Für den Fall, dass die Bedingung x < first.value gilt, müssen folgende Zeilen ausgeführt werden:
neu.next = first; // Schritt 2 first = neu; // Schritt 3
Einfügen ganz hinten
Es kann auch sein, dass das neue Element größer ist als das letzte Listen-Element. In diesem Fall würde die while-Schleife von oben einen Laufzeitfehler melden, wenn nämlich nach pos.next.value gefragt wird und pos auf das letzte Element zeigt. Der Nachfolger des letzten Elementes ist null, und null hat keine Komponente next und erst recht keine Komponente next.value.
Also muss dieser Fall verhindert werden, indem vorher geprüft wird, ob das neue Element größer ist als das letzte. Dabei ist es sinnvoll, neben dem Zeiger first auch einen Zeiger last zu verwalten, der stets auf das letzte Element der Liste zeigt. Es ginge auch ohne einen solchen Zeiger, aber dann müsste man eine Subroutine schreiben, die immer wieder bei first startet und einen Hilfszeiger solange nach rechts bewegt, bis er auf das letzte Element zeigt.
last.next = neu; last = neu;
Mit diesen beiden Zeilen könnte man beispielsweise die Zahl 15 in die vorhandene Beispiel-Liste einfügen.
Und wenn die Liste leer ist? Seitenanfang
Wenn die Liste noch leer ist, wenn also die Bedingung first == null sowie die Bedingung last == null gilt, dann ist das Einfügen recht einfach:
first = neu; last = neu;
Der next-Zeiger von neu kann weiterhin auf null zeigen, denn das ist ja bei einer Liste, die aus nur einem Element besteht, korrekt.
Jetzt gibt es noch eine Sache zu bedenken. Schauen wir uns noch einmal die while-Schleife an, mit der ein Element mitten in die Liste eingefügt wird:
Node pos = first; while (pos.next.value <= x) pos = pos.next;
Wenn die Liste aus nur einem Element besteht, zeigt pos auf dieses Element. Der next-Zeiger dieses Elementes hat aber den Wert null, also existiert pos.next.value nicht, und ein Laufzeitfehler wäre zu erwarten. Aber ein solcher Fehler sollte nicht eintreten. Warum nicht?
Angenommen, die Liste besteht tatsächlich nur aus einem Element. Dann ist das neu einzufügende Element entweder kleiner als das einzige Element, oder es ist nicht kleiner.
Es wird also auf jeden Fall vor oder hinter dem ersten und einzigen Element eingefügt. Danach besteht die Liste aus zwei Elementen, und pos.next.value hat einen Wert, wenn pos auf das erste Element zeigt.
Der komplette Quelltext der sortierten dynamischen Liste Seitenanfang
Vorüberlegung zur Reihenfolge der Fallunterscheidungen
Zunächst muss geprüft werden, ob die Liste leer ist. Ist dies nicht der Fall, muss getestet werden, ob das neue Element vor dem ersten oder hinter dem letzten Element eingefügt werden muss. Ist auch dies nicht der Fall, kann die while-Schleife zum Suchen der Einfügeposition aufgerufen werden, anschließend wird das neue Element in die Liste eingefügt.
Quelltext der Klasse List
Der folgende Quelltext wurde mit BlueJ entwickelt aus ausgiebig getestet. Hier zunächst der Quelltext der Klasse Liste. Als Listen-Elemente werden Objekte der Klasse IntNode verwendet; die Werte dieser Knoten sind ganze Zahlen.
public class List
{
IntNode first, last;
public List()
{
first = last = null;
}
public void insert (int x)
{
IntNode neu = new IntNode(x,null);
// Liste noch leer?
if (empty())
{
first = neu;
last = neu;
}
// eventuell vorne einfuegen?
else if (x < first.value)
{
neu.next = first;
first = neu;
}
// oder hinten anhaengen?
else if (x >= last.value)
{
last.next = neu;
last = neu;
}
// oder mitten drin einfuegen
else
{
IntNode pos = first;
while (pos.next.value < x) pos = pos.next;
neu.next = pos.next;
pos.next = neu;
}
}
public boolean empty()
{
return first == null;
}
public void show()
{
IntNode pos = first;
while (pos != null)
{
System.out.println(pos.value);
pos = pos.next;
}
}
}
Quelltext der Klasse Test
Da das Testen dieser Klasse recht aufwändig wäre, wenn man den Objekt-Inspektor von BlueJ verwenden würde, wurde eine Testklasse geschrieben, deren Quelltext so aussieht:
import java.util.Random;
public class Test
{
List testList;
Random rand = new Random();
public Test()
{
testList = new List();
for (int i=0; i<30; i++)
testList.insert(rand.nextInt(100));
testList.show();
}
}
Hier werden 30 Zufallszahlen erzeugt und in die Liste eingefügt. Danach wird die Liste ausgegeben.