Datentypen Doppelt verkettete Liste implementieren

[ubik]

Hallo,

ich habe Probleme bei der Implementierung einer doppelt verketteten Liste. Ich studiere an der Fernuni Hagen und habe eigentlich so ziemlich alles aus dem Skript abgeschrieben.

Wenn ich allerdings Main.java ausführe, bekomme ich eine Exception:

Exception in thread "main" java.lang.NullPointerException
at List.insert(List.java:43)
at Main.main(Main.java:7)

Offensichtlich liegt das daran, dass isempty() nicht richtig funktioniert.

Ich verstehe auch nicht, warum front() einfach return this; zurückgeben soll. Damit wird doch die Listenklasse zurückgegeben und nicht das erste Element?

Und schon gar nicht verstehe ich, wie der last-Zeiger gesetzt werden soll.

Hier ist der Code:
Main.java:

public class Main
{
   public static void main(String[] args)
   {
     List l1 = new List();

     l1.insert(l1.front(), new Elem(5.32, 1));

     Pos iterator = l1.front;

     while(!l1.eol(iterator))
     {
       iterator = l1.next(iterator);
     }
   }
}

List.java:

public class List extends Pos
{
   public Pos front, last;

   public Pos front()
   {
     return this;
   }

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

   public List empty()
   {
     return null;
   }

   public Pos next(Pos p)
   {
     return p.succ;
   }

   public boolean bol(Pos p)
   {
     return (front() == p);
   }

   public boolean eol(Pos p)
   {
     return (this.last == p);
   }

   public List insert(Pos p, Elem el)
   {
     Pos q = new Pos();
     q.value = el;
     if(!(eol(p) || isempty()))
     {
       q.pred = p;
       q.succ = p.succ;
       p.succ.pred = q;
       p.succ = q;
     }
     else
     {
       q.pred = p;
       q.succ = null;
       p.succ = q;
       pred = q; // Last-Zeiger aendern
     }
     return this;
   }

   public List delete(Pos p)
   {
     Pos q;
     if(!isempty())
     {
       if(eol(p))
       {
         if(p == this.front)
         {
           last = null;
           p.succ = null;
         }
         else
         {
           q = this.front;
           while(q.succ != p) q = q.succ;
           last = q;
           p.succ = null;
         }
       }
       else
       {
         q = p.succ;
         if(q == last) last = p;
         p.succ = p.succ.succ;
       }
     }

     return this;
   }
}

Elem.java:

public class Elem
{
   double coeff;
   int exp;

   Elem(double i, int j)
   {
     this.coeff = i;
     this.exp = j;
   }

   public double getCoeff()
   {
     return this.coeff;
   }
}

Pos.java:

public class Pos
{
   Elem value;
   Pos pred, succ;

   public Elem getValue()
   {
     return this.value;
   }
}

 

[Jardcore]

Bei üben einer doppelt verketteten Liste hilft es ungemein sich auf einem Blatt Papier mehrere Kästchen aufzumalen und diese mit jeweils 4 Zeigern zu verbinden.

        |  1  | ----> |  2  | ----> |  3  | ---> 1
3 <---- |  1  | <---- |  2  | <---- |  3  |

 

[ubik]

Hallo Jardcore,

ich weiß 🙂

Aber ich weiß halt nicht, wie ich die Klassenvariablen front und last implementiere.

public Pos front()
  {
  return this;
  }

steht im Kurstext. Aber irgendwie kann ich mir darunter so gar nichts vorstellen. Warum soll denn für das erste Listenelement das Listenobjekt zurückgegeben werden!?

 

[Jardcore]

Okay eine Position (Pos) ist wahrscheinlich das besagte Kästchen. Ein Element (Elem) ist der Wert der in der Position gespeichert ist.
Die Position muss jetzt also zwei Zeiger haben vom Typ Pos. (pred, succ). Das sind die Pfeile in dem Schaubild XD.

So wenn deine Liste nur eine Position hat, wird front() = Position und last() = Position sein.
Wenn du jetzt eine Position hinzufügst wird der succ auf die front-Position zeigen und der pred auch. Aber last() ist jetzt deine neue Position.

... hab Feierabend... werde das später Zuhause beenden 🙂

 

[ubik]

Hallo, danke für den Tipp mit dem front() = Position.

Das hat geklappt. Das Einfügen funktioniert jetzt.. Die Klasse Liste.java sieht jetzt so aus:

public class List extends Pos
{
  public Pos front, last;

  public Pos front()
  {
  return this;
  }

  public boolean isempty()
  {
  if(front() == null) return true;
  else return false;
  }

  public List empty()
  {
  return null;
  }

  public Pos next(Pos p)
  {
  return p.succ;
  }

  public boolean bol(Pos p)
  {
  return (front() == p);
  }

  public boolean eol(Pos p)
  {
  if(front() == p) return true;
  else return false;
  }

  public List insert(Pos p, Elem e)
  {
  Pos q = new Pos();
  q.value = e;
  if(!eol(p) && !isempty())
  {
  System.out.println("1");
  q.pred = p;
  q.succ = p.succ;
  p.succ.pred = q;
  p.succ = q;
  }
  else
  {
  q.pred = p;
  q.succ = null;
  p.succ = q;
  pred = q; // Last-Zeiger aendern
  }
  return this;
  }

  public List delete(Pos p)
  {
  Pos q;
  if(!isempty())
  {
  if(eol(p))
  {
  if(p == this.front)
  {
  last = null;
  p.succ = null;
  }
  else
  {
  q = this.front;
  while(q.succ != p) q = q.succ;
  last = q;
  p.succ = null;
  }
  }
  else
  {
  q = p.succ;
  if(q == last) last = p;
  p.succ = p.succ.succ;
  }
  }

  return this;
  }
}

Aber: Wie durchlaufe ich jetzt die Liste?

public class Main
{
  public static void main(String[] args)
  {
  List l1 = new List();

  Elem el1 = new Elem(5.32, 1);
  Elem el2 = new Elem(2.2, 2);
  Elem el3 = new Elem(8.7, 3);
  Elem el4 = new Elem(6.6, 4);

  l1.insert(l1.front(), el1);
  l1.insert(l1.front(), el2);
  l1.insert(l1.front(), el3);
  l1.insert(l1.front(), el4);

  Pos iterator = l1.front();


  while(!l1.eol(iterator))
  {
  System.out.println(iterator.getValue().getCoeff());
  iterator = l1.next(iterator);
  }
  }
}

Das hier zeigt einfach nichts an, wenn ich Main starte.

 

[Meniskusschaden]

@ubik: Ist es eigentlich deine Entscheidung gewesen, List von Pos abzuleiten oder ist das vorgegeben? Mir ist nämlich noch nicht klar, welche Funktion List letztendlich haben soll. Soll es lediglich die Referenzen auf das erste und letzte Element halten? Oder soll es zusätzlich noch entweder als Speicher eines Elementes dienen oder als leeres Dummy-Element am Listenanfang und Ende stehen?

 

[ubik]

Nein, es ist nicht meine Entscheidung gewesen.

Ich weiß ehrlich gesagt auch nicht, warum man eine extra Klasse für die Liste erstellt.

 

[Flown]

Also das ist ein OOP Desaster. List sollte auf jedenfall nicht von Pos ableiten, sondern verwenden. Kann man hier ein paar Veränderungen vornehmen, oder muss man das Konstrukt so verwenden wie hier gegeben?

 

[ubik]

Ich verstehe das auch nicht, wieso Pos abgeleitet wird. Im Kurstext steht:

Die Klasse List erweitert die Klasse Pos um Mehtoden, die die Operationen des Datentyps list realisieren. Eine List-Instanz ist das Kopfelement einer Liste, deren Elemente aus Pos-Instanzen bestehen.​

Offensichtlich dient die Klasse List als Kopfelement der Liste.

Aber wie soll man jetzt das Ende der Liste eol() implementieren?

 

[Jardcore]

War gestern leider zu beschäftigt.
Hab das mal so implementiert wie eine doppelt verkettete Liste grundlegend funktioniert.
Zur Vereinfachung hat mein Element nur ein String als Wert. Und habe meine Attribute ein wenig anders genannt.

public class Elem {
    String value;
  
    public Elem(String value) {
        this.value = value;
    }
  
    @Override
    public String toString() {
        return value;
    }
}

public class Pos {
    Elem elem;
    Pos next;
    Pos prev;
  
    public Pos(Elem elem) {
        this.elem = elem;
    }
  
    public Pos(Pos prev, Elem elem, Pos next) {
        this.next = prev;
        this.elem = elem;
        this.prev = next;
    }
}

public class List {
    private Pos front;
    private Pos last;
  
    public void insert(Pos pos) {
        if(isEmpty()) {
            front = pos;
            last = pos;
            front.next = last;
            last.prev = front;
            front.prev = null;
            last.next = null;
        } else {
            pos.prev = last;
            last.next = pos;
            last = pos;
        }
    }
  
    public void delete(Pos pos) {
        if(isEmpty()) {
            return;
        }
      
        if(pos == front) {
            front = null;
            last = null;
            return;
        }
      
        if(pos == last) {
            last = pos.prev;
            last.next = null;
            return;
        }
      
        Pos current = front;
        while(current != null) {
            if(current == pos) {
                current.next.prev = current.prev;
                current.prev.next = current.next;
                return;
            }
            current = current.next;
        }
    }
  
    public void deleteAll() {
        front = null;
        last = null;
    }
  
    public boolean isEmpty() {
        return front == null && last == null;
    }
  
    public Pos front() {
        return front;
    }
  
    public Pos last() {
        return last;
    }
  
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        Pos current = front;
      
        while(current != null) {
            sb.append(String.format("[ %12d | %12d |  %12d ]\n",
                    getHashCode(current.prev),
                    getHashCode(current),
                    getHashCode(current.next)));
            current = current.next;
        }
        return sb.toString();
    }
  
    private int getHashCode(Pos pos) {
        if(pos == null) {
            return -1;
        }
        return pos.hashCode();
    }
}

public class Main {
    public static void main(String[] args) {
       
        Pos pos1 = new Pos(new Elem("Eins"));
        Pos pos2 = new Pos(new Elem("Zwei"));
        Pos pos3 = new Pos(new Elem("Drei"));
        Pos pos4 = new Pos(new Elem("Vier"));
        Pos pos5 = new Pos(new Elem("Fünf"));
        Pos pos6 = new Pos(new Elem("Sech"));
        Pos pos7 = new Pos(new Elem("Sieben"));
       
        List list = new List();
        list.insert(pos1);
        list.insert(pos2);
        list.insert(pos3);
        list.insert(pos4);
        list.delete(pos5);
        System.out.println(list);
        list.delete(pos2);
        System.out.println(list);
        list.deleteAll();
        list.insert(pos7);
        list.insert(pos6);
        System.out.println(list);
        list.delete(pos6);
        System.out.println(list);
    }
}

Was mir bei deiner Implementierung aufgefallen ist, ist zu einem das Erben deiner Liste von Pos, ich weiß noch nicht genau wieso das gemacht wurde. Und zum anderen hast du ein paar grundsätzliche Schönheitsfehler.
Wenn man z.B. ein Boolean zurückgeben möchte benutzt man nicht

public boolean isCrazy()
    if(BOOLSCHER_AUSDRUCK) {
        return true;
    } else {
        return false;
    }
}

sondern:

public boolean isCrazy()
    return BOOLSCHER_AUSDRUCK;
}

 

[ubik]

Wow, danke. Und so schnell 🙂

Das erleichtert das Verständnis sehr! 🙂

 

[Jardcore]

Gibt wahrscheinlich noch Verbesserungsmöglichkeiten, ist halt quick & dirty.
Die toString() und die getHashCode() sind nur zum besseren Verständnis bei der Ausgabe.

 

[Meniskusschaden]

Ich verstehe das auch nicht, wieso Pos abgeleitet wird. Im Kurstext steht:

Die Klasse List erweitert die Klasse Pos um Mehtoden, die die Operationen des Datentyps list realisieren. Eine List-Instanz ist das Kopfelement einer Liste, deren Elemente aus Pos-Instanzen bestehen.

Vielleicht ist "List erweitert die Klasse Pos" hier nicht im Vererbungssinne gemeint, sondern einfach umgangssprachlich. Andererseits kann ich mir nicht vorstellen, dass in einem Uni-Skript so nachlässig formuliert wird. Deshalb wäre vielleicht noch folgende Auslegung denkbar, in der List tatsächlich von Pos abgeleitet wird:

List repräsentiert nicht nur den Listenkopf, sondern ist gleichzeitig eine Dummy-Position. Das Attribut value wird nicht genutzt. Die Attribute succ bzw. pred zeigen auf die erste bzw. letzte Position. Im Konstruktor von List werden succ und pred auf this gesetzt. Wir hätten dann von Beginn an eine kreisförmige Liste, die anfangs leer ist, also nur sich selbst als Dummy-Pos enthält. Die durch List repräsentierte Pos dient gleichzeitig als Kennzeichnung von Listenanfang und -ende.

Das wäre zwar eine etwas eigentümliche Implementierung, hätte aber immerhin den Vorteil, dass man bei den insert-, delete-, next- und previous-Operationen keinerlei Fallunterscheidungen benötigt und auch nichts auf null setzen oder abfragen muß. Vielleicht hat der Skript-Autor etwas Ähnliches im Sinn gehabt. Es würde zumindest zu ein paar rätselhaften Aussagen passen.

 

[Jardcore]

Die Überlegung hatte ich auch schon, hatte es auch zu beginn als zirkuläre doppelt verkettete Liste implementiert. Da hier aber nichts davon stand, also zirkulär sollte in der Uni in diesem Zusammenhang schon gefallen sein, habe ich meine Vorschlag als normale doppelt verkettete Liste implementiert.