Beliebiges Element in einer Liste löschen (Java)(Lineare Datenstrukturen)

[V_Fynn03]

Die Aufgabe lautet, dass wir ein beliebiges Element in einer Liste löschen können. Ich habe auch schon einen Ansatz. Doch ich komme jetzt leider nicht mehr weiter. Ich kann bisher nur das erste und letzte Element löschen. Doch noch keines in der Liste. Also das Dummy läuft durch die Queue bis zum vorletzten Element. Wenn nun der gesuchte Content mit dummy.getNext() übereinstimmt, dann soll gelöscht werden. Ich habe es auch schon so versucht zu programmieren aber irgendwie krieg ich es nicht ganz so hin, wie ich es mir vorgestellt habe.


Ist etwas in meiner Logik falsch oder etwas wie ich es programmiert habe? Kann mir wer helfen das weiter so zu programmieren? Danke

public void delete(String s) {
        Node dummy = first;
        Node last = getLast();
        Node nach = getNext();

        if(s.equals(first.getContent())) {
        delete();
        }
        else if(getLast().getContent().equals(s)) {
          delete();
        }
        
        while(!(dummy.getNext().getContent().equals(s))) {
            delete();
            dummy=dummy.getNext();
        }
        dummy.setNext(dummy.getNext().getNext());

    }

 

[kneitzel]

Also der Code sieht sehr dubios aus. Ohne genaue Details werden wir aber nur raten können.
Wie ist die Liste aufgebaut? Was macht delete()?

Also generell macht es keinen Sinn: egal ob das erste oder letzte Element das zu löschende ist: delete wird aufgerufen.
Und so lange das gesuchte Element nicht das gesuchte ist, rufst du delete auf?

Also bring erst einmal die Details der Liste, die gegeben ist. Und dann beschreib erst einmal in Worten, was du machen musst um ein Element zu finden und zu löschen.

 

[V_Fynn03]

Also die Methode zu delete ist:

public void delete() {
        first = first.getNext();

    }

Was für Details brauchst du denn genau? s ist ja quasi dass was man eingibt um das zu löschen. Und die Queue soll halt so lange durchgelaufen werden (dummy.getNext().getContent()) bis es eine Übereinstimmung mit s gibt. Dann soll delete() ausgeführt werden. Dummy durchläuft quasi die Queue bis zum vorletzten Element, wenn keine Übereinstimmung gefunden ist. Die ersten Methoden sind ja dafür da um jeweils das erste (first.getContent()) und das letzte Element (getLast()) zu löschen wenn das gesuchte an eben diesen Stellen ist. Ab der while Schleife geht es dann darum ein Element was in der Liste drinnen liegt zu löschen. Bitte korrigiere mich wenn meine Logik nicht stimmt, aber ich weiß nicht wie ich weiter vorgehen soll und was ich bisher vlt schon falsch gemacht habe.

 

[kneitzel]

Node wäre interessant. Es handelt sich vermutlich um eine einfach verkettete Liste, aber das wäre schon interessant um das zu bestätigen.

Beschreib doch einmal mit eigenen Worten, was delete genau macht?
Und dann beschreib einmal in eigenen Worten aber sehr detailliert, wie du vorgehen musst, um ein Element zu löschen.
Derzeit dürfte nur das Löschen des ersten Elementes funktionieren.... der Rest des Codes ist so nicht korrekt, aber vergiss das einfach erst einmal. Wir fangen in Ruhe mit der Beschreibung des notwendigen Algorithmus an....

Du hast also eine Liste wie
a -> b -> c -> d -> null
First zeigte auf a.
Last zeigt auf d.
Wie löscht du das a?
wie würdest du b, c oder d löschen?

 

[V_Fynn03]

a lösche ich indem indem ich den ersten Pfeil auf das Element danach richte, sodass kein Pfeil mehr auf a zeigt und somit nicht mehr in der Liste ist. Also das erste Element ist nun das zweite (first=first.getNext()). So in der while Schleife läuft das Dummy nun Element für Element durch die Queue. Es holt sich quasi immer das nächste (dummy.getNext().getContent()) bis irgendwann dieser Inhalt mit dem gesuchten übereinstimmt. Wenn jetzt in c der gesuchte Content ist dann holt sich das Dummy erstmal den Content von a vergleich mit dem gesuchten und geht weiter wenn es nicht übereinstimmt, und das geht dann bis c wo es dann übereinstimmt. Wenn das der Fall ist dann soll delete() ausgeführt werden.

 

[kneitzel]

Beschreibe doch einmal mit eigenen Worten, was "delete()" genau macht.

Den Code hast Du mit:

public void delete() {
        first = first.getNext();
}

angegeben....

Und unabhängig davon: Bitte vergiss delete() bei Beschreibungen. Beschreibe genau, was getan werden soll.

Beim ersten Element hast Du korrekt gesagt:
first wird auf first.next gesetzt. Damit wird auf a nicht mehr gezeigt und a ist damit nicht mehr in der Liste.
(Das ist ja genau, was delete() macht. Also was macht das delete()? Welches Element wird bei delete gelöscht? Wie sollte man delete besser umbenennen? Sowas wie deleteXXXXXX schwebt mir vor...)

Bei c müssen wir was machen? ein first = first.next schmeisst das a raus aus der Liste. Das wollen wir aber doch nicht. c soll aus der Liste geschmissen werden. Also darf nichts mehr auf c zeigen. Was zeigt denn auf c? Und wohin muss das statt dessen zeigen?

 

[V_Fynn03]

Ok wenn c erreicht wird, dann soll der Pfeil vom Element vor c auf das Element nach c zeigen. Heißt ja eigentlich dass ich eine neue delete Methode schreiben müsste extra dafür oder? Sowas wie c = c.getNext() sodass der Pfeil vom Element davor auf das Element nach c zeigt oder?

 

[kneitzel]

Nicht ganz, aber fast. Aber du brauchst eine Referenz auf den Vorgänger. Und dann kannst Du vorgänger.next = current.next schreiben.

Also in der while schleife gehst Du so lange weiter, bis Du entweder am Ende angekommen bist (next ist null) oder der gesuchte wert gefunden wurde.
In der Schleife ist dann halt vorgaenger = current und current = current.next.

Nach der Schleife schaust du, ob current auf den gesuchten Wert zeigt um diesen dann zu löschen.

 

[V_Fynn03]

Danke, aber ich verstehe es nicht so ganz, muss ich jetzt eine neue delete Methode schreiben? Und wenn ja wie? Es tut mir ehrlich leid vom logischen und inhaltlichen her verstehe ich es ja, aber ich weiß nicht wo ich jetzt was niederschreiben soll. Muss ich jetzt noch was in der while Schleife ändern?
Ich verlange ja nicht dass du jetzt meinen Quelltext umschreiben sollst, aber wie dekliniere ich jetzt vorgänger und current? Wie lass ich die Methode wissen was vorgänger und current ist?

 

[kneitzel]

Also Du hast doch bereits eine Methode, die das Element löschen soll:
public void delete(String s) {

Und wir haben jetzt (mehr oder weniger deutlich) folgenden Pseudocode erarbeitet:
Ist das gesuchte Element das erste Element? -> Setze Zeiger auf erstes Element um.
Wir brauchen Vorgänger (first) und Current (Nachfolger von first).
So lange wie Current nicht null ist und Current nicht den Wert enthält, der gesucht wird:
-> Vorgänger wird Current
-> Current wird Nachfolger von Current.
Nach dieser Schleife ist eines der zwei Abbruchkriterien erfüllt.
Current ist null -> Das Element ist nicht in der Liste vohanden!
Current ist nicht null -> Wir haben jetzt Vorgänger und Current und können den Nachfolger von Vorgänger umsetzen.

Dies ist der Pseudocode, den Du immer als ersten Schritt im Detail selbst erarbeiten solltest. Und dazu das auf einem Zettel durchspielen und sozusagen selbst Computer spielen. Was würdest Du machen und was brauchst Du? Da meiste ist 08/15:
- Mit einer Laufvariable durch die Liste gehen. Das kommt regelmäßig.
- Wenn Du damit aber das Element gefunden hast merkst Du: Du brauchst den Vorgänger. Da Du da halt keinen Pfeil zurück hast, musst Du damit nun schauen, wie Du weiter kommen kannst:
a) Du kannst wie ich einfach den Vorgänger merken. Das ist meist der Weg, den ich bevorzuge.
b) Du kannst current einfach auf den Vorgänger setzen. Damit verschiebst Du alles etwas und damit ändert sich aber natürlich die Schleife:
-> aus current wird der Nachfolger von current
-> aus dem Wert von Current wird der Wert vom Nachfolger von current.
-> Der gesuchte Wert wird also immer im Nachfolger geprüft. Wenn der Wert da gefunden wird, habe ich in current den Vorgänger, das gesuchte Elemente ist der Nachfolger von Current und somit kann ich auch wieder alles machen....

Aus meiner Sicht solltest Du mehr üben, mit diesen abstrakten Datentypen auf einem Zettel zu arbeiten.