Ringstruktur-Liste

[javacc123]

Hallo liebe Community,

ich versuche eine Aufgabe zu doppelt verketteten Listen, die als Ringstruktur abgebildet sind (also das letzte Element zeigt auf das erste usw.), zu lösen.
Das gelingt mir nicht so ganz.

Zur Aufgabe: Die Implementierung des Ringes soll allein über die Klasse RingElement realisiert werden. Aufgrund der Ringstruktur bedarf es keines ausgezeichneten Startelements.

Ich soll eine generische Klasse RingElement schreiben, die einen Vorgänger und Nachfolger als Attribut besitzt.
Dann soll ich eine Methode insertRingElement implementieren, die ein übergebenes RingElement-Objekt als Nachfolger des aktuellen Ringelements einfügt.
Und dann soll ich noch eine Methode getRingElements implementieren , die eine Liste der in der Ringstruktur erhaltenen RingEelement-Objekte zurückliefert.

Ich habe mich versucht und das ganze sieht bei mir so aus:

public class RingElement<T> {
  private Object data;
  private RingElement<T> newest;
  private RingElement<T> first;
  private RingElement<T> succecessor;
  private RingElement<T> predecessor;
  int size = 0;

  public RingElement (){}
  // alle Getter-Setter Methoden

  // Methode zum Einfügen
  public void insertRingElement (RingElement<T> new){
    if(newest==null) {
      newest = new;
      first = newest;
      newest.succecessor = newest;
      newest.predecessor = newest;
      size++
    } else {
      if (size == 1) {
        newest.succecessor = new;
        newest.predecessor = newest;
        newest = newest.succecessor;
      } else {
        newest.succecessor = new;
        newest.predecessor = newest;
        newest = newest.succecessor;
        newest.succecessor = first;
      }
    }
  }
  // Alle Elemente in der Liste auslesen
  public void getRingElements(){
    for (T element : data){
      System.out.println(element);
    }
  }
}

 

[VfL_Freak]

Moin,

hast Du auch eine konkrete Frage ??

Gruß Klaus

 

[javacc123]

ob mein Code so in Ordnung ist,
bzw. ob er mit der obigen Aufgabenstellung übereinstimmt

 

[thecain]

Stimmt nicht, das neu Eingefügte muss auch einen succecessor und predecessor haben.

Dann muss vom Neuen der Succecessor wieder zurückzeigen mit dem predecessor und vom predecessor der successor auf das Neue zeigen.

Kannst du ja einfach testen, in dem du einmal mit vorwärts durch gehst und einmal rückwärts.

Ist ja eigentlich wie ein in der Mitte einfügen bei einer Doubly linked list

else{
        newest.succecessor.predecessor=new; // o x<-o
        new.succecessor = newest.succecessor; //  o x <-> o
        new.predecessor = newest // o <- x <-> o
        newest.succecessor= new; // o<-> x <-> o
        newest = new // o <-> x <-> o Newest setzen

so müsste mMn das else sein (x ist das neu eingefügte.

 

[javacc123]

Stimmt nicht, das neu Eingefügte muss auch einen succecessor und predecessor haben.

Dann muss vom Neuen der Succecessor wieder zurückzeigen mit dem predecessor und vom predecessor der successor auf das Neue zeigen.

Kannst du ja einfach testen, in dem du einmal mit vorwärts durch gehst und einmal rückwärts.

Ist ja eigentlich wie ein in der Mitte einfügen bei einer Doubly linked list

else{
        newest.succecessor.predecessor=new; // o x<-o
        new.succecessor = newest.succecessor; //  o x <-> o
        new.predecessor = newest // o <- x <-> o
        newest.succecessor= new; // o<-> x <-> o
        newest = new // o <-> x <-> o Newest setzen

so müsste mMn das else sein (x ist das neu eingefügte.

hm hat mein neu eingefügtest Element das nicht?

else {
        newest.succecessor = new;
        newest.predecessor = newest;
        newest = newest.succecessor;
        newest.succecessor = first;
      }

So wie ich mir das denke, eventuell denke ich falsch:
Sagen wir in der Struktur sind 2 Elemente ein Knoten mit 1 und ein anderer mit 2. Diese sind Verknüft als Vorgänger und Nachfolger.
Wenn ich jetzt einen Knoten 3 einfüge und den Code durchlaufe, dann ist ja von vornherein die 2 mein newest.
Es wird die 3 eingefügt und als Nachfolger der 2 gesetzt, danach wird die 2 als Vorgänger von newest gesetzt. Anschließend ist die 3 mein neues newest und hat als Nachfolger first, also den ersten Knoten der am anfang gesetzt wurde und als Vorgänger doch die 2 oder irre ich mich?

Und was sagst du mir mit newest.succecessor.predecessor=new?

mfg

 

[thecain]

Dein neu eingefügtes hat ja gar nichts, ausser das first als nachfolger mit der letzten Zeile

newest.predecessor = newest;

damit setzt du ja den vorgänger auf sich selber

Und was sagst du mir mit newest.succecessor.predecessor=new?

vom zuletzt eingefügten den Nachfolger, dessen Vorgänger ist das neue

 

[javacc123]

Meine Intention ist ja, dass ich alle vorgänger und nachfolger vorher definiere und dann erst am Ende, so wie du auch das newest umsetzte.
Mit:

newest.predecessor = newest;

Setzte ich ja den vorgänger auf sich selbst, um somit auf das alte Element zugreifen zu können, da ich ja am Ende das neue Element auf newest mache.
Somit wäre doch der newest.predecessor das alte newest, so wie ich das oben meine und da ich am ende das new = newest deklariert habe, hat er doch einen vorgänger.
Oder ist das einfach ein falscher Gedanke?

newest.succecessor.predecessor = new;

Sry aber das verstehe ich immernoch nicht so ganz, könntest du evtl ein genauers Beispiel dazubringen?
Das neu eingefügte ist ja vom alten neu eingefügten der Nachfolger, soweit klar.
Und sagst du mit zusätzlich .predecessor das sozusagen das alte neue Elemente direkt der Vorgänger von dem neuen Element ist?

mfg

 

[Flown]

Also ihr denkt wirklich alle etwas zu kompliziert.

Die Aufgabenstellung besagt etwas ganz anderes: Nur zwei Attribute (previous, next) und das zu speichernde Element.
Es besagt, es braucht kein ausgezeichnetes Startelement, da die RingElement Klasse nur als Struktur und noch nicht als Liste/etc. dient. Somit hat jemand anderes das Problem des Startelements übrig.
Die Implementierung soll ein Knoten nach DIESEM (this) einfügen. Danach sollen alle Datenelemente in eine Liste gespeichert und zurückgeliefert werden.

Dann sieht das ganze so aus:

public class Test {
   
   public static void main(String... args) {
     RingElement<Integer> r = new RingElement<>(1);
     r.insertRingElement(new RingElement<>(2));
     r.insertRingElement(new RingElement<>(3));
     r.insertRingElement(new RingElement<>(4));
     System.out.println(r.getRingElements());
   }
}

class RingElement<T> {
   private RingElement<T> previous, next;
   private T data;
   
   public RingElement(T data) {
     this.data = data;
     this.next = this.previous = this;
   }
   
   public void insertRingElement(RingElement<T> re) {
     re.previous = this;
     re.next = this.next;
     next.previous = re;
     this.next = re;
   }
   
   public List<T> getRingElements() {
     List<T> elements = new ArrayList<>(Collections.singleton(data));
     for (RingElement<T> re = this.next; re != this; re = re.next) {
       elements.add(re.data);
     }
     return elements;
   }
}

 

[javacc123]

Also ihr denkt wirklich alle etwas zu kompliziert.

Die Aufgabenstellung besagt etwas ganz anderes: Nur zwei Attribute (previous, next) und das zu speichernde Element.
Es besagt, es braucht kein ausgezeichnetes Startelement, da die RingElement Klasse nur als Struktur und noch nicht als Liste/etc. dient. Somit hat jemand anderes das Problem des Startelements übrig.
Die Implementierung soll ein Knoten nach DIESEM (this) einfügen. Danach sollen alle Datenelemente in eine Liste gespeichert und zurückgeliefert werden.

Dann sieht das ganze so aus:

public class Test {
  
   public static void main(String... args) {
     RingElement<Integer> r = new RingElement<>(1);
     r.insertRingElement(new RingElement<>(2));
     r.insertRingElement(new RingElement<>(3));
     r.insertRingElement(new RingElement<>(4));
     System.out.println(r.getRingElements());
   }
}

class RingElement<T> {
   private RingElement<T> previous, next;
   private T data;
  
   public RingElement(T data) {
     this.data = data;
     this.next = this.previous = this;
   }
  
   public void insertRingElement(RingElement<T> re) {
     re.previous = this;
     re.next = this.next;
     next.previous = re;
     this.next = re;
   }
  
   public List<T> getRingElements() {
     List<T> elements = new ArrayList<>(Collections.singleton(data));
     for (RingElement<T> re = this.next; re != this; re = re.next) {
       elements.add(re.data);
     }
     return elements;
   }
}

Ok jetzt bin ich komplett raus.
Also du meinst es besteht schon eine Ringstruktur und man soll das neue Element einfach nur nach dem letzten neu eingefügt hinzunehmen?

Also ist this der letzte Knoten der eingefügt wurde?

   public void insertRingElement(RingElement<T> re) {
     re.previous = this;
     re.next = this.next;
     next.previous = re;
     this.next = re;

Aber du setzt ja this gar nicht um, oder seh ich das falsch. Wenn wir einen Knoten einfügen und die Methode durchlaufen und dann wieder einen neuen Knoten einfügen, wird doch mit dem alten this (2 Knoten zuvor) verglichen oder?

Sagen wir, wie haben eine Ringstruktur mit 2 Knoten.
Dann wird gesagt, dass der vorgänger vom neuen das this ist(der zuletzt eingefügt).
Der Nachfolger von den zuletzt eingefügt (also sozusagen das erste Element) ist dann auch den Nachfolger von dem neueingefügt.
Dann verstehe ich den Code nicht weiter.
Was sagst du mit

next.previous = re;
this.next = re;

Das die 2 Attribute jetzt das re sind? Also das this oder wie?

mfg

 

[Flown]

Es steht in deiner Aufgabenstellung nichts von dem, dass hinter dem letzteingefügtesten Element eingefügt werden muss. Sondern die Aufgabe war, hinter dem aktuellen Element einzufügen.
Abfolge:

[] <- leere Liste
Erzeugen eines RingElements
this (previous -> this, next -> this) <=> [this] <- Liste mit einem Element
Einfügen eines zweiten Elements hinter dem ersten
this (previous -> other, next -> other), other (previous -> this, next -> this) <=> [this <-> other] <- Liste mit zwei Elementen

Auf jedenfall kommt es darauf an wo (also mit welchem Objekt) du dein insertRingElement aufrufst, darum gibt es kein ausgezeichnetes Startelement.

Wie schon gesagt die Struktur über den RingElementen, die dann die Liste abbilden sind dafür verantwortlich. Hier ein Beispiel:

Spoiler: Liste mit RingElement

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;

public class Test {
   
   public static void main(String... args) {
     MyList<Integer> myList = new MyList<>();
     System.out.println(myList.size());
     System.out.println(myList);
     for (int i = 0; i < 10; i++) {
       myList.add(i);
     }
     System.out.println(myList.size());
     System.out.println(myList);
     for (int i = 1; i < 10; i++) {
       myList.prepend(-i);
     }
     System.out.println(myList.size());
     System.out.println(myList);
     
     for (Integer i : myList) {
       myList.remove(i);
       System.out.println(myList);
       System.out.println(myList.size());
     }
   }
}

class MyList<T> implements Iterable<T> {
   
   private RingElement<T> start = null;
   private int size = 0;
   
   public MyList() {
   }
   
   public int size() {
     return size;
   }
   
   public boolean isEmpty() {
     return size == 0;
   }
   
   public void add(T element) {
     if (isEmpty()) {
       start = new RingElement<>(element);
     } else {
       start.previous.insertRingElement(new RingElement<>(element));
     }
     size++;
   }
   
   public void prepend(T element) {
     add(element);
     start = start.previous;
   }
   
   public boolean contains(T element) {
     if (isEmpty()) {
       return false;
     }
     RingElement<T> re = start;
     do {
       if (Objects.equals(re.data, element)) {
         return true;
       }
       re = re.next;
     } while (re != start);
     return false;
   }
   
   public void remove(T element) {
     if (contains(element)) {
       if (size == 1) {
         start = null;
       } else {
         RingElement<T> re = start;
         do {
           if (Objects.equals(re.data, element)) {
             if (re == start) {
               start = start.next;
             }
             re.removeRingElement();
             break;
           }
           re = re.next;
         } while (re != start);
       }
       size--;
     }
   }
   
   @Override
   public Iterator<T> iterator() {
     return start.getRingElements().iterator();
   }
   
   @Override
   public String toString() {
     return isEmpty() ? "[]" : start.getRingElements().toString();
   }
   
   class RingElement<E> {
     private RingElement<E> previous, next;
     private E data;
     
     public RingElement(E data) {
       this.data = data;
       this.next = this.previous = this;
     }
     
     public void insertRingElement(RingElement<E> re) {
       re.previous = this;
       re.next = this.next;
       next.previous = re;
       this.next = re;
     }
     
     public List<E> getRingElements() {
       List<E> elements = new ArrayList<>(Collections.singleton(data));
       for (RingElement<E> re = this.next; re != this; re = re.next) {
         elements.add(re.data);
       }
       return elements;
     }
     
     public void removeRingElement() {
       this.previous.next = this.next;
       this.next.previous = this.previous;
     }
   }
}

 

[javacc123]

Es steht in deiner Aufgabenstellung nichts von dem, dass hinter dem letzteingefügtesten Element eingefügt werden muss. Sondern die Aufgabe war, hinter dem aktuellen Element einzufügen.
Abfolge:

[] <- leere Liste
Erzeugen eines RingElements
this (previous -> this, next -> this) <=> [this] <- Liste mit einem Element
Einfügen eines zweiten Elements hinter dem ersten
this (previous -> other, next -> other), other (previous -> this, next -> this) <=> [this <-> other] <- Liste mit zwei Elementen

Auf jedenfall kommt es darauf an wo (also mit welchem Objekt) du dein insertRingElement aufrufst, darum gibt es kein ausgezeichnetes Startelement.

Wie schon gesagt die Struktur über den RingElementen, die dann die Liste abbilden sind dafür verantwortlich. Hier ein Beispiel:

Spoiler: Liste mit RingElement

import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;

public class Test {
  
   public static void main(String... args) {
     MyList<Integer> myList = new MyList<>();
     System.out.println(myList.size());
     System.out.println(myList);
     for (int i = 0; i < 10; i++) {
       myList.add(i);
     }
     System.out.println(myList.size());
     System.out.println(myList);
     for (int i = 1; i < 10; i++) {
       myList.prepend(-i);
     }
     System.out.println(myList.size());
     System.out.println(myList);
    
     for (Integer i : myList) {
       myList.remove(i);
       System.out.println(myList);
       System.out.println(myList.size());
     }
   }
}

class MyList<T> implements Iterable<T> {
  
   private RingElement<T> start = null;
   private int size = 0;
  
   public MyList() {
   }
  
   public int size() {
     return size;
   }
  
   public boolean isEmpty() {
     return size == 0;
   }
  
   public void add(T element) {
     if (isEmpty()) {
       start = new RingElement<>(element);
     } else {
       start.previous.insertRingElement(new RingElement<>(element));
     }
     size++;
   }
  
   public void prepend(T element) {
     add(element);
     start = start.previous;
   }
  
   public boolean contains(T element) {
     if (isEmpty()) {
       return false;
     }
     RingElement<T> re = start;
     do {
       if (Objects.equals(re.data, element)) {
         return true;
       }
       re = re.next;
     } while (re != start);
     return false;
   }
  
   public void remove(T element) {
     if (contains(element)) {
       if (size == 1) {
         start = null;
       } else {
         RingElement<T> re = start;
         do {
           if (Objects.equals(re.data, element)) {
             if (re == start) {
               start = start.next;
             }
             re.removeRingElement();
             break;
           }
           re = re.next;
         } while (re != start);
       }
       size--;
     }
   }
  
   @Override
   public Iterator<T> iterator() {
     return start.getRingElements().iterator();
   }
  
   @Override
   public String toString() {
     return isEmpty() ? "[]" : start.getRingElements().toString();
   }
  
   class RingElement<E> {
     private RingElement<E> previous, next;
     private E data;
    
     public RingElement(E data) {
       this.data = data;
       this.next = this.previous = this;
     }
    
     public void insertRingElement(RingElement<E> re) {
       re.previous = this;
       re.next = this.next;
       next.previous = re;
       this.next = re;
     }
    
     public List<E> getRingElements() {
       List<E> elements = new ArrayList<>(Collections.singleton(data));
       for (RingElement<E> re = this.next; re != this; re = re.next) {
         elements.add(re.data);
       }
       return elements;
     }
    
     public void removeRingElement() {
       this.previous.next = this.next;
       this.next.previous = this.previous;
     }
   }
}

Ok verstehe, also kommt es nicht drauf an wo gestartet wird, aber die Ringstruktur muss doch erhalten bleiben. Wenn ich jetzt eine Liste mit 2 Elmente habe und hinter einem der beiden einfüge dann ist doch this der vorgänger (hinterdem ich einfüge) und this.next auch der Nachfolger von den neuen element oder nicht?

Ich verstehe diese 2 Schritte nicht:

  next.previous = re;
     this.next = re;

 

[Flown]

Stift und papier nehmen -> aufzeichnen -> verstehen.

 

[javacc123]

Ok ich habe es probiert, bitte um Korrektur:

Beispiel: Ich habe ein Ring aus 2 Elementen vorhanden. Nennen wir sie Knoten 1 und Knoten 2.
Nehmen wir an das akutelle Element ist Knoten 2.
Also füge ich meinem Knoten hinter diesem akutellen Knoten 2 ein.
Mein neuen Knoten den ich einfüge möchte, nenne ich Knoten 3.
Jetzt durchlaufe ich die Methode Zeile für Zeile:
Der Vorgänger des Knoten 3 wird this, also Knoten 2.
Der Nachfolger des Knoten 3 wird this.next also der nächste von der 2, also Knoten 1.
Der Vorgänger von dem ehemaligen Nachfolger der 2, also reden wir von Knoten 1(next.previous), wird Knoten 3.
Und der Nachfolger von this, also Knoten 2, wird Knoten 3.

Soweit richtig?

 

[Flown]

Ja so fügst du einen knoten ein.

 

[javacc123]

Ok vielen Dank dafür!

Noch eine kleine Frage zu der Methode um die Elemente in einer Liste auszugeben:

public List<T> getRingElements() {
     List<T> elements = new ArrayList<>(Collections.singleton(data));
     for (RingElement<T> re = this.next; re != this; re = re.next) {
       elements.add(re.data);
     }
     return elements;
   }

Warum wählst du oben eine ArrayList<>? und warum muss diese nicht generisch sein?

mfg

 

[Flown]

Wie schon gesagt es ist die Aufgabe, die du gepostet hast, eine Liste zurückzugeben die alle Datenelemente enthält.

List: Interface für Listen
ArrayList: gängigste - in meisten Fällen schnellste - Implementierung des List Interface

ArrayList ist doch generisch (der Diamondoperator (<>) wurde in Java 7 eingeführt und verkürzt das Initialisieren von Generischen Typen, da ja auf der linken Seite schon der Typ steht:

List<T> list = new ArrayList<>();
// Ist das gleich wie
List<T> list = new ArrayList<T>();

Der Compiler fügt die Typinforamtionen per typeinfering hinzu. HIER das JLS dazu.

 

[javacc123]

Super alles klar.

Den Diamondoperator kannte ich noch nicht.