Einfach verkettete Liste: Wie Elemente löschen?

[titus]

Ich habe den unten stehenden Code aus einer Übung, den ich geringfügig erweitert habe, was aber so wenig ist, dass es nicht nennenswert ist.

Nun habe ich die setNext()-Methode in der ListElem-Klasse dazu geschrieben, da sie zwar im Quellcode erwähnt wird, aber in meinen Unterlagen kurioserweise fehlt. Allerdings habe ich noch nicht prüfen können, ob meine Idee so funktioniert, denn es gibt ein anderes Problem ...

Wie lösche ich in so einer Liste ein Element? Ich bin völlig ratlos!

1. Ich vermute, dass ich die Liste komplett durchlaufen muss, z.B. mit einer FOR-Schleife, wie ich es in den Zeilen 91 bis 96 versuche - richtig?
2. Irgendwie muss ich ja angeben können, WAS gelöscht werden soll. Da war ich etwas ratlos, dachte mir aber, dass ich das in einer Object-Variable definieren könnte.

Aber dann... . Wie kann ich in der main-Klasse/-Methode nun die Liste nach dem zu löschenden Element durchlaufen? Eine Suche via FOR-Schleife, wie in der print()-Anweisung kann ich ja nicht durchführen, da ich ja nicht auf m_Head zugreifen kann.

Kann mir jemand bitte helfen?

package singlelist;

class SingleList {
    private ListElem m_Head;    // Anfang der Liste

    // Der Listen-Konstruktor ...
    public SingleList() {
        m_Head = null;  // ... erwartet kein Argument.
    }

    // Durchlauf und Ausgabe aller Elemente
    public void print() {
        /* Die Liste wird so lange durchlaufen, bis das letzte Element erfasst
         * und ausgegeben wurde - eben so lange, so lange elem != NULL ist. */
        for (ListElem elem = m_Head; elem != null; elem = elem.getNext()) {
            System.out.println(elem.getElement() + "\t");
        }
    }

    // Fügt ein Element in die Liste ein
    public void addElement(Object obj) {
        /* Das 1. Element ist das kürzlich eingefügte Element. Ein Nachfolger-
         * Element existiert nicht, folglich ist es sein eigener Nachfolger. */
        m_Head = new ListElem(obj, m_Head);
    }

    void deleteElem(ListElem pElem2Delete) {
        // Soll überhaupt ein Element gelöscht werden UND ist sie NICHT leer?
        if (pElem2Delete != null && m_Head != null) {
            // Soll das Start-Element gelöscht werden?
            if (m_Head == pElem2Delete) {
                // Setze das nächste Element als Start-Element
                m_Head = pElem2Delete.getNext();
            }
            else {
                for (ListElem tmp = m_Head; tmp != null; tmp = tmp.getNext()) {
                    ListElem tmpNext = tmp.getNext();Seite 1 von 40
                    /* Überprüft ob das nächste Element gelöscht werden soll.
                     * Dies ist nötig, um nach dem Löschen des jeweiligen
                     * Elements eine Verbindung zwischen dessen Nachfolger und
                     * dessen Vorgänger herstellen zu können. */
                    if (tmpNext == pElem2Delete) {
                        /* Falls ja, so wird der Zeiger vom Vorgänger des zu
                         * löschenden Elements auf dessen Nachfolger gesetzt */
                        tmp.setNext(tmpNext.getNext());
                        return; // ... und die Methode verlassen.
                    }
                }
            }
        }
    }

    // implementiert ein Listen-Element
    class ListElem {
        // Ein Listen-Element merkt sich ...
        private ListElem m_Next; // ... den Verweis auf das nächste Element ...
        private Object   m_Elem; // ... und das Element.

        // Der Konstruktor des Listen-Elements erwartet ...
        public ListElem(Object obj, ListElem next) {
            m_Next = next;  // ... den Verweis auf das nächste Element ...
            m_Elem = obj;   // ... und das zu speichernde Element.
        }

        // Liefert ein Element aus der Liste
        public Object getElement() {
            return m_Elem;
        }

        // Liefert den Verweis auf das nächste Element
        public ListElem getNext() {
            return m_Next;
        }

        public void setNext(ListElem next) {
            this.m_Next = next;
        }
    }
}

public class Main {
    public static void main(String[] args) {
        SingleList sl = new SingleList();   // Legt die Liste sl an
        // Fügt 200 Elemente in die Liste ein
        for (int i = -100; i < 100; ++i) {
            sl.addElement(new Integer(i));
        }
        // Druckt die Liste aus
        sl.print();

        Object elem2find = 10;

        for (SingleList.ListElem elem = SingleList.m_Head; elem != null; elem = elem.getNext()) {
            if (elem.getElement() == elem2find)
            sl.deleteElem(elem);
        }
    }

}

 

[titus]

Hat keiner eine Idee?

Ich hatte mir dann noch folgendes überlegt ...

Ich schreibe in der Klasse SingleList eine Methode, die ein Element sucht. Dort kann ich ja problemlos auf die Variable m_Head zugreifen und die Liste durchlaufen/durchsuchen. ...

class SingleList {
[...]

    public ListElem findElement(Object obj) {
        for (ListElem tmp = m_Head; tmp != null; tmp = tmp.getNext()) {
            System.out.println("DEBUG: " + tmp + ": " + tmp.getElement() + "; obj: " + obj);
            if (tmp.getElement() == obj) {
                System.out.print("GEFUNDEN!! :o)");
                return tmp;
            }
        }
        return null;
    }
}

...

Nun kann ich in der main ein Element definieren, nach dem gesucht werden, z.B. das erste Element mit dem Inhalt -100, das in die Liste Eingetragen wird. Wenn es gefunden wird, dann übergebe ich es später an die Methode, die für das löschen zuständig ist.

        Object elem2find = -100;
        sl.findElement(elem2find);

Das Problem ist jetzt nur, dass, obwohl die Inhalte miteinander verglichen werden und wie man in der Ausgabe sieht, auch gleich sind, diese nicht als gleich erkannt werden. Folglich kann die Such-Methode nix finden. Hat jemand eine Idee, woran das liegt? Liegt es an den beiden unterschiedlichen Datentypen ListElem und Object?

 

[AmunRa]

objekte vergleicht man mit equals und nicht mit '=='

 

[HLX]

Für einen inhaltlichen Vergleich musst du über die Methode equals(Object) vergleichen. Du vergleichst mit "==". Dabei wird lediglich überprüft, ob die gleiche Objektreferenz vorliegt.

 

[titus]

Wieder was dazu gelernt! Ich danke euch!