Verkettete Liste

[T7V]

Hi, ich studiere jetz Informatik im 2.Semester und ich weiß, dass wir bald lernen Datenstrukuren (wie verkette Listen, Bäume, etc.) zu implementieren.
Also wollte ich schonmal im voraus just-for-fun ein Programm für verkettet Listen schreiben.
Dazu habe ich erstmal zwei Klassen geschrieben: die erste ist Liste, diese hat dann ein Attribut der Klasse Knoten und eine Methode einfügen (bzw später mehr).
Das Problem ist das mir Java dann eine NullPointerException wirft(bei der Methode).
Ich verstehe nur nicht warum. Eigentlich initialisiere ich die Variablen doch in einfügen.
Ich bitte um Hilfe. ???:L

PS: Ich habe gesucht aber nichts gefunden, was mir hilft. Generische Datentypen kann ich noch nicht und mehr Klassen möchte ich auch nicht erstellen(außer dann noch Element).

  public class Liste {

  protected Knoten knoten;

  public Liste(){

  }

  public Liste einfuegen (Element x){     //am Anfang
    Liste l = new Liste();
    knoten.danach = l;
    l.knoten.wert = x;
    l.knoten.danach = null;
    return this;
  }

public class Knoten{

  protected Element wert;
  protected Liste danach;

 

[ARadauer]

ich sehe nirgends ein new Knoten();

nur weil du ein Liste l = new Liste(); machst heißt das ja nicht, das knoten darin nicht null ist

 

[Final_Striker]

protected Liste danach;

Außerdem hat ein Knoten einen Verweis auf den nächsten Knoten und nicht auf die Liste selbst.

Liste l = new Liste();

Beim Einfügen jedes Mal eine neue Liste zu erstellen ist sicherlich auch nicht sinnvoll. Du willst ja schließlich nur eine Liste haben.

 

[T7V]

Ich habe es letztes Semester so gelernt, dass die Liste eine Liste gefolgt von einer weiteren Teilliste ist.
Außerdem ist die erste List nur ein pointer auf die Liste (ohne Wert).

Hab es dann so gemacht:

protected Knoten knoten = new Knoten();

 

[Final_Striker]

Es gibt viele verschieden Listenarten, die natürlich auch alle unterschiedlich imlementiert sind. Ich weiß nicht welche Listen ihr durchgenohmen habt, aber das was du da versucht zu machen, sieht nach einer einfach verketetten Liste aus. Und eine einfach verkettete Liste verwaltet ihre Knoten in denen die eigentlichen Werte enthalten sind.

Der Aufbau ist: 1 Liste, 0 bis "unendlich vielen" Knoten mehr nicht.

 

[T7V]

Hmm, dann hab ich mich wohl irgendwie vertan...???:L
PS: Vielleicht war das hier auch nur ein Beispiel für Rekursionen oder so.

 

[Final_Striker]

Ok, deine Definition war schon so richtig. Habs das gerade bei Wikipedia gelesen:

Wiki:
Sie ist die einfachste Form der verketteten Liste, da sie neben den einzelnen Knoten nur einen „Start“-Zeiger besitzt. Dieser zeigt auf den ersten Knoten in der Liste. Der letzte Knoten in der Liste zeigt auf den Wert NULL (hier NIL für „Not In List”).

Verbale Definition: Eine Liste ist entweder leer oder sie besteht aus einem Kopf und einem Zeiger, der wiederum eine Liste ist.


Finde die erste Definition aber um einiges besser, da die zweite, wie man bei dir sehen konnte, zu Missverständnissen führt.

 

[T7V]

Finde die erste Definition aber um einiges besser, da die zweite, wie man bei dir sehen konnte, zu Missverständnissen führt.

Da muss ich dir zustimmen.

 

[Landei]

Ich habe es letztes Semester so gelernt, dass die Liste eine Liste gefolgt von einer weiteren Teilliste ist.
Außerdem ist die erste List nur ein pointer auf die Liste (ohne Wert).

Das ist ein anderes mögliches Design, das aber eher für unveränderliche Listen geeignet sind. Ich habe schon mal etwas darüber geschrieben: http://www.java-forum.org/blogs/landei/104-einfach-verkettete-listen-veraenderlich.html

 

[T7V]

Habe jetzt eine neue Frage hierzu:

 public Liste stelle(int n){
    if(length()==(length() -n+2)) return this;  
    else return knoten.danach.stelle(n);
  }
  
  
  public Liste insert(Element e, int n){
    if((n > length()) ||(isEmpty())) throw new IllegalArgumentException("Liste besteht aus weniger als n Elementen");
      else {
        Liste l = new Liste();
        l.knoten.wert = e;
        l.knoten.danach = stelle(n+1);
        stelle(n).knoten.danach = l;
      }
    return this;
  }

Die zweite Methode soll Element e an Stelle n einfügen. Hierzu soll stelle(n) das Element vor der Stelle wiedergeben.
Auch hier bekomme ich für eine Test-Liste eine NullpointerException. Ich habe wahrscheinlich bei einem der return oder dem this was falsch gemacht...

 

[SlaterB]

du hast ja immer noch Liste + Knoten, ist das in irgendeiner Hinsicht nützlich?
wieso kann nicht Liste selber wert + danach haben und Knoten komplett wegfallen?

> if(length()==(length() -n+2))
klingt ziemlich unerfüllbar, außer n ist genau 2, deswegen dürfte immer else drankommen, bis irgendwann null,

aber das kann man mit Logging der Aktionen oder Debugging genauestens herausfinden,
dazu solltest du niemanden fragen und ich eigentlich auch nicht antworten..

 

[T7V]

> if(length()==(length() -n+2))
klingt ziemlich unerfüllbar, außer n ist genau 2, deswegen dürfte immer else drankommen, bis irgendwann null,

Logisch nicht.
Das war auch der Fehler. Ich wollte es so haben, dass das zweite length die Länge der nächsten Teilliste ist.Keine Ahnung warum ich das da so geschrieben habe... Jetzt geht es.

 

[Final_Striker]

Jetzt geht es.

Der Code ist aber trotzdem komplett falsch. Du sollst einen Wert einfügen, erstellst aber eine neue Liste.

 

[T7V]

So wie ich es mache enthält jede Liste einen Knoten, welcher nur ein Wert/ein Element enthält. Daher muss ich eine neue Liste erstellen und einfügen, wenn ich einen Wert/ein Element

So funktioniert es bisher eigentich:

public Liste stelle(int n, int j){
    if(length()==(j -n+2)) return this;
    else return knoten.danach.stelle(n,j);
  }
   public Liste insert(Element e, int n){
    if((n > length()) ||(isEmpty())) throw new IllegalArgumentException("Liste besteht aus weniger als n Elementen");
      else {
        int j = length();
        Liste l = new Liste();
        l.knoten.wert = e;
        n = n+1;
        l.knoten.danach = stelle(n+1,j);
        stelle(n,j).knoten.danach = l;
      }
    return this;
  }

 

[Final_Striker]

Es kann ja sein das es funktioniert. Aber die Funktion entspricht trotzdem nicht einer einfach verketteten Liste. Das wirst du aber nächstes Semester dann schon sehen.