# Implementierung Listen-ADT



## jono (17. Jan 2020)

Hallo,
ich habe folgendes Problem:

```
Implementieren Sie einen Listen-ADT anhand der Spezifikation "SortedList.asl".
Die Elemente in der Liste sollen stets aufsteigend sortiert sein.

Beachten Sie folgende Punkte:
- Das Nat in der Spezifikation muss als int in Java übersetzt werden.
- Alle Variablen und Methoden müssen public sein.
- In Node müssen die Variablen value und next heißen.
- In SortedList muss die Variable first heißen.
- Die Methodennamen müssen identisch mit den functions aus der Spezifikation sein.
- Das Verhalten innerhalb der Methoden muss dem Verhalten der equations aus der Spezifikation entsprechen.
- Sie dürfen keine imports oder sonstige vorgefertigte Typen wie z.B. Arrays verwenden. 
Bitte benutzen Sie folgendes Schema für die Dateinamen Ihrer Lösung: SortedList.java, Node.java.
```
Hier die Spezifikation:

```
specification SortedList
imports
  bool
  nat
sorts
  SortedList
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
  head : SortedList -> Nat? // Head element
  tail : SortedList -> SortedList? // SortedList without head
  isNil : SortedList -> Bool // Test for nil SortedList
  length : SortedList -> Nat // Number of elements in the SortedList
  append : SortedList x SortedList -> SortedList // Append two SortedLists
  last : SortedList -> Nat? // Last element
  init : SortedList -> SortedList? // SortedList without last
variables
  n : Nat
  n1 : Nat
  l : SortedList
  l1 : 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))
  head(cons'(n, l)) = n
  tail(cons'(n, l)) = l
  isNil(nil) = true
  isNil(cons'(n, l)) = false
  length(nil) = zero
  length(cons'(n, l)) = succ(length(l))
  append(l,nil) = l
  append(l, cons'(n, l1)) = append(cons(n,l),l1)
  last(cons'(n,l)) = if isNil(l) then n else last(l)
  init(cons'(n,l)) = if isNil(l) then nil else cons'(n, init(l))
```
Dazu habe ich bisher folgenden Quellcode:

```
public class SortedList {
	private Node first;
	private int n;
	private int n1;
	private SortedList l;
	private SortedList l1;

	public void cons() {
		if (l == null) {

		}
	}

	public int head() {
		return first.value;
	}

	public void tail() {
		first = first.next;
	}

	public boolean isNil() {
		if (first == null) {
			return true;
		}
		return false;
	}

	public int length() {
		
	}

	public void append() {

	}

	public int last() {
		if (l == null) {

		}

	}

	public void init() {

	}

}
```
Erstmal meine Frage, wie gehe ich das jetzt bei "cons" an, mit imports soll es ja nicht umgesetzt werden.


----------



## jono (17. Jan 2020)

Klasse Node:

```
public class Node {
	public int value;
	public Node next;
}
```


----------



## jono (17. Jan 2020)

Bei den anderen Methoden fällt es mir auch schwer. Bei "append" z.B. kann ich doch nicht einfach l+l1 schreiben.
Bei "length" gibt es ja auch keine spezielle Funktion die einem direkt die Länge einer Liste ausgibt. Kann mir jemand ein
Tipp geben wie ich das am besten angehe, da ich wirklich kein Plan habe, wie ich das machen soll. Stift und Zettel hilft mir
da auch nur bedingt weiter.


----------



## httpdigest (17. Jan 2020)

Ich denke nicht, dass die Variablen `n`, `n1`, `l` und `l1` als Instanzvariablen in `SortedList` implementiert werden sollen. Es sind Variablen, die in der Spezifikation benutzt werden, um den Zusammenhang von mehreren Dingen zu beschreiben.
Es sind aber sicherlich keine Instanzvariablen im Sinne der Java Klasse `SortedList`.
Die Variablen `n` und `n1` beschreiben den Wert eines Knotens (also quasi `Node.value`), denn ein `Node` selber wird in der Spezifikation nicht gebraucht.


----------



## jono (17. Jan 2020)

Ja, da war ich mir zunächst auch unsicher, dient ja eher der Semantik.


----------



## jono (17. Jan 2020)

@httpdigest Kannst du mir evtl. einen Tipp geben wie ich denn ein Element einer Liste hinzufügen kann?
Denn mit LinkedList ist es verboten, und ich weiß nicht wie ich eine Liste darstellen soll.


----------



## jono (17. Jan 2020)

Kannst du mir einen tipp geben wie ich eine das letzte element einer liste ausgebe ohne eine Arraylist zu benutzen ?


----------



## jono (17. Jan 2020)

Oder kannst du mich da auf hilfreiche Literatur verweisen ?


----------



## mihe7 (18. Jan 2020)

jono hat gesagt.:


> Kannst du mir einen tipp geben wie ich eine das letzte element einer liste ausgebe ohne eine Arraylist zu benutzen ?


Den Tipp hast Du im ADT stehen:


jono hat gesagt.:


> last(cons'(n,l)) = if isNil(l) then n else last(l)


----------



## jono (18. Jan 2020)

Ja, den Tipp verstehe der ist auch schon sehr GUT. Frage mich nur durch welchen Code ich die Liste darstellen kann. First. Next oder was?  Ich glaube nicht.


----------



## httpdigest (18. Jan 2020)

Genau. First. Next.


----------



## mihe7 (18. Jan 2020)

jono hat gesagt.:


> First. Next oder was? Ich glaube nicht.


1. In einer verketteten Liste kann jeder Knoten als Kopf einer verketteten Liste gesehen werden. 
2. Um eine verkettete Liste anzugeben, reicht die Angabe des Kopfes.

Bei (k,n) ist k nichts anderes als das Kopfelement, n das diesem folgende Element (next).


----------



## jono (18. Jan 2020)

Okay, danke. 

```
public int last(int value) {
		Node n = new Node();
		n.value = value;
		if(first.next == null) {
			n = this.first;
		} else {
			last(first.next);
	}
```
Wie kann ich denn jetzt das letzte Element herausfiltern ..?


----------



## jono (18. Jan 2020)

```
last(first.next);
```
last wird hier rot unterstrichen logischerweise


----------



## mihe7 (18. Jan 2020)

In Node:


```
public int last() {
    if (next == null) {
        return value;
    } else {
        return next.last();
    }
}
```


----------



## jono (18. Jan 2020)

Gehört der Code in die Klasse Node? Dachte es gehört in die Klasse Sorted.List, da es so in den Programmierfolien der Fall war..


----------



## jono (18. Jan 2020)

Also nicht am Beispiel last, aber war dann dementsprechend eher naheliegend es in die Klasse Sorted.List zu implementieren.


----------



## mihe7 (18. Jan 2020)

jono hat gesagt.:


> Gehört der Code in die Klasse Node? Dachte es gehört in die Klasse Sorted.List, da es so in den Programmierfolien der Fall war..


Der Code würde in die Klasse Node gehören und dient dazu, Dir die grundsätzliche Idee zu zeigen. Du wirst es vermutlich in SortedList implementieren müssen. Das geht natürlich nicht 1:1, da musst Du Dir zusätzlich was überlegen (s. im ADT die "hidden constructors").


----------



## jono (18. Jan 2020)

Wenn ich jetzt daran denke, dass ich erst dachte die equations einfach in Code umzusetzen, und jetzt daran einen hidden constructor zu implementieren, weiß ich beim hidden constructor zwar welche Aufgabe er erfüllt, aber nicht wie ich diesen einbauen kann , denn

```
-versteckte Konstruktoren lassen nur das Einfügen weiterer Elemente in eine Menge zu, falls diese Elemente noch nicht in der Menge enthalten sind
-Aufruf von versteckten Konstruktoren nur indirekt durch öffentliche Funktionen gleichen Namens möglich
```
Problem: Wie kann ich mir das vorstellen, wenn es darum geht das letzte Element zu returnen. Da kann ich keinen Zusammenhang sehen im Sinne von Zulassen von Einfügen weiterer Elemente in eine Menge, falls diese noch nicht in der Menge enthalten sind, damit hat das last-Element doch nichts zu tun, weil es nicht um Einfügen geht?
Das habe ich aus der Vorlesungsfolie, klingt ziemlich abstrakt.


----------



## mihe7 (18. Jan 2020)

Naja, wenn Du last() als rekursive Methode in SortedList einbaust, brauchst Du ja die "nächste" SortedList und nicht den nächsten Node.


----------



## jono (18. Jan 2020)

Da muss ich mal schauen, Rekursion kommt erst bald


----------



## jono (18. Jan 2020)

Geht es nicht anders, denn sonst wäre es ja schon in den Vorlesungen behandelt worden.


----------



## mihe7 (18. Jan 2020)

Klar geht das anders: Du hangelst Dich in einer Schleife bis zum letzten Element durch die Liste.


----------



## jono (18. Jan 2020)

Man könnte es doch eigentlich auch so machen, dass man sagt, dass das größte Element das letzte sein muss, da die Liste ja aufsteigend sortiert ist?


----------



## jono (18. Jan 2020)

Ja und das Problem  was ich habe ist, dass ich nicht weiß, wie ich das letzte Element anspreche wie du sagst über eine Schleife.


----------



## mihe7 (18. Jan 2020)

jono hat gesagt.:


> Man könnte es doch eigentlich auch so machen, dass man sagt, dass das größte Element das letzte sein muss, da die Liste ja aufsteigend sortiert ist?


Ob das letzte Element das größte ist, spielt für last() nicht die Rolle: das letze Element ist dasjenige, auf das kein weiterer Eintrag folgt.



jono hat gesagt.:


> Ja und das Problem was ich habe ist, dass ich nicht weiß, wie ich das letzte Element anspreche wie du sagst über eine Schleife.


Ich geb Dir noch einen Algorithmus an die Hand, den Code musst Du aber schon selbst hinbekommen:

```
letztesElement := erstes Element
so lange letztesElement nicht auf das letzte Element der Liste zeigt {
    letztesElement := das auf letztesElement folgende Element 
}
gib letztesElement zurück
```


----------



## jono (19. Jan 2020)

Wieso hast du dir letztesElement und erstesElement gleichgesetzt , verstehe das echt nicht.


----------



## jono (19. Jan 2020)

Schon gut habe es verstanden


----------



## Luca H (19. Jan 2020)

Mich würde mal interessieren wie der code nun aussieht ^^


----------



## jono (19. Jan 2020)

Den habe ich noch nicht, weil ich noch nicht drauf kam , wie ich das letzte Element anspreche ^^


----------



## mihe7 (19. Jan 2020)

Der Code sieht fast so aus wie der Algorithmus.


----------



## jono (19. Jan 2020)

Wärst du so nett und kannst mir ein Hinweis geben, wie das letzte Element aufgerufen wird.


----------



## mihe7 (19. Jan 2020)

Auf das letzte Element wird nicht "aufgerufen", es wird mit dem Algorithmus ermittelt.


----------



## jono (19. Jan 2020)

```
so lange letztesElement nicht auf das letzte Element der Liste zeigt
```
Das meine ich, letzteElement habe ich initialisiert indem ich

```
Node last = first;
```
gesetzt habe und jetzt muss ich ja mit einem Zeiger auf das letzte Element zeigen.
Aber "das letzte Element" muss ja auch eine spezifische Bezeichnung haben als Code 
oder nicht?


----------



## jono (19. Jan 2020)

Ich kann mir das ja nicht aus der Nase ziehen ^^


----------



## Snaer (19. Jan 2020)

mihe7 hat gesagt.:


> ```
> letztesElement := erstes Element
> so lange letztesElement nicht auf das letzte Element der Liste zeigt {
> letztesElement := das auf letztesElement folgende Element
> ...


Korrigiere mich wenn ich falsch liege 

```
Node last = first;
for (Node i=first; i.next!=0;i=i.next) 
if(i.next=null)
Return i
```


----------



## mihe7 (19. Jan 2020)

jono hat gesagt.:


> Das meine ich, letzteElement habe ich initialisiert indem ich
> 
> ```
> Node last = first;
> ...


richtig.



jono hat gesagt.:


> und jetzt muss ich ja mit einem Zeiger auf das letzte Element zeigen.
> Aber "das letzte Element" muss ja auch eine spezifische Bezeichnung haben als Code


last ist der Zeiger  

Nachem @Snaer schon fast die Lösung angegeben hat:

```
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;
```


----------



## jono (19. Jan 2020)

```
public int last() {
		Node last = first;
		while(last.next != null){
			last = last.next;
		}
		return last;
	}
```
Problem ist nur noch dass ein int zurückgegeben werden muss, wie mache ich das hier ?


----------



## mihe7 (19. Jan 2020)

Indem Du Dir Deine Node-Klasse ansiehst?!?


----------



## jono (19. Jan 2020)

```
public Node last()
```


----------



## mihe7 (19. Jan 2020)

Das ist nicht die Klasse Node.


----------



## jono (19. Jan 2020)

Ja das ist doch klar, habe den Methodennamen so umbenannt dann zeigt er keine Fehlermeldung mehr an .


----------



## mihe7 (19. Jan 2020)

Verstehe. Damit hast Du aber die Aufgabe nicht erfüllt


----------



## jono (19. Jan 2020)

Komm schon sag doch was daran noch falsch ist ^^


----------



## mihe7 (19. Jan 2020)

Was daran falsch ist? Du kannst doch nicht einfach hergehen und sagen: gut, laut Aufgabe soll ich eine Zahl zurückgeben, aber das ist mir zu kompliziert, mache ich einfach etwas anderes draus.


----------



## jono (19. Jan 2020)

Wie soll ich das denn sonst machen^^? Das Problem ist ja, dass last oben wegen first vom Typ Node ist und last kann ich nicht den Datentyp Int zuordnen.


----------



## mihe7 (19. Jan 2020)

Ach, Du Sch... jetzt realisiere ich das erst: @jono... *Du* bist das 



jono hat gesagt.:


> Das Problem ist ja, dass last oben wegen first vom Typ Node ist und last kann ich nicht den Datentyp Int zuordnen.


Deswegen solltest Du ja auch mal einen Blick in die Klasse Node werfen. Was könnte man da wohl sinnvollerweise zurückgeben?


----------



## jono (19. Jan 2020)

Value?


----------



## jono (19. Jan 2020)

Haha @mihe7 ^^, das klingt aber ziemlich nett


----------



## mihe7 (19. Jan 2020)

jono hat gesagt.:


> Value?


Du hast keinen Plan, was Du da eigentlich machst oder? Natürlich value, was denn sonst?


----------



## jono (19. Jan 2020)

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.


----------



## jono (19. Jan 2020)

Mit einem Parameter löse ich das oder ?


----------



## Snaer (19. Jan 2020)

Nachem @Snaer schon fast die Lösung angegeben hat:

```
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 (19. Jan 2020)

jono hat gesagt.:


> 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;`?


----------



## jono (19. Jan 2020)

Ja genau.


----------



## mihe7 (19. Jan 2020)

Snaer hat gesagt.:


> 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:

```
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:

```
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:


```
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.


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


----------



## mihe7 (19. Jan 2020)

jono hat gesagt.:


> Ja genau.


Das ist an der Stelle nichts anderes als `return this.value;` Du willst aber doch nicht die value der Liste, sondern des letzten Elements zurückgeben. Was musst Du also logischerweise schreiben?


----------



## Snaer (19. Jan 2020)

mihe7 hat gesagt.:


> Ja, mehrere. Ich habe das auch nur als "Lösung" akzeptiert, weil erkennbar war, was Du machen wolltest
> 
> Es geht um folgenden Code:
> 
> ...


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.


----------



## jono (19. Jan 2020)

last.value ?


----------



## Luca H (19. Jan 2020)

jono hat gesagt.:


> last.value ?



JA


----------



## kneitzel (19. Jan 2020)

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!



mihe7 hat gesagt.:


> 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.

```
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 (19. Jan 2020)

Jetzt habe ich noch Probleme bei der append und init Methode.

```
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?


----------



## kneitzel (19. Jan 2020)

Ä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 (19. Jan 2020)

Init soll die Liste ohne das letzte Element ausgeben.


----------



## jono (19. Jan 2020)

```
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 (19. Jan 2020)

jono hat gesagt.:


> Jetzt habe ich noch Probleme bei der append und init Methode.
> 
> ```
> public void init() {
> ...



Du musst last initialisieren also bei mir klappts mit 
	
	
	
	





```
Node last;
```


----------



## Luca H (19. Jan 2020)

ich hätte allerdings auch eine frage undzwar bei der Methode 

```
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:
> ...


----------



## Snaer (19. Jan 2020)

JustNobody hat gesagt.:


> ```
> 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 

```
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:

```
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 :

```
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 (19. Jan 2020)

```
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 (19. Jan 2020)

Luca H hat gesagt.:


> ich hätte allerdings auch eine frage undzwar bei der Methode


Es geht um eine *Sorted*List...


----------



## mihe7 (19. Jan 2020)

Snaer hat gesagt.:


> Sprich wenn die Liste leer ist fehlt dann nicht noch ein entsprechender Rückgabewert?


Richtig. 


Snaer hat gesagt.:


> 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.


Wenn Du eine leere List haben solltest, gilt first == null und first.next würde zu einer NullPointerException führen.


----------



## Snaer (19. Jan 2020)

mihe7 hat gesagt.:


> ```
> Eine SortedList l:
> 
> first     next      next      next
> ...


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 (19. Jan 2020)

Snaer hat gesagt.:


> 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:

```
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.


```
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:

```
first     next      next      next
----> [3] ----> [5] ----> [8] ----> nil
                           ^
                     [7]---+
                        next
```
Außerdem muss der aktuelle Nachfolger das neue Element sein:

```
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 (19. Jan 2020)

mihe7 hat gesagt.:


> Weil Ihr Euch das nicht richtig überlegt.
> 
> Geh mal von folgender Liste aus:
> 
> ...


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 : 

```
while (n> first.next){
first.next = first.next.next;
}
```


----------



## mihe7 (19. Jan 2020)

Snaer hat gesagt.:


> Die Logik dahinter verstehe ich, jedoch frage ich mich wie ich möglichst einfach den passenden Index in der Liste ansprechen kann.


Was willst Du denn mit einem Index?


----------



## Snaer (19. Jan 2020)

mihe7 hat gesagt.:


> 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.


----------



## mihe7 (19. Jan 2020)

Snaer hat gesagt.:


> Dann muss ich ja die Liste durch laufen bis ich raus finde wo die 7 hingehört also zwischen die 4 und die 8.


Ja, und wie läuft man durch eine verkettete Liste?


----------



## Snaer (19. Jan 2020)

Naja ich würde es entweder mithilfe einer For Schleife machen 

```
for (Node i = first ; i != null; i = i.next){

}
```
Oder mithilfe einer while schleife 

```
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 (19. Jan 2020)

Bei der zweiten Variante fehlt Dir die Referenz auf das aktuelle Element (in der ersten Variante ist das Dein i).

```
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. 



Snaer hat gesagt.:


> 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 (19. Jan 2020)

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 ?
	
	
	
	





```

```


```
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 (19. Jan 2020)

Snaer hat gesagt.:


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


current wäre doch eine Möglichkeit. 



Snaer hat gesagt.:


> 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 (19. Jan 2020)

Aso ja dann

```
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 (19. Jan 2020)

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.


```
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 (19. Jan 2020)

mihe7 hat gesagt.:


> 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 (19. Jan 2020)

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?

```
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 (19. Jan 2020)

Snaer hat gesagt.:


> 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.



Snaer hat gesagt.:


> verstehe ich es dann richtig das dann quasi so aussieht ?


Nein. Und wieder: Node-Objekte vs int...


----------



## Snaer (19. Jan 2020)

mihe7 hat gesagt.:


> 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 (19. Jan 2020)

Bevor das hier ausartet:

```
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 (20. Jan 2020)

mihe7 hat gesagt.:


> Bevor das hier ausartet:
> 
> ```
> public void cons(int n) { // Hinzufuegen eines elements
> ...


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.


----------



## jono (20. Jan 2020)

Kannst du bitte auch mal sagen, was jetzt genau mit current.next.value gemeint ist?


----------



## kneitzel (20. Jan 2020)

jono hat gesagt.:


> 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?



Snaer hat gesagt.:


> 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 (20. Jan 2020)

mihe7 hat gesagt.:


> Bevor das hier ausartet:
> 
> ```
> public void cons(int n) { // Hinzufuegen eines elements
> ...



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


```
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:
> ...


----------



## mihe7 (20. Jan 2020)

Snaer hat gesagt.:


> Ein Listen Objekt besteht ja aus einem Kopf in meinem Fall dann value


Ein Listen-Objekt besteht aus Node-Objekten. Der Kopf ist ein Node-Objekt, der in der Liste mittels "first" referenziert wird.


----------



## thecain (20. Jan 2020)

Wollt ihr nicht eine Lerngruppe gründen und das zusammen lösen? @mihe7 macht ja für einen halben Studiengang die Hausarbeit


----------



## mihe7 (20. Jan 2020)

Luca H hat gesagt.:


> es wäre nett wenn mir jemand einen Denkanstoß geben könnte


Schau nach, was append lt. ADT machen soll...


----------



## kneitzel (20. Jan 2020)

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 (20. Jan 2020)

mihe7 hat gesagt.:


> Schau nach, was append lt. ADT machen soll...



Es sollen zwei SortedLists angehangen werden - aber es wäre doch sinnvoller das mit einer While-Schleifen zu lösen oder?


----------



## Luca H (20. Jan 2020)

> //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 (20. Jan 2020)

JustNobody hat gesagt.:


> aber dann gibt @mihe7 mehr oder weniger auf


Nachdem ich registriert hatte, mit wem ich schreibe, war mir schon klar, wo das endet: mit 300 Kommentaren und am Ende schreibt man dann sowieso die Lösung  Vielleicht hilft es dem Verständnis, wenn man über den Code diskutiert.



Luca H hat gesagt.:


> Es sollen zwei SortedLists angehangen werden


Nein, das steht im ADT nicht.


----------



## mihe7 (20. Jan 2020)

Luca H hat gesagt.:


> Das würde ja an sich bedeuten, dass meine Liste nicht Sortiert ist und die Zahlen nur angehangen wurden oder?


Richtig, was anderes macht Deine append-Methode ja auch nicht.


----------



## Luca H (21. Jan 2020)

mihe7 hat gesagt.:


> Richtig, was anderes macht Deine append-Methode ja auch nicht.



Dann könnte ich ja mithilfe einer While - Schleife die Stelle herausfinden, in der der neue Wert eingefügt werden muss.


----------



## Snaer (21. Jan 2020)

```
public void append(SortedList l) {
        if (!l.isNil())
            if (first == null) {
                first = l.first;
            } else {
                Node neu;
                for (neu = l.first; neu.next != null; neu = neu.next) {
                    for (Node alt = first; alt.next != null; alt = alt.next) {
                        if (neu.value < alt.value) {
                            neu.next = alt.next;
                            alt.next = neu;
                        }
                    }
                }
            }
    }
```
Ich versuche hierbei durch beide Listen zu laufen und damit die Werte zu vergleichen. 
Meine Idee ist es dabei mit der ersten Schleife die neue Liste zu durchlaufen z.B 6,8,4 bzw 4,6,8, da sie ja durch die Cons Methode bereits sortiert sein sollte, und durch die alte 5,7,9. 
Wenn dann der Wert der neuen Liste kleiner ist als der der alten soll der neue Wert an die Stelle eingefügt werden. Jedoch bekomme ich als ersten Wert immer wieder die 5 ausgegeben. Ich habe schon einiges versucht zu verändern finde den Fehler allerdings dennoch nicht.


----------



## kneitzel (21. Jan 2020)

Snaer hat gesagt.:


> Ich habe schon einiges versucht zu verändern finde den Fehler allerdings dennoch nicht.



Hast Du das denn mal durchgespielt auf einem Zettel?
Der neue Node mit der 4 zeigt dann auf den ersten Node der existierenden Liste. Aber first verweist doch noch auf das ehemals erste Element aber nicht auf das neue Erste Element!

Also überleg Dir, wie Du first umsetzen kannst, so dies notwendig sein sollte....


----------



## Snaer (21. Jan 2020)

JustNobody hat gesagt.:


> Hast Du das denn mal durchgespielt auf einem Zettel?
> Der neue Node mit der 4 zeigt dann auf den ersten Node der existierenden Liste. Aber first verweist doch noch auf das ehemals erste Element aber nicht auf das neue Erste Element!
> 
> Also überleg Dir, wie Du first umsetzen kannst, so dies notwendig sein sollte....


Ich habe es zumindest versucht nur scheine ich ein klares Verständnis Problem zu haben. 
Meine Überlegung sah ungefähr so aus : 
neu (4) alt (5)
Wenn neu < alt 
In dem Fall gegeben, dann soll neu.next also 4.next auf alt.next zeigen also 5.next. 
und alt.next auf neu. 
Dabei habe ich versucht mich an den Zeilen von mihe zu orientieren 

```
toInsert.next = current.next;
        current.next = toInsert;
```
Also noch zuvor in der Cons Methode
Jedoch habe ich diese glaube nicht verstanden. Auf einem Zettel kam ich dabei auf die Umsetzung :
toInsert = n (5) 
current =first (9)
Wenn also die 9 kleiner ist als die 5 
Soll current.next (quasi dann 5.next) auf current .next zeigen
Aber wieso soll dann current.next toInsert werden, würde das dann nicht quasi bedeuten das die 5 nach der 9 kommt ?
Also das ich da irgendwo einen Denkfehler habe ist mir bewusst, da der Code ja so funktioniert nur leider bin ich gerade echt verwirrt.


----------



## mihe7 (21. Jan 2020)

Luca H hat gesagt.:


> Dann könnte ich ja mithilfe einer While - Schleife die Stelle herausfinden, in der der neue Wert eingefügt werden muss.


Könntest Du. Statt immer wieder den gleichen Code zu schreiben, könntest Du aber auch eine bereits existierende Methode verwenden


----------



## mihe7 (21. Jan 2020)

Snaer hat gesagt.:


> Wenn also die 9 kleiner ist als die 5 [...] würde das dann nicht quasi bedeuten das die 5 nach der 9 kommt ?


Ja, wenn die 9 kleiner als die 5 wäre, dann wäre das ja auch richtig


----------



## mihe7 (21. Jan 2020)

Snaer hat gesagt.:


> Ich habe es zumindest versucht nur scheine ich ein klares Verständnis Problem zu haben.


Du musst Dir den Spaß erstmal vernünftig aufzeichnen, damit Du nicht ständig den Knoten und den im Knoten gespeicherten Wert verwechselst:


----------



## Luca H (21. Jan 2020)

mihe7 hat gesagt.:


> Könntest Du. Statt immer wieder den gleichen Code zu schreiben, könntest Du aber auch eine bereits existierende Methode verwenden


Ich hab mir auch schon gedacht die cons - Methode zu verwenden, weil die ja ungefähr das macht


----------



## mihe7 (21. Jan 2020)

Luca H hat gesagt.:


> Ich hab mir auch schon gedacht die cons - Methode zu verwenden, weil die ja ungefähr das macht


Ja, die cons-Methode fügt Dir das Element sogar an der richtigen Stelle ein...


----------



## Luca H (21. Jan 2020)

mihe7 hat gesagt.:


> Ja, die cons-Methode fügt Dir das Element sogar an der richtigen Stelle ein...


Okay das Prinzip habe ich verstanden also müsste ich nur die Mehtode cons aufrufen und die würde die Zahlen sortiert einfügen


----------



## mihe7 (21. Jan 2020)

Ja, wboei cons halt immer nur eine Zahl einfügt (sonst wäre es ja genau das gleiche wie append)


----------



## Luca H (21. Jan 2020)

mihe7 hat gesagt.:


> Ja, wobei cons halt immer nur eine Zahl einfügt (sonst wäre es ja genau das gleiche wie append)


Eine Frage hätte ich noch. Und zwar gibt es eine Möglichkeit die cons - Methode aufzurufen und diese dann in append zu erweitern, das die alle Elemente hinzufügt und nicht nur eine?


----------



## mihe7 (21. Jan 2020)

Luca H hat gesagt.:


> Und zwar gibt es eine Möglichkeit die cons - Methode aufzurufen und diese dann in append zu erweitern, das die alle Elemente hinzufügt und nicht nur eine?


Das ist Sinn und Zweck der Sache. Konkret: für jedes Element der übergebenen Liste cons aufrufen.


----------



## Luca H (21. Jan 2020)

mihe7 hat gesagt.:


> Das ist Sinn und Zweck der Sache. Konkret: für jedes Element der übergebenen Liste cons aufrufen.



Prinizpiell müsste das doch dann mit 
	
	
	
	





```
Node i = cons();
```
gehen oder?


----------



## Snaer (21. Jan 2020)

JustNobody hat gesagt.:


> Hast Du das denn mal durchgespielt auf einem Zettel?
> Der neue Node mit der 4 zeigt dann auf den ersten Node der existierenden Liste. Aber first verweist doch noch auf das ehemals erste Element aber nicht auf das neue Erste Element!
> 
> Also überleg Dir, wie Du first umsetzen kannst, so dies notwendig sein sollte....


Ich verstehe nicht wieso first noch auf das ehemals erste Element zeigt. Ich habe es mir auch aufgezeichnet bzw zumindest versucht.
Also neu ist ja = l.first. Also ist neu der erste Knoten der neuen Liste in dem Fall dann 4 richtig ?
Wenn dann alt = first ist ist ja alt der erste Knoten der alten Liste also 5.
Somit sollte die if Anweisung sofort gelten da 4 < 5 ist. 
Dann verweist der Knoten mit der 4 auf den vorherigen ersten Knoten mit der 5. Und der ehemals alte Knoten soll ersetzt werden. 
Ich verstehe nicht wo genau der Unterschied zwischen dem Versuch und diesen Zeilen genau ist.

```
Node current = first;
        while (current.next != null && current.next.value < n) {
            current = current.next;
        }
        toInsert.next = current.next;
        current.next = toInsert;
        
    }
```
Wenn ich die Zeilen durchspiele müsste es ja so aussehen. 
Zuallererst wird die 9 in die leere Liste hineingefügt. Anschließend soll die ein Knoten mit der 5 eingefügt werden. 
Daher verweist der Knoten mit der 5 auf current.next also dem Knoten mit der 9. 
Und an die Stelle von current.next wird die 5 eingeschoben.


----------



## mihe7 (21. Jan 2020)

Luca H hat gesagt.:


> Prinizpiell müsste das doch dann mit


Die Methode cons() existiert nicht.


----------



## Luca H (21. Jan 2020)

mihe7 hat gesagt.:


> Die Methode cons() existiert nicht.



Ich übersehe hier die einfachsten Dinge. Ich komm einfach nicht drauf wie ich in append die Methode - cons aufrufen kann
Uns wurde das aber auch nicht erklärt in der letzten Übung, weil der Übungsleiter selbst kein bock hatte..


----------



## mihe7 (21. Jan 2020)

Naja, der Übungsleiter muss ja wohl nicht extra dazu sagen, dass nur genutzt werden kann, was auch definiert ist. Eine Methode cons() ohne Parameter gibt es nicht.


----------



## 1337Avdu (21. Jan 2020)

@Luca H wo studierst du denn? - Sowas ist Grundvoraussetzung.


----------



## Luca H (21. Jan 2020)

1337Avdu hat gesagt.:


> @Luca H wo studierst du denn? - Sowas ist Grundvoraussetzung.


Koblenz


----------



## Luca H (21. Jan 2020)

mihe7 hat gesagt.:


> Naja, der Übungsleiter muss ja wohl nicht extra dazu sagen, dass nur genutzt werden kann, was auch definiert ist. Eine Methode cons() ohne Parameter gibt es nicht.


Das Problem ist einfach das er nicht mal erklärt hat wie man eine ADT List implementiert


----------



## mihe7 (21. Jan 2020)

Snaer hat gesagt.:


> Ich verstehe nicht wo genau der Unterschied zwischen dem Versuch und diesen Zeilen genau ist.


Die alte Liste sei 5->6->null und die neue Liste 1->2->null

Die äußere Schleife iteriert mit neu über die neue Liste, also ist neu erstmal 1. 

neu=1->2 (neu ist ein Knoten mit dem Wert 1 und der Knoten zeigt auf einen anderen Knoten mit dem Wert 2).

In der inneren Schleife iterierst Du mit alt über die alte Liste, also ist alt erstmal 5.

alt=5->6

Jetzt prüfst Du, ob neu.value < alt.value gilt, was offensichtlich der Fall ist, denn 1 < 5. Also führst Du aus:
neu.next = alt.next, d. h. neu=1->6 und
alt.next = neu, d. h. alt=5->1

Durch die Änderung der next-Zeiger ergibt sich also:
1. für die alte Liste 5->1->6-null
2. für die neue Liste 1->6->null

Mal abgesehen davon, dass die 2 nun ganz verloren ist, stimmt die Reihenfolge in der alten Liste auch nicht.


----------



## Snaer (21. Jan 2020)

mihe7 hat gesagt.:


> Jetzt prüfst Du, ob neu.value < alt.value gilt, was offensichtlich der Fall ist, denn 1 < 5. Also führst Du aus:
> neu.next = alt.next, d. h. neu=1->6 und
> alt.next = neu, d. h. alt=5->1
> 
> ...


Gut danke das macht es mir ersichtlich, aber wieso verhält es sich dann nicht genauso bei dem Code ?

```
Node current = first;
        while (current.next != null && current.next.value < n) {
            current = current.next;
        }
        toInsert.next = current.next;
        current.next = toInsert;
```
Ist first selbst ein Element der Liste oder ist es nur der erste Zeiger auf den nächsten Knoten?


----------



## mihe7 (21. Jan 2020)

Luca H hat gesagt.:


> Das Problem ist einfach das er nicht mal erklärt hat wie man eine ADT List implementiert


Das können wir hier schlecht beurteilen, ich bin aber schon verwundert, dass hier gleich mehrere Leute sind, die ernsthafte Probleme haben.

Schau doch mal Deine cons-Methode an, die erwartet einen Parameter, nämlich den einzufügenden Wert.

Wenn Du also eine Methode schreibst:

```
public void append(SortedList l) {
    cons(5);
    cons(2);
    cons(9);
}
```
Dann fügt diese Methode die Werte 5, 2 und 9 zur aktuellen Liste hinzu.

Statt der fixen Werte willst Du cons nun für alle Elemente aus l aufrufen, also musst Du über l iterieren. Dafür gibt es verschiedene Möglichkeiten, in jedem Fall brauchst Du eine Schleife.


----------



## mihe7 (21. Jan 2020)

Snaer hat gesagt.:


> aber wieso verhält es sich dann nicht genauso bei dem Code ?


1. Ist das der Code für cons und nicht für append.
2. Wird hier bis zum richtigen Element iteriert und nicht einfach eingefügt, sobald neu < alt gilt.
3. Ist es denn wirklich so schwer, das selbst durchzuspielen?

Nimm die Grafik aus 107 und etwas, womit Du auf einen Knoten zeigen kannst, sagen wir mal einen Stift. Dann repräsentiert Dein Stift current. Und dann gehst Du den Code Zeile für Zeile durch. Wenn im Code steht: current=first, dann zeigst Du mit dem Stift auf den ersten Knoten (der auf den first zeigt). Wenn im Code steht: current = current.next, dann zeigst Du mit dem Stift auf den Knoten auf den - ausgehend vom aktuellen - next zeigt (kurz: auf den nächsten Knoten). Das ganze probierst Du aus für die Fälle 1, 4, 7 und 10. Dann sollte klar sein, wie der Code funktioniert.



Snaer hat gesagt.:


> Ist first selbst ein Element der Liste oder ist es nur der erste Zeiger auf den nächsten Knoten?


first ist nur der Zeiger auf den ersten Knoten der Liste.


----------



## kneitzel (21. Jan 2020)

Ja, aber das ist doch auch nicht das erste Mal, dass hier so eine Gruppe aufschlägt oder ist das jetzt lediglich die Gruppe, die vor paar Wochen hier schon aktiv war?

Aber wie dem auch sei: Ich bin hier teilweise mit meinem Latein am Ende. So im Forum können wir nicht alle Grundlagen so ausführlich bringen. Dafür gibt es Lehrbücher. Ein Dozent mag schlecht sein, aber dann muss doch wenigstens auf brauchbare Literatur verwiesen werden.....

Vor allem sehe ich das Problem, dass wir an einer Aufgabe rumhantieren und nicht wirklich sehen, wo die Verständnisprobleme sind. Ich denke, dass da irgend eine Kleinigkeit fehlt. Ich versuche so z.B. immer einen Bezug zu Objekten zu schaffen, die weniger abstrakt sind.... Dann klappt es mit der Vorstellung evtl. und ich habe da immer die Hoffnung, dass es dann "Klick" macht.

Ich glaube auch, dass man ein paar Dinge einfach im Detail vormachen müsste. Dieses durchspielen auf einem Zettel ist da ein Beispiel. Und da staune ich dann teilweise über die Ascii Zeichnungen die hier teilweise gebracht werden. Ich hab mir noch einmal TeX installiert weil ich dachte, dass ich da dann schnell paar einfache Skizzen machen kann. Einige Dinge gehen ganz schnell, aber auch das ist noch einiges an Aufwand.... Und der blöde Export hin zu html haut nicht wirklich hin, sonst hätte ich da Erläuterungen in mein Blog gepackt .... Aber da geht wahnsinnig Zeit drauf. Man will ja noch einmal drüber schauen und so ...

Also lange Rede einmal kurz gefasst: Ich sehe hier gerade keinen Ansatz, wie das zu lösen ist....


----------



## Snaer (21. Jan 2020)

mihe7 hat gesagt.:


> Das können wir hier schlecht beurteilen, ich bin aber schon verwundert, dass hier gleich mehrere Leute sind, die ernsthafte Probleme haben.
> 
> Schau doch mal Deine cons-Methode an, die erwartet einen Parameter, nämlich den einzufügenden Wert.
> 
> ...


Ich habe mal versucht es mithilfe des Methoden Aufrufs von cons zu regeln. 

```
public void append(SortedList l) {
        if (!l.isNil())
            if (first == null) {
                first = l.first;
            } else {
                for (Node neu = l.first; neu.next != null; neu = neu.next) {
                    this.cons(neu.value);
                }
            }
    }
```
Dies funktioniert seltsamerweise jedoch nur für 2 von 3 Werten. Während die 4 und die 6 wohl korrekt eingefügt werden, wird die 8 wohl übersprungen


----------



## mihe7 (21. Jan 2020)

JustNobody hat gesagt.:


> ist das jetzt lediglich die Gruppe, die vor paar Wochen hier schon aktiv war?


Klar. Damals ging es um 2D-Arrays, wenn ich mich recht entsinne und schon da fehlten alle Grundlagen. Darum #99  



Snaer hat gesagt.:


> Dies funktioniert seltsamerweise jedoch nur für 2 von 3 Werten.


Das ist nicht seltsam, sondern liegt an Deiner Schleifenbedingung.


----------



## Snaer (21. Jan 2020)

mihe7 hat gesagt.:


> Das ist nicht seltsam, sondern liegt an Deiner Schleifenbedingung.


Ich nehme mal an du meinst da die Schleife nur solange durchläuft bis neu.next != null ist. 
Aber muss ich nicht diese Absicherung einbauen, damit ich nicht über das Ende der Schleife laufe?


----------



## kneitzel (21. Jan 2020)

Dann spielt es doch mal durch:
Du bist beim vorletzten Element, dann Rückstand du eins weiter und er prüft: neu.next != null und steigt aus.

Also aufzeichnen und schauen, wie lange du weiter gehen musst, damit es funktioniert.

Und brauchst die Sonderbehandlung mit der Prüfung, ob First Null ist?


----------



## Snaer (21. Jan 2020)

JustNobody hat gesagt.:


> Und brauchst die Sonderbehandlung mit der Prüfung, ob First Null ist?


Die Bedingung habe ich für den Fall eingesetzt, dass die erste Liste null sei, sodass quasi die neue Liste diese einfach ersetzen kann. Ob es wirklich getestet wird kann ich nicht einsehen, da nur ein kleiner Teil des Tests einsehbar ist.


----------



## mihe7 (21. Jan 2020)

Snaer hat gesagt.:


> Die Bedingung habe ich für den Fall eingesetzt, dass die erste Liste null sei, sodass quasi die neue Liste diese einfach ersetzen kann.


Leute, Leute... bevor Ihr Euch an irgendwelche Optimierungen wagt, solltet ihr halbwegs wissen, was ihr da betreibt. Bei Euch fehlt wirklich alles an Grundlagen, was ich mir vorstellen kann. Dozent hin oder her: *IHR* müsst Euch darum kümmern, die Zeiten, in denen der Lehrer dem Schüler alles nachträgt sind für Euch vorbei. 

Zurück zum Thema: first ist eine Referenz(!) auf ein Node-Objekt. Wenn Du first einfach auf l.first setzt, dann referenzieren first und l.first das selbe(!) Objekt. Die Listen bestehen dann nicht aus gleichen Objekten sondern aus identischen. So gut wie jede Änderung der einen Liste wirkt sich damit automatisch auf die andere Liste aus. Das ist nicht das, was Du willst.


----------

