Doppelt verkettete Listen

[java (Gast)]

Hallo,



ich soll in Java eine doppelt verkettete Liste erstellen und weiß nicht 
recht wie.



Ich stelle mal den vorhandenen Code ein:

public class Aufgabe10 {



  public static void main(String[] args)

    {

    //System.out.println("hello");

    Natset liste = new Natset();

    

    

    }

  

  

}



public class MyNode {



  private int value;

  private MyNode next;

  private MyNode previous;

  

  

  public MyNode()

  {}

  

  public int getValue()

  {

    return value;

  }

  

  public void setValue(int m)

  {

    value = m;

  }

  

  public MyNode getNext()

  {

    return next;  

  }

  

  public MyNode getPrevious()

  {

    return previous;  

  }

  

}







public class Natset {



  private MyNode start;

  private int size;

  

  public Natset(){}

  

  public int getSize()

  {

    return size;

  }  

  



}

Ein Teil war bereits vorgegeben, und ich soll es "fertigstellen".



Ein bisschen was habe ich schon gemacht, aber es reicht nicht um 
weiterzukommen.



Erstmal habe ich gedacht, ich erzeuge ein neues Objekt liste, das muss 
ich ja.

Jetzt stellt sich mir die Frage, wie weiße ich start seinen Wert zu? 
Erzeuge ich da einfach ein neues Objekt aus MyNode? Und wie erzeuge ich 
dann neue Listeneinträge? Ich muss von einem Vorhandenen Listeneintrag 
auf den neuen Zeigen. In C habe ich das schon erfolgreich mit Pointern 
Programmiert, aber diese Objektorientierung macht mir ziemlich zu 
schaffen.



Wäre nett wenn mir jemand einen kleinen Hinweiß geben könnte, damit ich 
weiter dran arbeiten kann.



Danke schonmal

[ozo (Gast)]

Das Objekt, welches ein Element der Liste repräsentieren soll, benötigt 
zusätzlich noch eine Referenz auf seinen Vorgänger und seinen 
Nachfolger.
In dem Objekt, welches die Liste als Ganzes darstellen soll, nimmt man 
sinnigerweise eine Referenz auf das erste und letzte Element mit auf.
Nennen wir sie mal 'Kopf' und 'Arsch'. Zunächst ist Kopf=Arsch=null und 
die Liste damit leer. Bist du so weit?

[Karl H. (kbuchegg)]

java schrieb:

> Jetzt stellt sich mir die Frage, wie weiße ich start seinen Wert zu?

einfach ein neues MyNode Objekt mit new erzeugen und zuweisen

> Erzeuge ich da einfach ein neues Objekt aus MyNode? Und wie erzeuge ich
> dann neue Listeneinträge?


    vorhandenerKnoten.next = new MyNode

> auf den neuen Zeigen. In C habe ich das schon erfolgreich mit Pointern
> Programmiert,

na dann.
Funktioniert doch in Java auch nicht anders, nur dass es keine Pointer 
Syntax gibt und du Pointer zuweist, in dem du stattdessen die Objekte 
rumreichst und Java unter der Hand nur Pointer umkopiert.

> aber diese Objektorientierung macht mir ziemlich zu
> schaffen.

Das heist in deinem Fall nichts anderes als das eine Funktion "anhängen" 
nichts anderes als eine Funktion des Objektes ist und nicht einfach eine 
freistehende Funktion. Aber mehr ist das nicht.
Einfach 'Beamtendenken" einsetzen: Wer ist dafür zuständig, dass eine 
Operation gemacht wird.
Nicht die Liste ist in letzter Konsequenz dafür zuständig, dass an das 
Ende der List ein neuer Knoten angehängt wird und macht sich die Finger 
schmutzig. Die Liste identifiziert wer der letzte Knoten ist und 
beauftragt dann diesen Knoten den neuen Knoten an sich drann zu hängen. 
Das ist sein Job, da soll sich mal der Knoten die Finger damit schmutzig 
machen.

[java (Gast)]

Soweit bin ich, dass die Liste leer ist.


Jetzt ist eher meine Frage, wie bekomme ich ein neues Objekt da hinein. 
Und wie greife ich darauf zu, über start? Wie soll das gehen, ich steh 
ziemlich auf dem Schlauch

[Karl H. (kbuchegg)]

java schrieb:
> Soweit bin ich, dass die Liste leer ist.
>
>
> Jetzt ist eher meine Frage, wie bekomme ich ein neues Objekt da hinein.

indem du es erzeugst.

die Liste hat eine Referenz, die nennt sich start

also wird der erste Knoten erzeugt mittels

    start = new MyNode;

ferig.

> Und wie greife ich darauf zu, über start?

ja.

> Wie soll das gehen,

Indem du einfach das Objekt (über seine Referenz) benutzt

    start.getValue();

> ich steh
> ziemlich auf dem Schlauch

du denkst viel zu komplizert.

[ozo (Gast)]

Nun ja, dein Objekt 'Liste' könnte doch unter Umständen eine Methode a 
la 'addToHead(Node N)' besitzen. Von außen dann etwa so aufzurufen:
myList = new List();
myList.addToHead(new ListItem());

Klemmts im Detail oder in der Übersicht?

[Läubi .. (laeubi)]

java schrieb:
> Jetzt ist eher meine Frage, wie bekomme ich ein neues Objekt da hinein.
> Und wie greife ich darauf zu, über start?

http://openbook.galileocomputing.de/javainsel/

[java (Gast)]

Hi,

in der Übersicht klemmt es, das was Karl Heinz gesagt hat bringt mich 
schon weiter, ich habe echt zu kompliziert gedacht.

und wenn ich jetzt den nächsten eintrag machen will, mache ich dann
start.next = new MyNode(); oder?

Danke

[Läubi .. (laeubi)]

java schrieb:
> und wenn ich jetzt den nächsten eintrag machen will, mache ich dann
> start.next = new MyNode(); oder?

Nein... Du benötigst eine append/prepend Funktion da auf private 
Elemente nicht jeder zugreifen kann bzw. soll!

Überleg dir doch erst ohne Java prinzipiell wie es ablaufen soll. Und 
in der Aufgabe steht bestimmt auch drinn welche Operationen zu 
implementieren sind...

[Karl H. (kbuchegg)]

java schrieb:
> Hi,
>
> in der Übersicht klemmt es, das was Karl Heinz gesagt hat bringt mich
> schon weiter, ich habe echt zu kompliziert gedacht.
>
> und wenn ich jetzt den nächsten eintrag machen will, mache ich dann
> start.next = new MyNode(); oder?

IM Prinzip ja.

Aber du machst es nicht so. Du machst es objektorientiert.

Du gibst dem Knoten start den Auftrag einen neuen Knoten an sich hinten 
drann zu hängen. Denn der Liste ist das schnurzegel, wie das genau geht. 
Das geht die Liste nichts an sondern das ist das Bier vom Knoten

   start.append( new MyNode() );

und die append Methode der Klasse MyNode (weil start ja eine Referenz 
auf ein MyNode Objekt ist) macht dann erst den Klimbim mit den 
'Pointern'.

public class MyNode {

  ...

  public void append( MyNode newNode )
  {
    if( this.next() != null ) {
      newNode.next( this.next() );
      this.next().previous( newNode );
    }
    this.next( newNode );
    newNode.previous( this );
  }

  ...

[java (Gast)]

Ahh sonst würde ich das ins unendliche verschachteln.

Gut ich brobiere es jetzt so, ist ziemliches Neuland für mich, aber 
danke soweit schonmal.

[Karl H. (kbuchegg)]

Eines noch.

Du machst natürlich nicht

   start.append( new MyNode() );

Die Liste soll sich den neuen Knoten nicht selbst erzeugen, sondern den 
kriegt sie wiederrum von main. Dort wird der Knoten erzeugt und an eine 
append Methode der Liste weitergegeben, die ihn an die Liste anhängt, 
indem sie den letzten Knoten der Liste beauftragt, den Knoten 
anzuhängen. Natürlich nur wenn es schon einen letzten Knoten gab. Wenn 
nicht, dann ist der übergebene Knoten der neue letzte Knoten (und auch 
erster Knoten klarerweise, denn die Liste muss dann leer gewesen sein, 
wenn es keinen letzten Knoten gab)

public class Natset {

  private MyNode first;
  privtae MyNode last;

  public void append( MyNode newNode )
  {
    if( this.last == null )
      this.first = newNode;
    else
      this.last.append( newNode );

    this.last = newNode;
  }
}

und den Member Variable size schmeisst du am besten gleich wieder raus. 
Wenn jemand wissen will, wieviele Elemente in der List sind, dann zählst 
du die Knoten.

[java (Gast)]

Also ich habs mal selber nochmal versucht und habe es zwar "geschafft" 
aber ich habe hier glaube ich zwei Variablen, die ich mir irgendwie 
schenken könnte, ich weiß nur noch nicht wie. Ich lasse im Moment Natset 
die Listenverwaltung machen, was ich für sinnvoll halte:

Hier mal der derzeitige Code:

public class Aufgabe10 {

  public static void main(String[] args)
    {
    //System.out.println("hello");
    
    //Neue Liste erzeugen
    Natset liste = new Natset();
    
    //Startpunkt erstellen
    liste.setStart();
    
    //Listenelemente hinzufügen
    liste.append(1);
    liste.append(2);
    liste.append(3);
    liste.append(4);
    liste.append(5);
    
    //in Liste auf und abgehen und Elemente ausgeben
    System.out.println(liste.nextItem());
    System.out.println(liste.nextItem());
    System.out.println(liste.nextItem());
    System.out.println(liste.nextItem());
    System.out.println(liste.nextItem());
    System.out.println(liste.nextItem());
    
    System.out.println(liste.previousItem());
    
    
    
    }
  
  
  
  
  
  
}


public class Natset {

  private MyNode start;
  private MyNode last;
  private MyNode address;
  private MyNode buffer;
  private int size;
  
  public Natset(){}
  
  public void setStart()
  {
    //Start festlegen
    start = new MyNode();  
    last = start;
    address = start;    
  }
  
  public void append(int a)
  {
    //next auf neu erzeugtes Element zeigen lassen
    last.setNext(new MyNode());
    //Reverenz auf altes Element speichern
    buffer = last;
    //letzer Wert
    last = last.getNext();
    //Reverenzen und Werte setzen
    last.setNext(null);
    last.setPrevious(buffer);
    last.setValue(a);
    size++;
  }
  
  public int nextItem()
  {
    //Wenn es ein nächstes Element gibt
    if(address.getNext() != null)
    {
      //Ein Element weiter springen
      address = address.getNext();    
      return address.getValue();
    }
    else
    {
      return 0;
    }
    
  }
  
  public int previousItem()
  {
    if(address.getPrevious() != null)
    {
      //Ein Element zurückspringen
      address = address.getPrevious();    
      return address.getValue();
    }
    else
    {
      return 0;
    }
    
  }
  
    
  
  public int getSize()
  {
    return size;
  }  
  
}

public class MyNode {

  private int value;
  private MyNode next;
  private MyNode previous;
  
  
  public MyNode()
  {}
  
  
  public int getValue()
  {
    return value;
  }
  
  public void setValue(int m)
  {
    value = m;
  }
  
  public MyNode getNext()
  {
    return next;  
  }
  
  public MyNode getPrevious()
  {
    return previous;  
  }
  public void setNext(MyNode n)
  {
    next = n;
  }
  
  public void setPrevious(MyNode p)
  {
    previous = p;
  }

  
}

Wäre nett wenn nochmal jemand drüber schauen würde und mir noch ein paar 
Tipps gibt.


Danke euch soweit schonmal :)

[java (Gast)]

@Karl Heinz,

mit dem was du mir gepostet hast bin ich übrigends auf keinen grünen 
Zweig gekommen, ich habe es nicht so recht verstanden.

[Purzel H. (hacky)]

Also, eine doppeltverkettete Liste sollte man aufm Papier aufmalen und 
in irgendeiner Sprache hinschreiben koennen. Im Schlaf. Das ist Teil des 
Eintrittstickets in den Beruf. Zum Glueck gibt's Debugger, da kann man 
Singlesteppen bis die Ohren wackeln. Sinnvoll zur Liste ist auch noch 
eine Membervariable 'count' die die Anzahl Elemente zaehlt.
Mach mal.

[java (Gast)]

Sorry, dass ich sowas erst jetzt in meinem Studium versuche lerne, aber 
woher soll ich sowas können? Ich versuche mich gerade darin und verstehe 
deinen Kommentar nicht. Wenn du es kannst, dann hilf mir dabei.
Außerdem zähle ich die Anzahl der Elemente.

[Purzel H. (hacky)]

Also. Mach's mal auf dem Papier. Welche Pointer muessen wohin zeigen. 
Und werden in welcher Reihenfolge wohin verschoben ?

Die Liste hat die Membervariablen : Erster & Letzter und beide zeigen 
auf Knoten.
Die Knoten haben die Membervariablen : Vorheriger & Naechster, und 
zeigen auf Knoten.
Mal das mal auf Papier.
Wie wird der erste, zweite & N-te Knoten angefuegt ?
Wie wird der n-te, zweitletzte & letzte Knoten geloescht ?

Mal das mal auf.

[java (Gast)]

Das habe ich bereits aufgemalt, aber hast du eigentlich meinen Code 
gelesen?
Er funktioniert schon, nur frage ich mich, ob es ohne die Variablen 
Buffer und address geht.

Danke

[Karl H. (kbuchegg)]

java schrieb:
> Das habe ich bereits aufgemalt, aber hast du eigentlich meinen Code
> gelesen?
> Er funktioniert schon, nur frage ich mich, ob es ohne die Variablen
> Buffer und address geht.

natürlich


kein Mensch sagt, dass alle Variablen Member einer Klasse sein müssen. 
Man kann wie in jeder Programmiersprache, auch in Java funktionslokale 
Variablen anlegen

Aber Milli hat schon recht: Zum Einfügen braucht man die eigentlich 
nicht. Mal dir auf dem Papier 2 Knoten auf, die korrekt verpointert 
sind. Jetzt kommt ein 3.ter Knoten dazu und wird angehängt. In welcher 
Reihenfolge musst du welchen Pointer wohin zeigen lassen, damit sich das 
alles ausgeht und du keinen Hilfspointer brauchst? Da muss man dann eben 
ein wenig rumprobieren.

Soweit zu "buffer"

Deine "address", bzw. die Funktionen nextItem und previousItem, sind 
genau in der Art gemacht, wie man es nicht macht. Aber keine Angst, du 
bist da in guter Gesellschaft. Ich hab auch schon erfahrene 
Programmierer gesehen, die es genau so gemacht haben und das Kopfkratzen 
war dann groß wie man wohl gleichzeitig unabhängig voneinander 2 
Iterationen durch die Liste macht.
Teil des Problems ist es, dass du die Warnung objektorientiert zu 
programmierern über Bord geschmissen hast. Es ist nicht Aufgabe der 
LIste den Nachfolger eines Knotens festzustellen, sondern das macht der 
Knoten gefälligst selber. Deine address Variable muss da raus. Der 
Verwender der Liste muss das selber verwalten. d.h. er befragt die 
Liste: welches ist dein erster Knoten? Und dann befragt er den Knoten 
selber: Welches ist dein Nachfolger. SOlange, bis ein Knoten kommt, der 
von sich sagt: Ich hab keinen Nachfolger mehr.
Der Verwender in main befragt also nicht die Liste mittels "Ich brauche 
den Nachfolger", sondern er befragt die Liste mittels "Ich brauche den 
Nachfolger VON"

[Karl H. (kbuchegg)]

java schrieb:
> @Karl Heinz,
>
> mit dem was du mir gepostet hast bin ich übrigends auf keinen grünen
> Zweig gekommen, ich habe es nicht so recht verstanden.

Was genau hast du daran nicht verstanden?

Du willst das alles so benutzen können (in main())

    Natset liste = new Natset();
    
    //Listenelemente hinzufügen
    liste.append( new MyNode(1) );
    liste.append( new MyNode(2) );
    liste.append( new MyNode(3) );
    liste.append( new MyNode(4) );
    liste.append( new MyNode(5) );

    MyNode loop = liste.first();
    while( loop != null ) {
      System.out.println( loop );
      loop = liste.next( loop );
    }

Ich denke, du hast schon mal eine Liste geschrieben? Dann musst du doch 
wissen, wie man sowas benutzt.

[Läubi .. (laeubi)]

Karl Heinz Buchegger schrieb:
> Deine address Variable muss da raus. Der
> Verwender der Liste muss das selber verwalten. d.h. er befragt die
> Liste: welches ist dein erster Knoten? Und dann befragt er den Knoten
> selber: Welches ist dein Nachfolger. SOlange, bis ein Knoten kommt, der
> von sich sagt: Ich hab keinen Nachfolger mehr.

Ich sag jetz mal "jein" ;)
Dafür wurde in Java die Collection API erfunden insbesondere der 
Iterator/Enumeration.
http://download.oracle.com/javase/6/docs/api/java/util/Enumeration.html

Eine solche Liste sollte also idealerweise eine Methode:

Iterator<MyNode> getIterator()
Iterator<MyNode> getReverseIterator()

Soviel erstmal zur allgemeinen Verwirrung ;)

Karl Heinz Buchegger schrieb:
> Ich denke, du hast schon mal eine Liste geschrieben? Dann musst du doch
> wissen, wie man sowas benutzt.

Deshalb hab ich ja vorher gefragt welche Operationen den implementiert 
werden sollen...

[Purzel H. (hacky)]

> public int nextItem()
> public int previousItem()

weshalb int ? Da moechte man den pointer auf den Knoten bekommen.
Das Item zieht man aus dem knoten selbst. Nur dan kann man in einem Loop 
weitermachen.

> public void append(int a)
> public void setStart()

weshalb void ? Da moechte man den pointer auf den Knoten bekommen.

[java (Gast)]

Also jetzt habe ich es komplett ohne Hilfsvariablen gemacht.
Jeder Knoten gibt seinen nächsten zurück.
Und jeder Knoten erzeugt seinen Nachfolger, wobei nur der letzte Knoten 
einen erzeugen sollte. Der Startknoten könnte das zwar auch, ist aber 
nicht gerade sinnvoll.

public class Aufgabe10 {

  public static void main(String[] args) {
    // System.out.println("hello");

    // Neue Liste erzeugen
    Natset liste = new Natset();

    // Startpunkt erstellen
    liste.setStart();

    liste.addElement(1);
    liste.addElement(2);
    liste.addElement(3);
    liste.addElement(4);

    liste.printList();

  }

}


public class Natset {

  private MyNode start;
  private MyNode last;
  private int size;

  public Natset() {
  }

  public void setStart() {
    // Start festlegen
    start = new MyNode();
    last = start;
  }

  public void addElement(int a) {
    last = last.append(a);
    size++;
  }  
  
  public void printList()
  {
    MyNode x;
    x = start;
    while(x.getNext() != null)
    {
      x = x.getNext();
      System.out.println(x.getValue());      
          
    }    
  }

  public int getSize() {
    return size;
  }

}



public class MyNode {

  private int value;
  private MyNode next;
  private MyNode previous;

  public MyNode() {
  }

  public MyNode append(int a) {
    next = new MyNode();
    next.previous = this;
    next.setValue(a);
    return next;
  }

  public int getValue() {
    return value;
  }

  public void setValue(int m) {
    value = m;
  }

  public MyNode getNext() {
    return next;
  }

  public MyNode getPrevious() {
    return previous;
  }

}

[Karl H. (kbuchegg)]

> Dafür wurde in Java die Collection API erfunden insbesondere der
> Iterator/Enumeration.
> http://download.oracle.com/javase/6/docs/api/java/util/Enumeration.html
>
> Eine solche Liste sollte also idealerweise eine Methode:
>

Iterator<MyNode> getIterator()
> Iterator<MyNode> getReverseIterator()

Soviel erstmal zur
> allgemeinen Verwirrung ;)

Ich wollte ihn nicht auch noch mit Iteratoren verwirren. Klar sind 
Iteratoren die bessere Lösung.


> Der Startknoten könnte das zwar auch, ist aber nicht gerade sinnvoll.

Ich kann der Idee noch nichts abgewinnen, dass eine leere Liste aus 
einem sonst nicht weiter benutzten Startknoten besteht nicht. Aber ok, 
damit kann man leben und manche Dinge werden dann tatsächlich einfacher.

Viel lästiger finde ich allerdings, wenn ich explizit setStart aufrufen 
muss. Wozu soll das gut sein? Ohne kann ich die Liste sowieso nicht 
verwenden, also kann auch gleich der Konstruktor die Liste so 
herrichten, dass ich keinen Fehler (setStart aufrufen vergessen) machen 
kann. Deswegen gibt es Konstruktoren, die ein Objekt erst mal in einen 
benutzbaren Zustand bringen, damit sich ein Verwender nicht mit 
'Kleinigkeiten', wie dem Aufrufen von Initialisierungsfunktionen, 
beschäftigen müssen. Der Unterschied: Der Konstruktur wird IMMER 
aufgerufen, wenn ein Objekt erzeugt wird, das kann ich als Verwender 
daher nicht vergessen. setStart ist daher so nicht notwendig, was 
allerdings nicht heißt, das sie sinnlos wäre. Aber in einem anderen 
Zusammenhang. Durch die Garbage Collection von Java übernimmt dein 
'setStart' die Funktionalität: lösche die komplette Liste. Also nenne 
die Funktion auch entsprechend und sorge dafür, dass clear immer 
aufgerufen werden kann und das richtige vollständig macht.

  public Natset() {
    clear();
  }

  public void clear() {
    start = new MyNode();
    last = start;
    size = 0;
  }

[java (Gast)]

Soweit mal Danke,

ich habe die Methode addElement() mal geändert:

public void addElement(int a) {
    if (size == 0) {
      start = new MyNode();
      last = start;
      start.setValue(a);
    } else {
      last = last.append(a);
    }
    size++;
  }

Jetzt gibt es nur dann einen Knoten, wenn wirklich ein Element 
hinzugefügt wird.
Und den Konstruktor hätte ich vorher tatsächlich verwenden können, aber 
ich bin noch nicht so fit mit Java, aber danke für den Hinweis.

[java (Gast)]

Ach ja und löschen der Liste mache ich einfach mit

public void clear()
{
  start = null;
  last = null;
  size = 0;
}