Doppelt verkette Liste Element löschen

[okayjetztgehts]

Hallo, habe eine doppelt verkette Liste.

Diese wurde manuell erstellt.

Nun möchte ich, in einer Methode, ein Element löschen und das Datenelement des gelöschen Elements zurück geben.

Wenn der Stapel leer ist, soll eine Nullreferenz returnt werden, wenn nicht soll das Datenelement des ersten Elements der Liste zurückgegeben werden. Aber zuvor muss ich natürlich das listenelement aus der Liste entfernen, indem ich die Referenzen des vorhergehenden und des nachfolgenden Elements auf das zu löschende Element anpasse.

Wie mache ich das?

Das einfügen am Anfang mache ich beispielsweise so und das klappt:

public void hinzufuegen(elementinhalt omn ){
    Element_der_Liste neuesele = new LElement_der_Liste(omn);
    neuesele.next = kopf.next;
    neuesele.prev = kopf;
    neuesele.next.prev = neuesele;
    kopf.next = neuesele;
    }

Wie kann ich aber ein Element löschen?

Ich soll vorher noch prüfen, ob der Stapel leer ist... Was ist denn mit Stapel gemeint ?

 

[kneitzel]

Ich soll vorher noch prüfen, ob der Stapel leer ist... Was ist denn mit Stapel gemeint ?

Vermutlich sollst Du prüfen, ob die Liste leer ist. Das ist halt ein Spezialfall der geprüft werden muss.

Und bezüglich des Löschen eines Elements: Überleg es Dir doch bildlich:

Stell dir einen Zug vor. Du hast lauter Waggons, die aneinander gekoppelt sind: Der vordere Waggon ist an den hinteren gehakt und der hintere an den Vorderen.

Wenn Du jetzt drei Waggons hast und du den in der Mitte heraus nimmst: Welche Kupplungen sind betroffen und was ist an welchen Waggon gekoppelt?

Wenn Du am Ende bist, dann hast Du nur zwei Waggons und der letzte wird heraus genommen: Was ändert sich dann?

Diese bildliche Vorstellung musst Du im Detail durchgehen und dann kannst Du dies in Java umsetzen.

 

[okayjetztgehts]

Vermutlich sollst Du prüfen, ob die Liste leer ist. Das ist halt ein Spezialfall der geprüft werden muss.

Und bezüglich des Löschen eines Elements: Überleg es Dir doch bildlich:

Stell dir einen Zug vor. Du hast lauter Waggons, die aneinander gekoppelt sind: Der vordere Waggon ist an den hinteren gehakt und der hintere an den Vorderen.

Wenn Du jetzt drei Waggons hast und du den in der Mitte heraus nimmst: Welche Kupplungen sind betroffen und was ist an welchen Waggon gekoppelt?

Wenn Du am Ende bist, dann hast Du nur zwei Waggons und der letzte wird heraus genommen: Was ändert sich dann?

Diese bildliche Vorstellung musst Du im Detail durchgehen und dann kannst Du dies in Java umsetzen.

Genau ich habe mir gedacht ich nehme den Head und sage schaue nun auf das zweite Element was nach dir kommt un dnicht mehr das erste ELement, also
head.next=head.next.next
danach sollte das erste Element gelöscht sein oder? Weil der HEad zeigt ja nicht mehr aufs erste Element.


Genau ich soll prüfen ob die Liste leer ist, aber was ist damit gemeint? Soll ich jedes Lsitenelement einzeln prüfen?

 

[kneitzel]

danach sollte das erste Element gelöscht sein oder?

Nein, das reicht nicht. Was ist den mit prev?

Genau ich soll prüfen ob die Liste leer ist, aber was ist damit gemeint?

Wie sieht denn die Liste aus, wenn diese leer ist?

 

[okayjetztgehts]

Nein, das reicht nicht. Was ist den mit prev?


Wie sieht denn die Liste aus, wenn diese leer ist?

Naja eine Liste die Leer ist hat keine Elemente da ist nur ein head wahrscheinlich, aber ich weiß halt nicht wie ich das prüfe in code, die theorie ist mir da klar.

"Nein, das reicht nicht. Was ist den mit prev?" Meinste prev von head, das zeigt ja auf head selber oder, da ist es ja egal, das prev von head zeigt ja auf head selber.

Mus dazu sagen ich habe als klasse listenelement und da steht:


class Elementderliste
{
protected Inhaltvonl inhaltvonl;
protected Elementderliste prev,nect;
}

Meiste ich muss Inhaltvonl prüfen? ob das nicht leer ist, wenn ja wie das denn ?

 

[kneitzel]

Jedes Element einer Doppelt verketten Liste hat doch eine prev Referenz. Daher wirklich bildlich vorstellen. Wenn das mit den Waggons nicht hilft, dann mal es Dir auf. Die Referenzen können dann z.B. Pfeile sein.

Bei der leeren Liste: Was ist in head.next?

 

[okayjetztgehts]

Jedes Element einer Doppelt verketten Liste hat doch eine prev Referenz. Daher wirklich bildlich vorstellen. Wenn das mit den Waggons nicht hilft, dann mal es Dir auf. Die Referenzen können dann z.B. Pfeile sein.

Bei der leeren Liste: Was ist in head.next?

Danke dir Hat sich nun geklärt, also das überprüfen, dass bekomme ich nun hin!

Aber wie lösche ich nun das erste ELement

 

[kneitzel]

Die Prüfung, ob die Liste leer ist, stimmt so.

Das Element, das du löschen willst, musst Du in der Regeln nicht mehr verändern. Das wird ja nicht weiter referenziert und daher vom GC gelöscht.

Jedes Element hat einen Vorgänger und einen Nachfolger.
Wenn du jetzt den Nachfolger eines Elements auf den Nachfolger des Nachfolger setzt, dann ist das schon einmal richtig. Damit ist in der Richtung das Folge-Element nicht mehr referenziert. Aber das Element, das nach dem zu löschenden Element kommt, hat doch auch einen Vorgänger?

Und was musst Du prüfen, wenn das zu löschende Element das letzte Element ist?

 

[okayjetztgehts]

Die Prüfung, ob die Liste leer ist, stimmt so.

Das Element, das du löschen willst, musst Du in der Regeln nicht mehr verändern. Das wird ja nicht weiter referenziert und daher vom GC gelöscht.

Jedes Element hat einen Vorgänger und einen Nachfolger.
Wenn du jetzt den Nachfolger eines Elements auf den Nachfolger des Nachfolger setzt, dann ist das schon einmal richtig. Damit ist in der Richtung das Folge-Element nicht mehr referenziert. Aber das Element, das nach dem zu löschenden Element kommt, hat doch auch einen Vorgänger?

Und was musst Du prüfen, wenn das zu löschende Element das letzte Element ist?

Achso:

dann könnte ich sagen head.next.next.prev=head oder?

"Und was musst Du prüfen, wenn das zu löschende Element das letzte Element ist?"

Ich muss schauen ob es auf sich selber bei letzteselement.next zeigt oder?

 

[kneitzel]

A) Welchen Wert hat denn next beim letzten Element?

B) Wenn head.next das letzte Element ist, dann wäre also head.next.next der Wert aus A)

C) So Du A und B richtig beantwortet hast, wäre die Frage: Was passiert, wenn Du versuchst auf head.next.next.prev zuzugreifen?

 

[kneitzel]

Oder evtl. Das Zug Beispiel: Doppelt Verkettet bedeutet: Du kannst zwischen Zwei Waggons hin und her springen.

Du gehst also los und springst von Waggon zu Waggon. Beim letzten Waggon willst Du auf den nachfolgenden und springst hinten ab (folgst dem next). Wo landest Du? Bist Du dann in einem Waggon, so dass von dem in den vorherigen Waggon gehen könntest (Als eine mögliche Aktion)?

 

[okayjetztgehts]

Oder evtl. Das Zug Beispiel: Doppelt Verkettet bedeutet: Du kannst zwischen Zwei Waggons hin und her springen.

Du gehst also los und springst von Waggon zu Waggon. Beim letzten Waggon willst Du auf den nachfolgenden und springst hinten ab (folgst dem next). Wo landest Du? Bist Du dann in einem Waggon, so dass von dem in den vorherigen Waggon gehen könntest (Als eine mögliche Aktion)?

Puhh gute frage

Ich denke es muss gehen oder, weil sonst könnte ich ja nicht das vorletzte Element löschen?


Um das Element zu löschen mache ich:

kopf.next=kopf.next.next
kopf.next.next.prev=kopf

oder?

Und wenn das stimmt frage ich mich nun was wegen dem vorletzten Element.

Bei uns ist es so wir haben eine Struktur wo wir ein kopf haben und ein unechtes Element namens unecht: Also struktur unserer Leeren liste ist:

Kopf ⇌unecht, deshalb muss man auch prüfen ob kopf.next bei uns auf unecht zeigt, dann haben wir eine leere lsite.

Gehen wir mal wegen Ihrem Beispiel davon aus ich habe diese Liste:

Kopf ⇌element1⇌element2⇌element3⇌element4⇌unecht

Wie lösche ich nun element4?

Um es zu löschen, muss ich ja das next von element3 nehmen und dem sagen, dass er zu unecht zeigt, aber wie wähle ich element 3 aus?

Wenn ich unecht habe, kann ich sagen

unecht.prev, das kann ich machen, aber wie mache ich nun dass unecht.pev nicht mehr zu element 4 zeigt, sondern zu element3?

Wie könnte ich das realisiren?

wäre da es richtig zu machen:

unecht.prev=unecht.prev.prev?
und dann mache ich:

unecht.prev.prev.next=unecht?

 

[kneitzel]

Ok, wenn es auch am Ende immer so ein Element gibt, dann sieht es gut aus.

Dann gibt es den Sonderfall mit dem letzten Element löschen nicht und du kannst, so es ein Element gibt, immer so löschen wie du es gesagt hast.

Beim Löschen musst du natürlich immer erst zu dem Element, das gelöscht werden soll, kommen. Das erste und letzte Element hast du ja, wenn mitten in der Liste gelöscht werden soll, dann musst du erst durch die Liste gehen. Dazu kannst du z.B. eine lokale Variable mit Kopf initialisieren.
Dann gehst du so lange zum nächsten Element (mit der lokalen Variable) wie das nachfolgende Element weder das gesuchte noch das unechte Element ist.
Wenn das folgeelement das gesuchte Element ist, dann kannst du es löschen. Das geht so, wie du es skizziert hast mit Kopf- nur statt Kopf nimmst du die lokale Variable.

kopf.next=kopf.next.next
kopf.next.next.prev=kopf

Da bitte aber aufpassen: das ist nicht ganz korrekt, denn nach der ersten Zeile ist Kopf.next ja schon Kopf.next.next. Daher reicht dann ein Kopf.next.prev = Kopf als Zweites.

 

[okayjetztgehts]

Ok, wenn es auch am Ende immer so ein Element gibt, dann sieht es gut aus.

Dann gibt es den Sonderfall mit dem letzten Element löschen nicht und du kannst, so es ein Element gibt, immer so löschen wie du es gesagt hast.

Beim Löschen musst du natürlich immer erst zu dem Element, das gelöscht werden soll, kommen. Das erste und letzte Element hast du ja, wenn mitten in der Liste gelöscht werden soll, dann musst du erst durch die Liste gehen. Dazu kannst du z.B. eine lokale Variable mit Kopf initialisieren.
Dann gehst du so lange zum nächsten Element (mit der lokalen Variable) wie das nachfolgende Element weder das gesuchte noch das unechte Element ist.
Wenn das folgeelement das gesuchte Element ist, dann kannst du es löschen. Das geht so, wie du es skizziert hast mit Kopf- nur statt Kopf nimmst du die lokale Variable.


Da bitte aber aufpassen: das ist nicht ganz korrekt, denn nach der ersten Zeile ist Kopf.next ja schon Kopf.next.next. Daher reicht dann ein Kopf.next.prev = Kopf als Zweites.

Stimmt!
Aber wenn wir das mal rückwärts durchspielen,w egen der letzten Anmerkung:


unecht.prev=unrecht.prev.prev
unecht.prev.prev=unecht
Wäre jetzt auch falsch oder, wenn wir so vorgehen würden?

Jetzt müsste ich

unecht.prev=unecht.prev.prev machen

und
unecht.prev=unecht

so würde ich das Element vor unecht löschen oder? (also das letzte echte Element würde so gelöscht werden oder?)

 

[okayjetztgehts]

Aber moment:

Wenn wir jetzt sagen

z. B.
kopf.next=kopf.next.next
kopf.next.prev=kopf

Jetzt möchte ich ja danach noch den Inhalt von dem Element ausgeben, was ich eben gelöscht habe,

da kann ich ja jetzt nicht mehr kopf.next.data machen oder?

Weil kopf.next ist ja jetzt schon was anderes, wie greife ich auf dessen daten zu? Vorher zwischenspeichern oder?

 

[kneitzel]

Vorher zwischenspeichern oder?

Ja genau, dann müsste man es vorher zwischen speichern.

Und bezüglich dem letzten Element löschen: das sieht schon gut aus.

unecht.prev=unecht

Hier hast du aber vermutlich ein next vergessen. Denn es ist ja wie beim ersten Element - sozusagen nur umgedreht. Da war es ja Kopf.next.prev das gesetzt wurde.