DoublyLinkedList

[Aralgut]

Aufgabe im Anhang. Was haltet ihr von meiner Lösung?

public DoublyLinkedList<T> split(T o)
    {
        DoublyLinkedList<T> newList = new DoublyLinkedList<>();
        Element current = first;
        for(int i = 0; i<size; i++)
        {
            if ( current.getContent().equals(o))
            {
                
                current = newList.last;
                for(int j = i; j> 0; j--)
                {
                    current = current.getPred();
                }
                current = newList.first;
                size = size -i;
                newList.size = i;
                newList.last.disconnectSucc();
                break;
            }
            else
            {
                current = current.getSucc();
            }
        }
        return newList;
    }

 

[mihe7]

Was haltet ihr von meiner Lösung?

Welche Lösung?

Mal ein paar Kommentar zum Code:

    public DoublyLinkedList<T> split(T o)
    {
        DoublyLinkedList<T> newList = new DoublyLinkedList<>();
        Element current = first;
        for(int i = 0; i<size; i++)
        {
            if ( current.getContent().equals(o))  // aktuelles Element ist das gesuchte
            {
                
                current = newList.last;           // hier setzt Du current auf das letzte Element
                                                  // der neuen, leeren Liste... 
                for(int j = i; j> 0; j--)        
                {
                    current = current.getPred();  // dann gehst Du (i-1)-mal rückwärts 
                                                  // durch die leere Liste 
                }
                current = newList.first;          // jetzt setzt Du current auf das erste Element
                                                  // der neuen, leeren Liste
                size = size -i;                   // Die Größe der aktuellen Liste um i verringert
                newList.size = i;                 // Die Größe der neuen Liste auf i gesetzt
                newList.last.disconnectSucc();    // Nachfolger des letzten Elements der 
                                                  // leeren Liste "abtrennen" - die Methode
                                                  // disconnectSucc habe ich in der Aufgabe 
                                                  // nirgends gefunden.
                break;
            }
            else
            {
                current = current.getSucc(); // weiter mit dem nächsten Element
            }
        }
        return newList; 
    }

Das ganze kann reduziert werden zu:

    public DoublyLinkedList<T> split(T o)
    {
        DoublyLinkedList<T> newList = new DoublyLinkedList<>();
        Element current = first;
        for(int i = 0; i<size; i++)
        {
            if ( current.getContent().equals(o))  // aktuelles Element ist das gesuchte
            {
                
                size = size -i;                   // Die Größe der aktuellen Liste um i verringert
                newList.size = i;                 // Die Größe der neuen Liste auf i gesetzt
                break;
            }
            else
            {
                current = current.getSucc(); // weiter mit dem nächsten Element
            }
        }
        return newList; 
    }

Das einzige, was Du mit dem Code erreichst, ist die Invariante der Liste zu verletzen.

 

[Aralgut]

public DoublyLinkedList<T> split(T o)
{
    DoublyLinkedList<T> newList = new DoublyLinkedList<>();  // neue Liste anlegen
    Element eins;
    Element current = first;
    Element currentsec= first;
  
    for(int i =0; i < size i++)            // gehe Liste durch
    {
        if( current.getContent().equal(o))        // falls Element current == o ist, setze ich eins == current 
        {                                                           
            eins = current; 
            break;                                             // breche Schleife ab, da element gefunden
        }
        else
        {
            current = current.getSucc();        // falls current != 0, schleife wird fortgesetzt
        }
      
    }
    newList.first = currentsec;                 // setzte 1. Element der neuen Liste auf first( alte Liste)
    newList.last = eins.getPred();            // setzte letztes Element der neuen Liste auf Vorgänger von eins
    newList.last.disconnectSucc();          // disconnecte beide listen voneinander
    size = size -(i-1);                             // Passe size der ursprünglichen liste an
    newList.size= i-1;
    return newList;
}

Zweiter Versuch. Falls es wieder Schwachsinn ist, bitte helfen...

 

[mihe7]

Beschreib mal ohne Code, mit welchen Schritten Du was erreichen möchtest.

BTW: wo kommt disconnectSucc() her?!?

 

[Aralgut]

Beschreib mal ohne Code, mit welchen Schritten Du was erreichen möchtest.

BTW: wo kommt disconnectSucc() her?!?

Aus der Klasse Element.

 

[Aralgut]

Beschreib mal ohne Code, mit welchen Schritten Du was erreichen möchtest.

BTW: wo kommt disconnectSucc() her?!?

habe meinen code mal kommentiert

 

[mihe7]

Aus der Klasse Element.

Vielleicht bin ich blind, aber in dem Bild von Deiner Aufgabe (666.png) sehe ich keine Methode disconnectSucc().

Zum Rest schreib ich gleich noch was.

 

[Aralgut]

Vielleicht bin ich blind, aber in dem Bild von Deiner Aufgabe (666.png) sehe ich keine Methode disconnectSucc().

Zum Rest schreib ich gleich noch was.

Danke, das ist nett. Habe leider keine Lösungen.... sehr nervig

 

[mihe7]

Also, Du hast eine doppelt verkettete Liste:

null<->1<->2<->3<->4<->5<->6<->null
       ^                   ^
     first                last

Nehmen wir mal an, es wird split(3) ausgeführt. Wie Du das ja anfangs schon richtig hattest, suchst Du die 3 und speicherst die Referenz auf das Element in einer Variablen current. Hast Du das Element gefunden, ergibt sich folgendes Bild:

null<->1<->2<->3<->4<->5<->6<->null
       ^       ^           ^
     first  current       last

Was muss jetzt passieren? Am Ende sollst Du zwei Listen haben, nämlich die aktuelle (this) und eine neue:

null<->1<->2<->null    null<->3<->4<->5<->6<->
       ^   ^                  ^           ^
     first last              first       last
        this                     newList

Um das zu erreichen, musst Du ein paar Dinge tun. Wenn ich nichts übersehen habe:

1. altes Last sichern

newLast = last

2. aktuelle Liste ändern

this.last = current.previous
this.last.next = null

3. neue Liste einrichten

newList.last = newLast
newList.first = current
newList.first.previous = null

Nun gibt es ein paar Sonderfälle, die man sich anschauen sollte.

1. die aktuelle Liste ist vor dem Aufruf leer
2. das gesuchte Element ist nicht in der Liste
3. das erste Element der aktuellen Liste ist das gesuchte

Zu 1.: hier gibt man einfach eine leere Liste zurück
Zu 2.: auch hier reicht es, eine leere Liste zurückzugeben
Zu 3.: hier wird es interessant. Wenn das erste Element das gesuchte ist, dann gilt current.previous == null. Im ersten Schritt unter Punkt 2 oben wird das letzte Element somit auf null gesetzt. Der zweite Schritt kann so aber nicht mehr ausgeführt werden. Stattdessen muss das erste Element auf null gesetzt werden (this.first = null;).

 

[mihe7]

Wenn ich nichts übersehen habe:

Was ich natürlich habe und zwar einen Sonderfall:
4. das letzte Element der aktuellen Liste ist das gesuchte
Hier kannst Du Dir mal überlegen, was dann zu tun ist.