Datenstrukturen und Algorithmen

Website:	Hamburg Open Online University
Kurs:	Programmieren mit Java
Buch:	Datenstrukturen und Algorithmen

Gedruckt von:	Gast
Datum:	Donnerstag, 21. November 2024, 14:35

Beschreibung

Hier gibt es einen Einstieg in die beiden Themen mit eigener Implementierung einer Single Linked List.

Single Linked List

Der Inhalt dieser Einheit soll einen Einstieg in die Themen Datenstrukturen und Algorithmen bieten. Als Beispiel wollen wir uns hierbei eine eigene Implementierung einer Single Linked List, also einer einfach verknüpften Liste, erstellen. Hierbei handelt es sich um eine Datenstruktur, die eine Reihe Elemente gleichen Types aufnehmen kann. Jedes Element beinhaltet hierbei zwei Werte. Der Eine ist die eigentlichen Information, die verarbeitet werden sollen, der zweite Wert ist die Information, welches Element als nächste folgt.

Der Vorteil einer Single Linked List gegenüber einem Array ist, dass beliebig Elemente angehängt werden können. Der Nachteil ist, dass man ein bestimmtes Element der Liste nur erreichen kann, indem man vom Anfang bis dort alle Elemente durchläuft. Man kann diese Art einer Liste nicht rückwärts durchlaufen.

In der Praxis würde man selten eine eigene Listen implementieren, weil Java bereits verschiedene sehr gute Implementierungen mitbringt. Wir wollen uns hier aber mit den Konzepten beschäftigen und darum nicht einfach nur eine fertige Bibliothek benutzen.

Klassen als Datenstruktur

In Java können Datenstrukturen nur in der Form von Klassen definiert werden. Klassen sind eigentlich ein zentraler Bestandteil der objektorientierten Programmierung, die nicht Bestandteil dieses Kurses sein soll. Darum wollen wir sie nur auf die aller einfachste Weise als eine Art Container benutzen.

Für unser Beispiel wollen wir eine Klasse “SingleLinkedList” erstellen, mit deren Hilfe wir Strings speichern können. Innerhalb der Klasse solles zwei Felder geben. Felder sind Variablen, die nicht nur in einer Methode gültig sind, sondern als eine Eigenschaft einer Instanz existieren. Sie werden darum auch innerhalb der Klasse, aber außerhalb von Methoden definiert. Wir wollen sie immer mit dem Schlüsselwort “public” definieren, so können wir von überall darauf zugreifen.

Wir beginnen damit, dass wir ein neues Java-Projekt in Eclipse erstellen mit dem Namen “Datenstrukturen”. Außerdem definieren wir die Klasse “SingleLinkedList”.


 public class SingleLinkedList {
     public SingleLinkedList next;
     public String data;
 }

Damit unser Projekt ausführbar wird, wollen wir auch gleich die Mainmethode ergänzen. Darin können wir dann auch eine Instanz unserer Liste erstellen und die verschiedenen Funktionen, die unsere Liste bekommen wird, testen.


 public class SingleLinkedList {
     public SingleLinkedList next;
     public String data;

     public static void main(String[] args) throws Exception {

         // unsere Liste
         SingleLinkedList planeten = null;
     }
 }

Die Grundfunktionen einer Liste

Um mit einer Liste von Daten sinnvoll arbeiten zu können, ist es wichtig, dass wir wenigstens Elemente hinzufügen, suchen und entfernen können. Dieser Funktionalität wollen wir jetzt erstellen. Um uns einfach ein Bild von der Liste machen zu können, soll zusätzlich eine Methode zum Ausgeben der Liste erstellt werden.

Es wird immer eine kurze Beschreibung der Eingaben und Ausgaben der Methoden geben, so dass eine informelle Beschreibung des Algorithmus gegeben ist. Ausgehend davon wird der Algorithmus dann implementiert.

Wir definieren, dass das letzte Element in einer Liste daran zu erkennen ist, dass die Eigenschaft next den Wert null hat.

Eine leere Liste soll durch null repräsentiert werden. Es ist wichtig, dass wir immer am Beginn einer Methode prüfen, ob wir es mit einer leeren Liste zu tun haben, da es sich hierbei um einen Sonderfall handelt.

Elemente hinzufügen

Die Funktion, mit der ein Element an unsere Liste angehängt wird, soll “wertHinzufuegen” heißen. Sie soll als Parameter ein Verweis auf eine Liste und den einzufügenden Wert bekommen. Zurückgeben wird sie den Verweis auf die Liste. Der Wert null soll nicht zu der Liste hinzugefügt werden. Er wird ignoriert.


 public static SingleLinkedList wertHinzufuegen(SingleLinkedList liste, String data) {

     // null soll nicht in der Liste vorkommen
     if(data == null) {
         return liste;
     }

     // Neuen Eintrag erstellen und Daten einfügen
     SingleLinkedList eintrag = new SingleLinkedList();
     eintrag.data = data;

     // Bei einer leeren Liste, wird eine neue Liste begonnen
     if(liste == null) {
         return eintrag;
     }

     // Wir suchen das Ende der Liste
     SingleLinkedList position = liste;
     while(position.next != null) {
         position = position.next;
     }

     // Eintrag am Ende anhängen
     position.next = eintrag;

     // Verweis auf Liste zurückgeben
     return liste;
 }

In diesem Beispiel wird zuerst geprüft, ob der neue Wert ungleich null ist, da er nur dann in die Liste aufgenommen werden darf. Dann wird ein neues Listenelement erstellt und die Daten eingefügt. Im dritten Schritt wird geprüft, ob es sich um eine leere Liste handelt. Dann würde der neue Eintrag zurückgegeben werden, als der Beginn einer neuen Liste.

Im vierten Schritt wird das Ende der Liste ermittelt. Hierfür wird eine temporäre Variable “position” verwendet und solange durch den nächsten Listeneintrag überschrieben, bis das Ende erreicht wird. Danach wird der neue Eintrag angefügt.

Wir können nun in unserer Main Methode die Liste der Planeten befüllen.


 public static void main(String[] args) throws Exception {

         // unsere Liste
         SingleLinkedList planeten = null;
         planeten = wertHinzufuegen(planeten, "Merkur");
         planeten = wertHinzufuegen(planeten, "Venus");
         planeten = wertHinzufuegen(planeten, "Erde");
         planeten = wertHinzufuegen(planeten, "Mars");
         planeten = wertHinzufuegen(planeten, "Jupiter");
         planeten = wertHinzufuegen(planeten, "Saturn");
         planeten = wertHinzufuegen(planeten, "Uranus");
         planeten = wertHinzufuegen(planeten, "Neptun");
         planeten = wertHinzufuegen(planeten, "Pluto");
     }

Liste ausgeben

Zum Ausgeben unserer Liste wollen wir eine Methode “listeAusgeben” erstellen, die als Parameter nur die Liste übergeben bekommt.


     public static void listeAusgeben(SingleLinkedList liste) {

        // Leere Liste erkennen und danach stoppen
        if(liste == null) {
            System.out.println("SingleLinkedList()");
            return;
        }

        // Listenanfang ausgeben
        System.out.print("SingleLinkedList(" + liste.data);

        // Liste durchlaufen
        while(liste.next != null) {
            liste = liste.next;
            System.out.print(", " + liste.data);
        }

        // Listenende ausgeben
        System.out.println(")");
    }

Wir müssen wieder den Sonderfall der leeren Liste zu Beginn prüfen und gegebenen Falls abbrechen. Danach können wir den Listenanfang und jedes weiter Element ausgeben. Hierfür eignet sich die System.out.print() Methode, da sie keinen Zeilenumbruch am Ende ausgibt.

Länge ermitteln

Um die Länge zu ermitteln benötigen wir eine Methode “laenge” die als Parameter eine Liste entgegen nimmt und die Anzahl der Elemente zurückgibt.


    public static int laenge(SingleLinkedList liste) {

        // Leere Liste erkennen und danach stoppen
        if(liste == null) {
            return 0;
        }

        // Elemente zählen
        int laenge = 1;
        while(liste.next != null) {
            liste = liste.next;
            laenge ++;
        }

        return laenge;
    }

Elemente finden

Für die Suche von Einträgen, in unserer Liste wollen, wir definieren, dass die Methode “suche” als Parameter die Liste und einen String, der gesucht werden soll, übergeben bekommt. Als Rückgabe erwarten wir den Wert -1 wenn der Wert nicht enthalten ist und sonst die Position. Wie bei Arrays soll das erste Element die Position 0 haben.

    
 public static int suche(SingleLinkedList liste, String suchwort) {

        // Leere Liste erkennen und danach stoppen
        if(liste == null) {
            return -1;
        }

        // Leres Suchwort behandeln
        if(suchwort == null) {
            return -1;
        }

        // Element suchen
        int position = 0;
        while(liste.next != null) {
            if(suchwort.equals(liste.data)) {
                return position;
            }
            liste = liste.next;
            position ++;
        }

        return -1;
    }

Wir prüfen wieder als Erstes ab, dass keiner der Parameter null ist. Falls doch wird die Liste unverändert zurückgegeben. Als Nächstes behandeln wir den Sonderfall, dass der Wert vom Anfang der Liste entfernt werden muss. Hier reicht es den hinteren Teil der Liste zurück zu geben.

Am darauf folgenden Abschnitt wird nach dem Wert gesucht, der entfernt werden soll. Leider kann man in dieser Datenstruktur nur vorwärts laufen und man benötigt den Vorgänger eines Elements um das Element zu entfernen. Darum wird immer geprüft, ob das nächste Element den gesuchten Wert hat. Wenn ja, wird dessen Nachfolger als Nachfolger des aktuellen Elements gesetzt. Hierdurch fällt der Wert aus der Liste heraus.

Iterativ vs Rekursiv

Im vorherigen Abschnitt haben wir schon eine Reihe kleiner Algorithmen umgesetzt, damit wir mit unserer Single Linked List arbeiten konnten. Dabei haben wir uns ausschließlich auf iterative Ansätze beschränkt. Das heißt, dass wir die Liste immer nur mit hilfe von Schleifen abgelaufen sind. Als Beispiel hierzu noch einmal die Methodendefinition von “laenge”.


    public static int laenge(SingleLinkedList liste) {

        // Leere Liste erkennen und danach stoppen
        if(liste == null) {
            return 0;
        }

        // Elemente zählen
        int laenge = 1;
        while(liste.next != null) {
            liste = liste.next;
            laenge ++;
        }

        return laenge;
    }

Bei einer rekursiven Umsetzung würde eine Methode sich selbst wieder aufrufen um einen Teil des Problems darin zu lösen und diese Teillösung dann in ein Ergebnis zusammenzufügen.

Unsere Beispielfunktion könnte mit Hilfe von Rekursion wie folgt umgesetzt werden.



    public static int laenge(SingleLinkedList liste) {

        if(liste == null) {
            return 0;
        } else {
            return laenge(liste.next) + 1;
        }
    }

Es ist leicht zu sehen, dass der rekursive Ansatz bei diesem Problem mit weniger Schreibarbeit umgesetzt werden kann. Das ist nicht in jedem Fall so. Auch ist in diesem Fall die iterative Implementierung sicherlich vom Laufzeitverhalten sicherlich besser. Es gibt aber Problemstellungen, die sich in nach dem einen oder anderen Verfahren wesentlich besser umsetzen lassen.