Implementierung Listen-ADT

jono

Top Contributor
Doch habe ich ! Du hast auf Seite 2 return last angegeben, und wenn du das so schreibst dann dachte ich es auch so zu übernehmen.
Aber mit value ist immer noch eine Fehlermeldung, value ist noch rot gekringelt.
 

Snaer

Aktives Mitglied
Nachem @Snaer schon fast die Lösung angegeben hat:
Java:
Node last = first; // das erste Element könnte das letzte sein.
while (last.next != null) { // Wenn last aber noch nicht das letzte Element ist,
    last = last.next; // dann könnte das nächste Element das letzte sein
}
return last;
[/QUOTE]
Mir fällt auf das ich das i vermutlich durch last ersetzen hätte sollen damit die Initialisierung von Node last = first überhaupt einen Sinn macht.
Habe ich sonst noch einen Fehler gemacht?
 

mihe7

Top Contributor
Doch habe ich ! [...] Aber mit value ist immer noch eine Fehlermeldung, value ist noch rot gekringelt.
Wenn Du einen Plan hättest, dürftest Du keine Fehlermeldung erhalten. @jono, das ist keineswegs böse gemeint, aber Du zeigst mit jedem zweiten Kommentar, dass Du gar keine Grundlagen beherrschst. Du musst da echt dran arbeiten.

Was hast Du denn geschrieben? Vermutlich return value;?
 

mihe7

Top Contributor
Habe ich sonst noch einen Fehler gemacht?
Ja, mehrere. Ich habe das auch nur als "Lösung" akzeptiert, weil erkennbar war, was Du machen wolltest :)

Es geht um folgenden Code:
Java:
Node last = first;
for (Node i=first; i.next!=0;i=i.next) 
if(i.next=null)
Return i

Durch die fehlenden Blöcke und Einrückungen ist das ziemlich unübersichtlich, daher schreibe ich das erstmal um:
Java:
Node last = first;
for (Node i=first; i.next!=0;i=i.next) {
    if(i.next=null) {
        Return i
    }
}
Mal abgesehen von dem Tippfehler bzgl. "return" und dem fehlenden Semikolon am Ende der Anweisung, ist die Bedingung im if-statement eine Zuweisung und kein Vergleich. Hinzu kommt, dass ein abschließendes return (außerhalb der for-Schleife) fehlt. In der Bedingung prüfst Du auf 0, das kann nicht funktionieren, denn 0 ist ein int, während i.next ein Node ist. Du müsstest also auf null prüfen.

Berücksichtigt man diese Punkte, erhält man:

Java:
Node last = first;
for (Node i=first; i.next!=null;i=i.next) {
    if(i.next == null) {
        return i;
    }
}
return ???;
Jetzt kommen zwei weitere Punkte hinzu:
1. was Du schon selbst angemerkt hast: Du müsstest mit last und nicht mit i arbeiten.
2. Die Bedingung im if-Statement wird niemals true sein, da diese mit der Bedingung der while-Schleife genau gegenteilig überprüft wurde. Der Schleifenkörper wird nur ausgeführt, wenn i.next != null ist, folglich gilt im Schleifenkörper i.next==null gerade nicht.

Java:
Node last;
for (last = first; last.next != null; last = last.next) {
    ; // nichts zu tun
}
return last;
 

Snaer

Aktives Mitglied
Ja, mehrere. Ich habe das auch nur als "Lösung" akzeptiert, weil erkennbar war, was Du machen wolltest :)

Es geht um folgenden Code:
Java:
Node last = first;
for (Node i=first; i.next!=0;i=i.next)
if(i.next=null)
Return i

Durch die fehlenden Blöcke und Einrückungen ist das ziemlich unübersichtlich, daher schreibe ich das erstmal um:
Java:
Node last = first;
for (Node i=first; i.next!=0;i=i.next) {
    if(i.next=null) {
        Return i
    }
}
Mal abgesehen von dem Tippfehler bzgl. "return" und dem fehlenden Semikolon am Ende der Anweisung, ist die Bedingung im if-statement eine Zuweisung und kein Vergleich. Hinzu kommt, dass ein abschließendes return (außerhalb der for-Schleife) fehlt. In der Bedingung prüfst Du auf 0, das kann nicht funktionieren, denn 0 ist ein int, während i.next ein Node ist. Du müsstest also auf null prüfen.

Berücksichtigt man diese Punkte, erhält man:

Java:
Node last = first;
for (Node i=first; i.next!=null;i=i.next) {
    if(i.next == null) {
        return i;
    }
}
return ???;
Jetzt kommen zwei weitere Punkte hinzu:
1. was Du schon selbst angemerkt hast: Du müsstest mit last und nicht mit i arbeiten.
2. Die Bedingung im if-Statement wird niemals true sein, da diese mit der Bedingung der while-Schleife genau gegenteilig überprüft wurde. Der Schleifenkörper wird nur ausgeführt, wenn i.next != null ist, folglich gilt im Schleifenkörper i.next==null gerade nicht.

Java:
Node last;
for (last = first; last.next != null; last = last.next) {
    ; // nichts zu tun
}
return last;
Okay danke für die Antwort, die fehlenden Simikolons und Schleifen kommen daher, dass ich es schnell übers Handy eingetippt habe, aber dennoch gut zu wissen das dort noch mehr Fehler drin sind.
 
K

kneitzel

Gast
Also bezüglich des Code von Snaer mit der for Schleife, habe ich da auch noch ein paar Anmerkungen. Mihe7 hat da schon sehr gut einiges zu geschrieben, aber der Ansatz ist durchaus interessant und korrekt ....

for Schleife: Aus meiner Sicht ist das die typische "Zählschleife", also dient dem durchzählen. Andere Verwendung sehe ich da eher nicht, weil ungewöhnlich. Aber das ist eine reine Präferenz und die Nutzung ist prinzipiell richtig!

Jetzt kommen zwei weitere Punkte hinzu:
1. was Du schon selbst angemerkt hast: Du müsstest mit last und nicht mit i arbeiten.
2. Die Bedingung im if-Statement wird niemals true sein, da diese mit der Bedingung der while-Schleife genau gegenteilig überprüft wurde. Der Schleifenkörper wird nur ausgeführt, wenn i.next != null ist, folglich gilt im Schleifenkörper i.next==null gerade nicht.

Also diesbezüglich kann ich auch als Alternative anbieten:
zu 1. Da die lokale Variable last nur initialisiert aber nie verwendet wird, kann diese einfach gelöscht werden. Dadurch entfällt die erste Zuweisung. (Aber die Variable in der for Schleife kann man ja umbenennen....)
zu 2. Ja, mir ist das als "doppelte Prüfung" aufgefallen. Die Konsequenz daraus kann dann aber auch sein, dass man den Vergleich in der Bedingung der for Schleife komplett entfernt.
Java:
for (Node last = first; ; last = last.next) {
    if (last.next == null) return last;
}

Ein return am Ende brauchte ich nicht, denn das wäre in meinen Augen auch unreachable code gewesen. Die for Schleife hat ja kein break und damit wird diese nicht verlassen.

Das war halt auch eine Option, die ich bei dem Code gesehen hätte, auch wenn ich für meine Person immer zu der while Schleife greifen würde ....
 

jono

Top Contributor
Jetzt habe ich noch Probleme bei der append und init Methode.
Java:
public void init() {
        if (first.next == null) {
            first = null;
            last = null;

        } else {
            last.init.next = null;
            last = last.init;
        }
        length--;

    }
Prinzipiell ist das ja schonmal korrekt, jedoch wird mir last rot unterstrichen, kann ich auch hier wieder
Node last = first anwenden, was ich eigentlich für sinnvoll halte?
 
K

kneitzel

Gast
Ähm, kannst Du einmal beschreiben, was init genau machen soll? Eine leere Liste initialisieren?
Was ist denn first, last und length bei einer leeren Liste, nachdem die Liste initialisiert wurde?
 

jono

Top Contributor
Java:
Was ist denn first, last und length bei einer leeren Liste, nachdem die Liste initialisiert wurde?
Weiß gerade nicht worauf dich da bei mir beziehst, bzw. was du mir damit sagen willst.
 

Luca H

Mitglied
Jetzt habe ich noch Probleme bei der append und init Methode.
Java:
public void init() {
        if (first.next == null) {
            first = null;
            last = null;

        } else {
            last.init.next = null;
            last = last.init;
        }
        length--;

    }
Prinzipiell ist das ja schonmal korrekt, jedoch wird mir last rot unterstrichen, kann ich auch hier wieder
Node last = first anwenden, was ich eigentlich für sinnvoll halte?

Du musst last initialisieren also bei mir klappts mit
Code:
Node last;
 

Luca H

Mitglied
ich hätte allerdings auch eine frage undzwar bei der Methode
Code:
    public void cons(int value) {
        Node newElem = new Node();
        newElem.value = value;

        if (this.first == null) {
            this.first = newElem;
        } else {
            Node tmp = this.first;
            while (tmp.next != null) {
                tmp = tmp.next;
            }
            tmp.next = newElem;
        }
    }

bekomme ich folgenden Fehler

JUnit version 4.12
.E
Time: 0.004
There was 1 failure:
1) test(PublicTests)
java.lang.AssertionError: expected:<5> but was:<9>
at org.junit.Assert.fail(Assert.java:88)
at org.junit.Assert.failNotEquals(Assert.java:834)
at org.junit.Assert.assertEquals(Assert.java:645)
at org.junit.Assert.assertEquals(Assert.java:631)
at PublicTests.test(PublicTests.java:15)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
 

Snaer

Aktives Mitglied
Java:
for (Node last = first; ; last = last.next) {
    if (last.next == null) return last;
}
Die Funktion der last Methode sieht ja so aus :
"last : SortedList -> Nat? // Last element "
Sprich wenn die Liste leer ist fehlt dann nicht noch ein entsprechender Rückgabewert?
Sprich wenn ich eine leere Liste haben sollte, ist first.next bzw in dem Beispiel auch gleichzeitig last.next == null und anschließend gebe ich last aus. Ist das aber auch genug für die angegebene Funktion oder muss man auch noch eine if Anweisung einbauen, die den Fall berücksichtigt, dass die Liste von Beginn an leer sein könnte und es dementsprechend kein letztes Element gibt?

Zudem tue ich mich gerade noch bei der cons Methode schwer:
"constructors nil : -> SortedList // Empty list
hidden constructors cons' : Nat x SortedList -> SortedList // Head element and tail list
functions cons : Nat x SortedList -> SortedList //add element to SortedList
equations cons(n, nil) = cons'(n, nil) cons(n, cons'(n1, l)) = if(greater(n,n1)) then cons'(n1, cons(n, l)) else cons'(n, cons'(n1, l)) "

Meine bisherigen Ansätze sahen so aus
Code:
public void cons(int n) { // Hinzufuegen eines elements
        Node n1 = new Node();
        if(first==null) {
            first.value=n;
            first.next=null;
        }
        if(n<first.value) { // n kleiner als erstes Element bsp 5 kleiner 9
            n1=first;        // speicher first in n1 (n1 =9)
            first.value=n;     // speicher n in first   (first = 5)
            first.next=n1;        // first next zeigt auf n1 also 9
            
        }
        if (n>first.value) { // n ist groesser als first beispiel 7 groesser als 5
            n1.value=n;     // speicher n in n1
            first.next= n1;  // n1 soll hinter first gespeichert werden
        }
    }
Bei diesem bekomme ich jedoch eine Nullpointer Exception
"
There was 1 failure:
1) test(PublicTests)
java.lang.NullPointerException
at SortedList.cons(SortedList.java:14)
at PublicTests.test(PublicTests.java:12)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)"
und:
Code:
public void cons(int n) { // Hinzufuegen eines elements
        Node n1 = new Node();
        n1.value = n;
        if (first == null) // Liste ist null n1 wird Kopfelement
            first = n1;
        else {
            Node i;
            while (first.next != null) {
                if (n1.value != n) {
                    if (n1.value > n) { // Wenn n1 > n ist soll n1 head werden
                        n1.next = first;
                        n1.value = n;
                        first = n1;
                    }
                    if (n1.value < n) { // Wenn n1<n ist soll n1 hinten eingefuegt werden
                        n1.value = n;
                        n1.next = null;
                        while (first.next != null) {
                            first = first.next;
                        }
                        first.next = n1;
                    }
                }
                first=first.next;
            }
        }
    }
Dabei wird zwar das erste Element eingefügt allerdings wird die Liste anscheinend nicht richtig sortiert.

"There was 1 failure:
1) test(PublicTests)
java.lang.AssertionError: expected:<5> but was:<9>"

Da bislang niemand den Test gezeigt hat tue ich das eben mal :
Code:
import static org.junit.Assert.*;

import org.junit.Test;

public class PublicTests {

    @Test
    public void test() {
        SortedList sList = new SortedList();
        
        //Teste cons
        sList.cons(9);
        sList.cons(5);
        sList.cons(7);
        assertEquals(5, sList.first.value);
        assertEquals(7, sList.first.next.value);
        assertEquals(9, sList.first.next.next.value);
        
        
        //Teste append
        SortedList sList2 = new SortedList();
        sList2.cons(6);
        sList2.cons(8);
        sList2.cons(4);

        sList.append(sList2);
        assertEquals(4, sList.first.value);
        assertEquals(5, sList.first.next.value);
        assertEquals(6, sList.first.next.next.value);
        assertEquals(7, sList.first.next.next.next.value);
        assertEquals(8, sList.first.next.next.next.next.value);
        assertEquals(9, sList.first.next.next.next.next.next.value);
        
    }

}
 

mihe7

Top Contributor
Code:
Eine SortedList l:

first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
        

l.init():

first     next      next
----> [3] ----> [5] ----> nil


l.cons(4)

first     next      next      next
----> [3] ----> [4] ----> [5] ----> nil
 

mihe7

Top Contributor

Snaer

Aktives Mitglied
Code:
Eine SortedList l:

first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
       

l.init():

first     next      next
----> [3] ----> [5] ----> nil


l.cons(4)

first     next      next      next
----> [3] ----> [4] ----> [5] ----> nil
Ja das ist verständlich, nur verstehe ich nicht ganz wieso bei mir die Einordnung nicht funktioniert.
Wäre es vielleicht eine Möglichkeit mittels einer Zählschleife die Liste zu durchlaufen und dann anschließend einzufügen?
Also quasi first.next.next für den 3. Index der Liste?
Und sorry falls das eine dumme Frage ist, aber ich verstehe die Implementation von hidden constructors nicht ganz.
So wie es uns erklärt wurde bzw wie ich es verstanden habe, dienen hidden constructors dazu um z.b das hinzufügen eines Wertes zu kontrollieren.
Allerdings wurde in den Beispiel Folien die wir bekommen haben nie ein hidden constructor selbst implementiert sondern alles in der normalen Methode erledigt.
 

mihe7

Top Contributor
nur verstehe ich nicht ganz wieso bei mir die Einordnung nicht funktioniert.
Weil Ihr Euch das nicht richtig überlegt.

Geh mal von folgender Liste aus:
Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
Sagen wir mal, Du möchtest die 7 einfügen. Dann kann man das Problem in zwei Teile aufteilen: 1. finde den richtigen Knoten. 2. füge den neuen Knoten ein.

Welches wäre der richtige Knoten? Der mit der 5.

Warum? Weil wir einen Knoten immer nur hinter einen anderen hängen können und der Wert des auf die 5 folgenden Knotens größer als der einzufügende Wert ist. Ohne Berücksichtigung von Sonderfällen wandern wir also durch die Liste, bis der Wert des Nachfolgerknotens größer als der einzufügende Wert ist.

Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
       ^
       next.value == 5 < 7 --> also weiter        

first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
                 ^
                 next.value == 8 > 7 --> richtige Stelle
An der Stelle können wir also das neue Element einfügen. Wir können sagen, dass der Nachfolger des neuen Element gleich dem aktuellen Nachfolger sein muss:
Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
                           ^
                     [7]---+
                        next
Außerdem muss der aktuelle Nachfolger das neue Element sein:
Code:
first     next                next
----> [3] ----> [5]       [8] ----> nil
                 |         ^
                 +-->[7]---+
                 next   next
Sonderfälle gibt es drei:
1. Das Element muss am Ende der Liste eingefügt werden. Hier ist die Bedingung der Schleife entsprechend zu erweitern.
2. Das Element muss am Anfang einer Liste eingefügt werden.
3. Das Element muss in eine leere Liste eingefügt werden.

Die Fälle 2 und 3 werden gleich behandelt: der Nachfolger des einzufügenden Elements wird der Knoten, auf den first zeigt und first muss hinterher auf das neue erste Element zeigen.
 

Snaer

Aktives Mitglied
Weil Ihr Euch das nicht richtig überlegt.

Geh mal von folgender Liste aus:
Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
Sagen wir mal, Du möchtest die 7 einfügen. Dann kann man das Problem in zwei Teile aufteilen: 1. finde den richtigen Knoten. 2. füge den neuen Knoten ein.

Welches wäre der richtige Knoten? Der mit der 5.

Warum? Weil wir einen Knoten immer nur hinter einen anderen hängen können und der Wert des auf die 5 folgenden Knotens größer als der einzufügende Wert ist. Ohne Berücksichtigung von Sonderfällen wandern wir also durch die Liste, bis der Wert des Nachfolgerknotens größer als der einzufügende Wert ist.

Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
       ^
       next.value == 5 < 7 --> also weiter       

first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
                 ^
                 next.value == 8 > 7 --> richtige Stelle
An der Stelle können wir also das neue Element einfügen. Wir können sagen, dass der Nachfolger des neuen Element gleich dem aktuellen Nachfolger sein muss:
Code:
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
                           ^
                     [7]---+
                        next
Außerdem muss der aktuelle Nachfolger das neue Element sein:
Code:
first     next                next
----> [3] ----> [5]       [8] ----> nil
                 |         ^
                 +-->[7]---+
                 next   next
Sonderfälle gibt es drei:
1. Das Element muss am Ende der Liste eingefügt werden. Hier ist die Bedingung der Schleife entsprechend zu erweitern.
2. Das Element muss am Anfang einer Liste eingefügt werden.
3. Das Element muss in eine leere Liste eingefügt werden.

Die Fälle 2 und 3 werden gleich behandelt: der Nachfolger des einzufügenden Elements wird der Knoten, auf den first zeigt und first muss hinterher auf das neue erste Element zeigen.
Die Logik dahinter verstehe ich, jedoch frage ich mich wie ich möglichst einfach den passenden Index in der Liste ansprechen kann.
Meine einzige Idee wie ich an den dritten Index kommen kann ist first.next.next oder mittels einer Schleife jedoch wüsste ich nicht wie ich diese schreiben kann, außer wenn ich in den letzten Index erreichen möchte.
Oder würde das so funktionieren :
Code:
while (n> first.next){
first.next = first.next.next;
}
 

Snaer

Aktives Mitglied
Was willst Du denn mit einem Index?
Nun ja angenommen ich habe eine Liste in der bereits 3, 4, 8, und 9 gespeichert sind und in diese soll nun die 7 gespeichert werden.
Dann muss ich ja die Liste durch laufen bis ich raus finde wo die 7 hingehört also zwischen die 4 und die 8.
Index ist vielleicht der falsche Begriff dafür, aber ich meine eben die Stelle in der Liste bzw der richtige Knoten für den neuen Wert.
 

Snaer

Aktives Mitglied
Naja ich würde es entweder mithilfe einer For Schleife machen
Code:
for (Node i = first ; i != null; i = i.next){

}
Oder mithilfe einer while schleife
Code:
while (first.next != null){
first=first.next
}
Bei beiden Varianten durchlaufe ich die Liste ja allerdings bis ich am letzten Element angekommen bin. Ich müsste ja dann einen Weg finden, um diesen neuen Wert mit jedem Platz der Liste zu vergleichen nur weiß ich allerdings nicht wie ich die einzelnen Stellen der Liste ansprechen kann.
 

mihe7

Top Contributor
Bei der zweiten Variante fehlt Dir die Referenz auf das aktuelle Element (in der ersten Variante ist das Dein i).
Java:
Node i = first;
while (i.next != null) {
    i = i.next;
}
Du solltest die Referenz aber nicht "i" nennen; ein aussagekräftiger Name wäre besser.

nur weiß ich allerdings nicht wie ich die einzelnen Stellen der Liste ansprechen kann.
Über die Referenz i, die auf das jeweils aktuelle Element zeigt?
 

Snaer

Aktives Mitglied
Was schwebt dir für ein aussagekräftigerer Name denn vor?

Also kann ich dann mithilfe von i eine if Anweisung bauen und den Wert entsprechend einfügen ?
Code:
Code:
Node i = first;
while (i.next != null) {
    i = i.next;
    if (n < i)
    n.next = i;
    i.init = n;
}
Geht das so in die richtige Richtung oder müsste ich eventuell noch eine Hilfsvariable deklarieren um einen Wert in dieser zunächst zu speichern ?
 

mihe7

Top Contributor
Was schwebt dir für ein aussagekräftigerer Name denn vor?
current wäre doch eine Möglichkeit.

Geht das so in die richtige Richtung
Es geht bei der Schleife nur darum, i an die richtige Stelle zu positionieren. Du musst also nur die Schleifenbedingung anpassen. Aktuell stellst Du schon mal sicher, dass Du nicht über das Ende der Liste hinaus läufst. Bis zum Eintreffen welcher Situation musst Du denn i auf die nächste Stelle positionieren?
 

Snaer

Aktives Mitglied
Aso ja dann
Code:
Node i = first;
while (i.next > n ) {
    i = i.next;
    if(i.next < n)
    i.next = n;
}
Sprich ich durchlaufe die Liste solange bis ich einen Wert finde der kleiner ist als n und füge es dann dort ein.
Bzw müsste ich es so machen solange i.next < n da die Liste ja aufsteigend sortiert wird
 

mihe7

Top Contributor
1. i und i.next sind Referenzen auf Node-Objekte. Die kannst Du nicht einfach mit einem int vergleichen, das hatten wir heute schon einmal...
2. läufst Du jetzt ggf. über das Ende hinaus.
3. "müsste ich es so machen solange i.next < n da die Liste ja aufsteigend sortiert wird" - vom Prinzip richtig.

Java:
public void cons(int value) { // Hinzufuegen eines elements
    // ... hier kommt noch mehr ...

    Node current = first;
    while (current.next != null && current.next.value < value) {
       current = current.next;
    }

    // an der Stelle zeigt current auf den Knoten, hinter dem
    // der neue Knoten eingefügt werden muss...
}

EDIT: den Vergleich auf <= korrigiert: < reicht.
 

Snaer

Aktives Mitglied
1. i und i.next sind Referenzen auf Node-Objekte. Die kannst Du nicht einfach mit einem int vergleichen, das hatten wir heute schon einmal...
Sorry mein Fehler ich meine natürlich n.value.
Ich nehme mal an mit dem Kommentar hier kommt noch mehr spielst du auf die Möglichkeit an, dass die Liste auch leer sein kann und ich in diesem Fall das Element einfach hinzufügen kann ohne diese zu durchlaufen.
 

Snaer

Aktives Mitglied
Wenn current auf den Knoten zeigt hinter dem der neue Knoten eingefügt werden muss verstehe ich es dann richtig das dann quasi so aussieht ?
Ich will den Wert 5 einfügen.
Current wäre z.B 3 .next.value zeigt dann auf 4 und hinter eben dieser 4 muss ich dann meine Zahl einfügen also sprich die 5?
Code:
current.next.next = n.value;
Muss ich dann wirklich mehrere .next aneinander hängen um diesen Knoten anzusprechen oder denke ich da gerade völlig falsch ?
 

mihe7

Top Contributor
Ich nehme mal an mit dem Kommentar hier kommt noch mehr spielst du auf die Möglichkeit an, dass die Liste auch leer sein kann und ich in diesem Fall das Element einfach hinzufügen kann ohne diese zu durchlaufen.
Ja. Ggf. erstellst Du am Anfang auch schon das einzufügende Node-Objekt.

verstehe ich es dann richtig das dann quasi so aussieht ?
Nein. Und wieder: Node-Objekte vs int...
 

Snaer

Aktives Mitglied
Nein. Und wieder: Node-Objekte vs int...
Also ich meinte es nicht als bloße Zahlen sondern eher
Das Kopfelement 3 mit Tail auf Kopf 4. Die 5 wäre kleiner als der kopf Wert welcher ja in der Klasse Node als int value deklariert ist also muss dann der Tail von 4 auf die 5 zeigen, um diese einzufügen und wenn die Liste anschließend leer sein sollte zeigt Tail von 5 auf null.
 

mihe7

Top Contributor
Bevor das hier ausartet:
Java:
public void cons(int n) { // Hinzufuegen eines elements
    Node toInsert = new Node();
    toInsert.value = n;

    if (first == null || first.value >= n) {
        toInsert.next = first;
        first = toInsert;
        return;
    }

    Node current = first;
    while (current.next != null && current.next.value <= value) {
       current = current.next;
    }
    toInsert.next = current.next;
    current.next = toInsert;
}
 

Snaer

Aktives Mitglied
Bevor das hier ausartet:
Java:
public void cons(int n) { // Hinzufuegen eines elements
    Node toInsert = new Node();
    toInsert.value = n;

    if (first == null || first.value >= n) {
        toInsert.next = first;
        first = toInsert;
        return;
    }

    Node current = first;
    while (current.next != null && current.next.value <= value) {
       current = current.next;
    }
    toInsert.next = current.next;
    current.next = toInsert;
}
Könntest du mir den letzten Schritt erläutern?
Ein Listen Objekt besteht ja aus einem Kopf in meinem Fall dann value und einem Tail in meinem Fall dann next.
Ich verstehe es gerade so das zum Beispiel der Tail von 5 auf den Tail von 4 zeigt, und der Tail von 4 auf den Kopf von 5.
Aber wäre das dann nicht nur im Kreis und würde nicht mit mehreren Elementen funktionieren?
Ich sehe das der Code zwar so funktioniert allerdings verstehe ich es noch nicht ganz.
 
K

kneitzel

Gast
Kannst du bitte auch mal sagen, was jetzt genau mit current.next.value gemeint ist?
Überleg doch selbst einmal in Ruhe. Sowas solltest Du selbst erkennen können!

Was ist current in dem Code?
Was ist dann next bei current?
Und wenn Du das weisst:Was ist denn bei current.next dieses value?

Könntest du mir den letzten Schritt erläutern?
Ein Listen Objekt besteht ja aus einem Kopf in meinem Fall dann value und einem Tail in meinem Fall dann next.
Ich verstehe es gerade so das zum Beispiel der Tail von 5 auf den Tail von 4 zeigt, und der Tail von 4 auf den Kopf von 5.
Aber wäre das dann nicht nur im Kreis und würde nicht mit mehreren Elementen funktionieren?
Ich sehe das der Code zwar so funktioniert allerdings verstehe ich es noch nicht ganz.
Wenn es eine sortierte Liste ist, dann sollte das Element mit der 5 nie auf das Element von 4 zeigen, denn dann wäre es doch nicht sortiert.
Mein Tipp:Spiel das doch alles einmal richtig auf einem Zettel durch!
 

Luca H

Mitglied
Bevor das hier ausartet:
Java:
public void cons(int n) { // Hinzufuegen eines elements
    Node toInsert = new Node();
    toInsert.value = n;

    if (first == null || first.value >= n) {
        toInsert.next = first;
        first = toInsert;
        return;
    }

    Node current = first;
    while (current.next != null && current.next.value <= value) {
       current = current.next;
    }
    toInsert.next = current.next;
    current.next = toInsert;
}

vielen dank nun klappt diese methode bei mir, jedoch wird jz die append Methode als falsch angemerkt

Code:
    public void append(SortedList l1) {
        if (!l1.isNil())
            if (first == null) {
                first = l1.first;

            } else {
                Node i;
                for (i = first; i.next != null; i = i.next)
                    ;
                i.next = l1.first;
            }

    }

und folgender Fehler wird angezeigt, es wäre nett wenn mir jemand einen Denkanstoß geben könnte

JUnit version 4.12
.E
Time: 0.004
There was 1 failure:
1) test(PublicTests)
java.lang.AssertionError: expected:<4> but was:<5>
at org.junit.Assert.fail(Assert.java:88)
at org.junit.Assert.failNotEquals(Assert.java:834)
at org.junit.Assert.assertEquals(Assert.java:645)
at org.junit.Assert.assertEquals(Assert.java:631)
at PublicTests.test(PublicTests.java:27)
at java.base/jdk.internal.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
 
K

kneitzel

Gast
Ja, und ich will niemandem zu nahe treten, aber dann gibt @mihe7 mehr oder weniger auf und gibt die Lösung und dann gibt es da auch noch massive Verständnisprobleme? Wenn es an den Grundlagen fehlt: Die müsst ihr euch erarbeiten - ich denke, dass @mihe7 da wenig Übungsbedarf hat. Und wie immer gilt da:Übung macht den Meister!

Und wenn es Probleme gibt beim Verständnis der Aufgabe:Malt euch das auf! Das muss man nicht alles direkt im Kopf haben ... aber dann malt es euch auf! Was für Instanzen gibt es? Was sind da jeweils die Inhalte? Dann klappt es auch mit dem Verständnis!
 

Luca H

Mitglied
//Teste append SortedList sList2 = new SortedList(); sList2.cons(6); sList2.cons(8); sList2.cons(4); sList.append(sList2); assertEquals(4, sList.first.value); assertEquals(5, sList.first.next.value); assertEquals(6, sList.first.next.next.value); assertEquals(7, sList.first.next.next.next.value); assertEquals(8, sList.first.next.next.next.next.value); assertEquals(9, sList.first.next.next.next.next.next.value);

Der Fehler ist in Zeile 27 bei AssertEquals (4...) also demnach fügt der Code die 6,8,4 ein aber wenn er dann die Listen vergleicht kommt die Fehlermeldung. Das würde ja an sich bedeuten, dass meine Liste nicht Sortiert ist und die Zahlen nur angehangen wurden oder? Bis dato hat der code ja noch keinen Fehler angezeigt.
 

mihe7

Top Contributor
Ähnliche Java Themen
  Titel Forum Antworten Datum
ruutaiokwu JRE-/JDK-unabhängige PBKDF2WithHmacSHA512-Implementierung Java Basics - Anfänger-Themen 16
V Hilfe bei Implementierung einer boolean Methode Java Basics - Anfänger-Themen 6
K Fehler bei der Implementierung Java Basics - Anfänger-Themen 6
J Implementierung gcd();square() Java Basics - Anfänger-Themen 98
J Implementierung von Observer und Singleton-Pattern Java Basics - Anfänger-Themen 9
A Implementierung von String toString methode() Java Basics - Anfänger-Themen 4
G Projekt architektur (implementierung) Java Basics - Anfänger-Themen 3
M Implementierung einer getNextId Methode Java Basics - Anfänger-Themen 5
J Implementierung eines Zustandsdiagramms Java Basics - Anfänger-Themen 19
I GenericQueue / Implementierung als Ringspeicher Java Basics - Anfänger-Themen 4
MiMa Log4j2 implementierung Java Basics - Anfänger-Themen 4
S Interface Interface und seine Implementierung Java Basics - Anfänger-Themen 5
G Array implementierung Java Basics - Anfänger-Themen 23
J ANTLR Installierung und Implementierung Java Basics - Anfänger-Themen 2
E Hilfe bei Implementierung von Methoden Java Basics - Anfänger-Themen 10
S SkipList Implementierung Java Basics - Anfänger-Themen 1
J Methoden Suche effiziente Implementierung für eine Methode Java Basics - Anfänger-Themen 3
J Interface Probleme bei der Implementierung Java Basics - Anfänger-Themen 1
E hashCode implementierung Java Basics - Anfänger-Themen 9
S Implementierung der Klasse Konto und Nutzung bereits vorhandener Klassen Java Basics - Anfänger-Themen 7
H Implementierung eines Interfaces erweitern Java Basics - Anfänger-Themen 13
O Generics - Implementierung Java Basics - Anfänger-Themen 7
A Hilfestellung zur Implementierung des Gaußsches Eliminationsverfahren Java Basics - Anfänger-Themen 4
B OOP Implementierung eines Heaps Java Basics - Anfänger-Themen 13
K Bucketsort Implementierung Java Basics - Anfänger-Themen 0
K Mergesort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
K Quicksort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
S Klassen Klassendiagramm Implementierung? Java Basics - Anfänger-Themen 5
J Bucketsort Implementierung Java Basics - Anfänger-Themen 0
C Stack - listenbasierte Implementierung Java Basics - Anfänger-Themen 4
N Was bedeutet "Implementierung vor dem Client verbergen" bei Design Patterns? Java Basics - Anfänger-Themen 2
T Collections LinkedList<LinkedList<T>> - Implementierung Java Basics - Anfänger-Themen 10
F Implementierung von Interfaces -> Problem mit main Java Basics - Anfänger-Themen 12
D Resourcebundle implementierung Java Basics - Anfänger-Themen 2
M Implementierung des Knuth-Morris-Pratt-Algorithmus Java Basics - Anfänger-Themen 0
Q Implementierung von Listenern Java Basics - Anfänger-Themen 4
B Klassen Hilfe bei Implementierung Java Basics - Anfänger-Themen 5
N Compiler-Fehler Comparable / compareTo implementierung Java Basics - Anfänger-Themen 2
S Fragen zur Implementierung eines Binärbaums Java Basics - Anfänger-Themen 3
I Erste Schritte Implementierung der API Java Basics - Anfänger-Themen 2
S Fragen zur Implementierung eines Adressbuches Java Basics - Anfänger-Themen 20
M falsche implementierung von currentTimeMillis() ? Java Basics - Anfänger-Themen 14
G Implementierung eines Kontos Java Basics - Anfänger-Themen 11
M Quicksort implementierung Java Basics - Anfänger-Themen 23
SexyPenny90 Implementierung einer doubly linked list Java Basics - Anfänger-Themen 5
N Binärbaum/Implementierung Java Basics - Anfänger-Themen 9
U Doppelte Interfcae Implementierung Java Basics - Anfänger-Themen 10
K Kleiner Fehler bei Methoden Implementierung Java Basics - Anfänger-Themen 6
M Collections Problem bei Überschreibung von hashcode() und equals() bei Hashset-Implementierung Java Basics - Anfänger-Themen 5
S OOP Implementierung Komposition, Aggregation, Assoziation und Generalisierung Java Basics - Anfänger-Themen 2
C Klassenhirarchien zur Implementierung von Fahrzegen Java Basics - Anfänger-Themen 26
BinaryLogic Datentypen Statistik Interface - untersch. Implementierung Java Basics - Anfänger-Themen 5
E Performante Implementierung eines "Hintergrundprogramms" Java Basics - Anfänger-Themen 10
S Saubere Implementierung Java Basics - Anfänger-Themen 2
K Dijkstra implementierung 2.0 Java Basics - Anfänger-Themen 19
K dijskral implementierung Java Basics - Anfänger-Themen 14
U Probleme mit Server-Client implementierung Java Basics - Anfänger-Themen 5
K Game of Life Implementierung Java Basics - Anfänger-Themen 30
B OOP Problem bei Implementierung von Interface Java Basics - Anfänger-Themen 6
J HashSet Implementierung Java Basics - Anfänger-Themen 16
R NullPointerException in Queue-Implementierung Java Basics - Anfänger-Themen 11
X Frage zur Implementierung von equals() Java Basics - Anfänger-Themen 2
B Effektive Implementierung für Darstellung großer Datenmengen in Jogl Java Basics - Anfänger-Themen 5
D Datentypen Implementierung eines Binärbaumes Java Basics - Anfänger-Themen 7
B Implementierung Java Basics - Anfänger-Themen 2
N Implementierung Tic tac toc Java Basics - Anfänger-Themen 25
O Stack Implementierung als verkettete Liste Java Basics - Anfänger-Themen 8
Y Implementierung einer Potenzturm Funktion Java Basics - Anfänger-Themen 4
S Implementierung gegen Interfaces / List, ArrayList, LinkedList Java Basics - Anfänger-Themen 11
J Quicksort Implementierung-- Exception ArrayOutOfBounds Java Basics - Anfänger-Themen 6
U Implementierung Constructor Java Basics - Anfänger-Themen 7
T Problem mit Implementierung von einer HashMap aufgabe Java Basics - Anfänger-Themen 2
G Implementierung des Observer/Observable Patterns - Gut so? Java Basics - Anfänger-Themen 3
I Zugriff auf Implementierung verhindern Java Basics - Anfänger-Themen 8
D Implementierung nach MVC Java Basics - Anfänger-Themen 6
B Theoretische Frage zum Programmbau (nun zur Implementierung) Java Basics - Anfänger-Themen 8
H Implementierung von Interfaces Java Basics - Anfänger-Themen 4
G Implementierung von Bäumen Java Basics - Anfänger-Themen 2
N Probleme mit paint() bei Implementierung in ein Panel Java Basics - Anfänger-Themen 4
B Wie funktioniert die implementierung von c code in Java? Java Basics - Anfänger-Themen 7
D Listen in Listen in Listen ... ??? Java Basics - Anfänger-Themen 2
XWing listen Java Basics - Anfänger-Themen 7
FunkyPhil94 addLast und addFirst bei Listen Java Basics - Anfänger-Themen 6
S Einfach-Verkettete-Listen Ausgabe zeigt nur 1. und letzte instanz Java Basics - Anfänger-Themen 2
J 2 listen vergleichen, die auch null Elemente haben können ! Java Basics - Anfänger-Themen 9
W Liste mit Listen in JTable darstellen Java Basics - Anfänger-Themen 1
Buroto Threads Verschiedene .txt Dateien Auf Listen und Verbinden Java Basics - Anfänger-Themen 3
M Generics Vererbung Listen Java Basics - Anfänger-Themen 2
T Collections Sind Subklassen-Objekte in Listen mit Generics erlaubt? Java Basics - Anfänger-Themen 16
S Lineare listen verkettung Java Basics - Anfänger-Themen 7
S Listen Java Basics - Anfänger-Themen 12
S Listen , Nodes am ende anängen Java Basics - Anfänger-Themen 6
P Sortieren von Listen nach Attributen Java Basics - Anfänger-Themen 3
M Java Listen Java Basics - Anfänger-Themen 4
V einfach verkettete Listen Java Basics - Anfänger-Themen 10
A PhoneBook mit verketteten listen Java Basics - Anfänger-Themen 48
F ich brauche Hilfe bei Listen Java Basics - Anfänger-Themen 13
M (Sehr großes Problem) Listen als static in anderen Klassen verwendet Java Basics - Anfänger-Themen 12
G Java Listen und Iterator Java Basics - Anfänger-Themen 2
S Erklaerung Listen Java Basics - Anfänger-Themen 27

Ähnliche Java Themen

Neue Themen


Oben