Doppelt verkettete Liste bzw. Zirkulärliste (kleiner Fehler, den ich nicht finde)

[chik]

Hallo zusammen,

ich habe hier eine Zirkulärliste programmiert, die folgendermaßen aussieht:
Jedes Listenelement hat einen Wert und zwei Zeiger. Einer zeigt auf das nächste element und einer auf den Anfang.
Das letzte Element zeigt auf das Erste.

Also ich hatte es hin und her probiert und mit zwei Elementen hatte es funktioniert, beim dritten wurde dann das zweite element einfach immer überschrieben.
Jetzt habe ich es umprogrammiert und folgende Fälle überlegt:
1.Liste ist leer if (item == null && anfang.item == null)
2.Es ist bereicht ein Element drin und deshalb wird eine neues leeres Listenelement beim next Zeiger erzeugt
next = new ZirkulaereListe();
next.anfang = this. anfang;
next.insertlast(elem);
3.Der letzte vorherige Aufruf sollte dann von folgenden Code gegriffen werden (item == null && anfang.item != null) weil item sollte ja nun null sein, da es ja ein neues Element ist und Anfang ist ja nun auf Anfang gesetzt.

Leider klappt es nicht, seltsamer weise wird das erste if einfach übersprungen, hier der Code:

public class ZirkulaereListe { 
private Object item; 
private ZirkulaereListe next; 
ZirkulaereListe anfang;
public ZirkulaereListe() {} 

private ZirkulaereListe(Object i, ZirkulaereListe n) { 
    item = i; 
    next = n; 
} 

public Object insertlast(Object elem) {
    if (item == null && anfang == null) { 
        System.out.println("item == null && anfang == null");
        item = elem;
        anfang = this;
        next = anfang;
    }
    else
    if (item == null && anfang.item != null) { 
        item = elem;
        next = anfang;
        System.out.println("item == null && anfang != null");
    } 
    else 
        System.out.println("else");
        next = new ZirkulaereListe();
        next.anfang = this. anfang;
        next.insertlast(elem);

                return elem;
            }

//Die beiden Funktionen hier sind nur zum Testen
    public void ausgabeAnfang(){System.out.println(anfang.item);}

    public void ausgabeNext(){System.out.println(next.item);}
}

Über eure Hilfe wäre ich sehr dankbar, weil x+2 Augen, sehe mehr als meine 2 durch die Erkältung geröteten Augen ;-)

 

[SlaterB]

    } 
    else 
        System.out.println("else");
        next = new ZirkulaereListe();
        next.anfang = this. anfang;
        next.insertlast(elem);

                return elem;
            }

->

    } 
    else {
        System.out.println("else");
        next = new ZirkulaereListe();
        next.anfang = this. anfang;
        next.insertlast(elem);
    }
    return elem;
}

 

[chik]

thxs.

jetzt gibt es leider dennoch ein Problem:

Bis zum 2. Element geht alles.
Aber beim 3. Element passiert folgendes:
Das 1 Element zeigt dann auf das 3.Element das zweite geht dann somit verloren.
Hier der aktuelle code:

public class ZirkulaereListe { 
private Object item; 
private ZirkulaereListe next; 
ZirkulaereListe anfang;
public ZirkulaereListe() {} 

private ZirkulaereListe(Object i, ZirkulaereListe n) { 
    item = i; 
    next = n; 
} 

public Object insertlast(Object elem) {
    if (item == null && anfang == null) { 
        System.out.println("item == null && anfang == null");
        item = elem;
        anfang = this;
        next = anfang;
    }
    else
    if (item == null && anfang.item != null) { 
        item = elem;
        next = anfang;
        System.out.println("item == null && anfang != null");
     } 
    else {
        System.out.println("else");
        next = new ZirkulaereListe();
        next.anfang = this. anfang;
        next.insertlast(elem);
    }
    return elem;
}

public Object removefirst() { 
    if (item != null) { 
        Object res = item; 
        item = next.item; 
        next = next.next; 
        return res; 
    } 
    return null; 
}
 
public Object removelast() { 
    return (item == null) ? 
    null : (next.item == null) ? removefirst() : 
    next.removelast(); 
}

// suchen 
    public Object search(Object elem) { 
        return (item == null) ? 
        null : (item.equals(elem)) ? item : 
        next.search(elem); 
} 

// Liste ausgeben 
    public String toString() { 
        return (item == null) ? "" : item.toString() + " " + 
        next.toString(); 
    }
    
    public void ausgabeAnfang(){System.out.println(anfang.item);}

    public void ausgabeNext(){System.out.println(next.item);}
}

 

[SlaterB]

erstmal:
toString() nie aufrufen, da ist ja eine Endlosschleife drin, da musst du noch prüfen, ob z.B. next == anfang oder so

-----

du postest keinen Programmablauf, ich nehme aber mal an, du fügst deine neuen Elemente immer ins allererste Listenelement ein
(die weiteren ZirkulaereListe-Objekte werden ja auch nicht zurückgegeben/ sind nicht abfragbar),
in der insertlast()-Methode kennst du nur die Fälle 'bei mir einfügen', 'bei next einfügen' + 'neues next',

nicht aber, dass next schon vorhanden und belegt ist,
dann musst du das neue Element nämlich an next weiterreichen
und dort muss die ganze Überlegung von vorne beginnen,
könnte ja sein, dass next.next auch schon voll ist,

Vorsicht: nicht an next weiterreichen, wenn next anfang ist, sonst Endlosschleife des Umherreichens (ähnlich toString())

 

[chik]

Vielleicht hilft es Jemanden mal irgendwann:

public class ZirkulaereListe {
private Object item;
// die verschiedenen Zeiger
private ZirkulaereListe next;
private ZirkulaereListe anfang;
private ZirkulaereListe runner;
private ZirkulaereListe temp;
//Der Hauptkonstruktor
public ZirkulaereListe() {}

//Die Methode zum einfügen am Ende einer Liste
public void einfuegen(Object elem) {
   //Liste-Leer Fall
   if (item == null && anfang == null) {
       item = elem;
       anfang = this;
       next = anfang;
   }
   //Allg. Fall
   else {
       runner = this;
       //zum Ende der Liste laufen
       while (runner.next != this.anfang)
       {
           runner = runner.next;
        }
       //Zeiger anpassen
       runner = runner.next = new ZirkulaereListe();
       runner.anfang = this.anfang;
       runner.next =runner.anfang;
       runner.item = elem;
   }
}

public void loeschen(int z){
    runner=anfang;
    //Zur Stelle z gehen (gemäß Skript)
    for (int i=1; i<=z-1; i++)
    {runner = runner.next;}
    System.out.println("Zum löschen ausgewählte Zahl: " + runner.item + " an der gewählten Stelle: " + z + " (Siehe oben)");
    //Spezialfall für das 1.Element
    if (runner == anfang){
    runner.item = runner.next.item;
    runner.next = runner.next.next;
    }
    else
        //Spezialfall wenn nur noch 2 Elemente ex.
        if (runner.next.next == runner)
        {
            anfang.next = anfang;
        }
            //Letztes Element löschen
            else
                if (runner.next.next != runner && runner.next == anfang)
                    {
                        temp=this;
                        //Gehe zum vorletzten Element
                        while (temp.next != runner)
                            {
                                temp = temp.next;
                            }
                        //Setzte vorletztes Element auf den Anfang
                        temp.next = anfang;
                    }
                    //Allg. Fall
                    else
                    {
                        runner.item = runner.next.item;
                        runner.anfang = runner.next.anfang;
                        runner.next=runner.next.next;}
                        ausgaben();
}
   //Ausgabe Funktion, welche alle vorhandenen Daten ausgibt.
   public void ausgaben(){
    System.out.println("==============" + "Ausgabe" + "==============");
    runner = anfang;
    //Nur 1 Element Fall
    if (runner.next == anfang) {
        System.out.println(runner.item);
        return;}
    //Allg. Fall
    do{
    System.out.println(runner.item);
           runner = runner.next;
    }while (runner != this.anfang);
    }
}