Home > Informatik > Stufe Q1 > Referenzen

15.3 Projekt "Sortierte Liste"

Allgemeines - dynamischer Stack - sortierte Liste - NRW-Liste - doppelt verkettete Liste

Projektidee

Wir wollen eine dynamische Liste von int-Zahlen programmieren, in der die Zahlen gleich beim Einfügen aufsteigend einsortiert werden. Hier ein Beispiel:

Einfügen der Zahl 7 in die Liste 3 - 5- 9 - 12 führt zu 3 - 5 - 7 - 9 - 12

Vor dem Einfügen bestand die Liste aus vier sortierten Zahl, nach dem Einfügen der 7 besteht sie aus fünf sortierten Zahlen.

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.

Das Einfügen im Kästchenschema - vier Schritte
Schritt 1: neuen Knoten erzeugen

Zunächst wird das neue Element mit der 7 erzeugt. Der dazu gehörige Java-Quelltext könnte so aussehen:

Node neu = new Node(x);

Dabei ist Node die Klasse, welche für die einzelnen Knoten oder Elemente der Liste zuständig ist, und x ist der Parameter, der der Methode insert übergeben wird. Der Konstruktor von Node legt einen neuen Knoten an, dessen Wert dann x entspricht und dessen Nachfolger auf null zeigt.

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 Nachfolger-Zeiger des neuen Knotens auf den Knoten mit dem Wert 9 gesetzt. Das könnte mit folgendem Java-Quelltext geschehen:

neu.next = pos.next;
Schritt 4: Verknüpfen, Teil 2

Der Nachfolger der 5 ist immer noch die 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. Wegen der Bedingung 5 <= 7 wird der Zeiger um ein Element weiter gesetzt. Also zeigt pos jetzt auf die 5. Da die Bedingung 9 <= 7 nicht erfüllt ist, 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.

Einfügen ganz vorne im Kästchenschema

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 insert-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 x = 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 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.