Doppelt verkettete Liste

[jefo]

Hallo,

wer kann mir helfen bei der Implementierung von doppelt...
Was soll dieser Rückgabewert List? List ist doch interface.
ich weiss wir haben es schon 1000 mal gemacht aber trotzdem interessiert mich es mit dem Interface.

interface List {
    int len();               // liefert die Laenge der Liste
    boolean isempty();       // prueft, ob die Liste leer ist
    Object first();          // liefert das erste Element der Liste
    Object last();           // liefert das letzte Element der Liste
    List rest();             // liefert die Liste ohne das erste Element
    void append(Object o);   // haengt ein Objekt an das Ende der Liste an
    void print();            // gibt die Elemente mit Hilfe der toString()-Methode aus
    List remove(Object o);   // entfernt alle Objekte o aus der Liste und liefert diese
                             // Liste als Ergebnis
    List removeLast(Object o, int n);
                             // entfernt die letzten n Vorkommen von Objekten o aus der
                             // Liste und liefert die Liste als Ergebnis. Sind weniger
                             // als n Vorkommen von Objekten o in der Liste enthalten,
                             // stimmt die Semantik des Aufrufs von
                             // removeLast(Objekt o, int n) mit derjenigen von
                             // remove(Object o) ueberein.
}

class Test {
    public static void main(String[] argf) {
        Test.test(new PList());
    }
    static void test(List l) {
        // Liste aufbauen
        for (int i=0; i<6; i++) l.append(new Integer(i));
            l.append(new Integer(2));
            l.append("Hallo World");
        // Liste ausgeben
        l.print();
        System.out.println();
        // Bis zu 3 Integerzahlen mit Wert 2 loeschen und Liste ausgeben
        //l.removeLast(new Integer(2), 3);
        //l.print();
        System.out.println();
        // Alle Vorkommen von ’Hallo World’ loeschen, Floats hinzufuegen
        //l.remove("Hallo World");
        for (int i=0; i<4; i++) l.append(new Float(i/0.008));
        // Ausgabe der enthaltenen Elemente ueber l.first()
        while (!l.isempty()) {
            System.out.println(l.first().toString());
            //l = l.rest();
        }
    }
}

Implementieren Sie die Schnittstelle List in einer Klasse PList als doppelt
verkettete Liste so, dass das Programm test.java
folgende Ausgabe liefert:

0
1
2
3
4
5
2
Hallo World
0
1
3
4
5
Hallo World
0
1
3
4
5
0.0
125.0
250.0
375.0

ich habe es versucht aber habe feststellen müssen, dass anstatt PList List Rückgabetyp ist. das verwirrt mich nur.

class PList implements List{
  private PList vorcheriger;
  private PList naechster;
  private PList first;
  private Object o;

  public PList(){
    first = null;
  }

  private PList(Object o){
    this.o = o;
  }

  public boolean isempty(){
    return(first == null);
  }

  public void append(Object o){
    PList neu = new PList(o);
    neu.naechster = first;
    neu.vorcheriger = null;
    if(neu.naechster != null){
      PList temp = neu.naechster;
      temp.vorcheriger = neu;
    }
    first = neu;
  }

  public Object first(){
    return(first.o);
  }

  public void print(){
    PList aktuell = first;
    while(aktuell != null){
      aktuell.toString();
    }
  }


  int len(){

  }

  Object last(){
       blabla
  }
  List rest(){
     blabla
  }
  List remove(Object o){
       blabla
  }
  private List removeLast(Object o, int n){
          blabla
  }
}

 

[Beni]

Irgendetwas implementiert ja dieses Interface. Und das kannst du dort zurückgeben. (Eben halt etwas vom Typ "List").

Und hier ist wohl gedacht, dass du sowas schreibst:

public List remove( Object o ){
  // blabla

  return this;
}

 

[Guest]

Kannst Du mir es etwas näher beschreiben. (eine Methode implementieren oder etwas ähnliches)

Danke.

 

[Beni]

"implementieren" ist ein Wort, das man auch mit "schreiben", "coden" oder "herstellen" übersetzt.

"implementieren" ist auch die dt. Übersetzung von "implements" und wird verwendet, wenn eine Klasse ein Interface implementieren soll.

z.B. PList implements List heisst nichts anderes als "PList implementiert alle Methoden die in List vorgegeben sind"

Bsp:
Die Implementation von "first()"

  public Object first(){
    return(first.o);
  }

 

[Guest]

Ok, verstanden. Aber als Beispiel wie soll ich diese Methode implementieren:

public List removeLast(Object o, int n){ 
          blabla 
  }

 

[Beni]

( Ich frage mich, ob es nicht sinnvoller wäre, wenn die Daten in einer "Node"-Klasse gespeichert wird, und die PList nur die Schnittstelle nach aussen ist. Das wäre auch der normale Weg eine Liste zu schreiben.

Beispiel, als Pseudocode:

public void append( Object o ){
  Node node = new Node( o );
  lastNode.setNext( node );
  node.setPreviousNode( lastNode );
  lastNode = node;
}

)



So, aber falls du an deiner Lösung festhalten willst:
Hier ein Denkanreiz. Diese Version entfernt die Elemente von vorne her (im Interface wird gesagt, es soll von hinten her gehen. Aber das umschreiben wird ja kein Problem sein).

public List removeLast(Object o, int n){
  PList list = first;

  for( int i = 0; i < n && list != null ; i++ ){
    if( list.o == o ){
      PList prev = list.vorcheriger;

      if( prev != null )
        prev.naechster = naechster;

      if( naechster != null )
        naechster.vorcheriger = vorcheriger;
    }

    if( list == first )
      first = list.naechster;

    list = list.naechster;
  }
  return first;
}

Beni

 

[Guest]

Ok ich habe diese Klasse so entwickelt und die Methoden so implementiert ;-)
Aber mit der Methode rest() habe ich Schwierigkeiten es funktioniert nicht wie es sein sollte (siehe Ausgabe). Vielleicht ein kleines Tipp. Ich habe zusätzlich die Methode
printBack() implementiert um zu sehen, ob die Objekte richtig ausgehängt werden.
Acha die remove() Methoden sind ziemlich kompliziert geworden, vielleicht geht es einfacher. Vielen Dank für jegliche Hilfe.

public class PList implements List{
  private PList vorcheriger;
  private PList naechster;
  private PList first;
  private PList letzte;
  private Object o;

  public PList(){
      first = null;
  }

  private PList(Object o){
      this.o = o;
  }

  public boolean isempty(){
      return(first == null);
  } 

  public void insert(Object o){
      PList neu = new PList(o);
      neu.naechster = first;
      neu.vorcheriger = null;
      if(neu.naechster != null){
          PList temp = neu.naechster;
          temp.vorcheriger = neu;
      }
      first = neu;
  }
  public void append(Object o){
    PList neu = new PList(o);
    if(first == null){
      neu.vorcheriger = null;
      neu.naechster = null;
      first = neu;
      letzte = first;
    }else{
      letzte.naechster = neu;
      neu.vorcheriger = letzte;
      neu.naechster = null;
      letzte = neu;
    }
  }

  public Object first(){
      return (first.o);
  }

  public void print(){
    System.out.println("od przodu: "); 
      PList aktuell = first;
      while(aktuell != null){
          System.out.println(aktuell.o.toString());
          aktuell = aktuell.naechster;
      }
  }
  
  public void printBack(){
      System.out.println("od tylu: "); 
      PList aktuell = letzte;
      while(aktuell != null){
          System.out.println(aktuell.o.toString());
          aktuell = aktuell.vorcheriger;
      }
  }

  public int len(){
    PList aktuell = first;
    int i = 0;
    while(aktuell != null){
        i++;
        aktuell = aktuell.naechster;
    }
      return i;
  }

  public Object last(){
      return letzte.o;
  }

  public List rest(){
    first = first.naechster;
    return first;
  }

  
  
  public List remove(Object o){  
    PList aktuell = letzte;
      while(aktuell != null){
        if(aktuell.o.toString().equals(o.toString())){
          PList prev = aktuell.vorcheriger;
          if(prev != null){ 
            prev.naechster = aktuell.naechster;
          }
          if(aktuell.naechster != null){
            aktuell.naechster.vorcheriger = aktuell.vorcheriger;
          }else{
            letzte = aktuell.vorcheriger;
          }
          if(prev != null){
            aktuell = prev.vorcheriger;
          }else{
            first = aktuell.naechster;
          }
          
        }else{
          aktuell = aktuell.vorcheriger;
        }
      }
      return letzte;
    }

  public List removeLast(Object o, int n){
      PList aktuell = letzte;
      int z=0;
      while(aktuell != null){
        if(z == n) break;
          if(aktuell.o.toString().equals(o.toString())){
            z++;
            PList prev = aktuell.vorcheriger;
            if(prev != null){ 
              prev.naechster = aktuell.naechster;
            }
            if(aktuell.naechster != null){
              aktuell.naechster.vorcheriger = aktuell.vorcheriger;
            }else{
              letzte = aktuell.vorcheriger;
            }
            if(prev != null){
              aktuell = prev.vorcheriger;
            }else{
              first = aktuell.naechster;
            }
          
          }else{
            aktuell = aktuell.vorcheriger;
          }
        }
        return letzte;
      }
}