Datenstrukturen und Algorithmen

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.