Java List Implementierung?

Wenn man in Java ne eigene Liste implementieren will, also mit Hilfe von Klassen, dann gibt es ja bei der Liste immer den Knoten Head/Front

der ist erstmal auf null aber wenn ein Element drin ist wird dieser Knoten auf diesen Wert gesetzt und nicht nur Front.next sondern der ganze knoten irgendwie, hat man dann nicht Redundanz wenn Front den value hat und das jeweilige Element

Answer 1

[Aventus9999]

Es gibt keine Redundanz, da Front (oder Head) nur als Verweis auf das erste Element in der Liste dient. Der Wert des ersten Elements wird nicht in der Liste selbst gespeichert, sondern im Knoten, der das Element repräsentiert...

Comments

[Cream31415926]

Aber ich mache doch Front = newNode;

wieso kann ich nicht einfach zunächst Front.value = null;

Front.next = newNode;

wie auch dann zwischen zwei knoten

[regex9]

@Cream31415926

Ganz am Anfang, wenn die Liste noch leer ist, zeigt der Startknoten (ich nenne ihn head, statt Front) auf null. Es gibt eben noch keinen einzigen Knoten. Die Anweisung

head.value = null; // exception

würde folglich zu einem Ausnahmefall / Programmabbruch führen. Von einem nicht-existenten Objekt (bzw. Nichts) kannst du keine Eigenschaften setzen.

Es muss erst ein Knotenobjekt erstellt werden.

head = new Node();
head.value = // first list entry value ...

Das ist der allererste Knoten in der Liste. Ein Nachfolger für diesen Knoten wird erst angelegt, sobald der Liste ein weiterer Wert hinzugefügt werden soll.

Answer 2

[regex9]

Eine Liste besteht aus Knoten, jeder Knoten dient als Container für einen Wert. Bildlich könnte man sich einen Güterzug vorstellen, bei dem jeder Waggon einem Knoten entspricht und eine bestimmte Ware beinhaltet. Waggon und Ware sind voneinander getrennt (bzw. nicht ein- und dasselbe Objekt), um zwischen konkreten Daten (Ware) und Struktur (Waggon) klar zu unterscheiden. Der Waggon hat Kupplungsteile zu anderen Waggons implementiert, nicht die Ware. Es wäre unflexibel, wenn die Ware selbst Kupplungsteile (u.ä.) mitliefern müsste.

Auf Programmebene kann man es nochmal wie folgt verdeutlichen:

class MyList<T> {
  private T head;

  void add(T value) {
    if (head == null) {
      head = value;
      return;
    }

    // find last entry ...
    last.setNext(value);
  }
}

Bei dieser Implementation hast du das Problem, dass die Typen, die in die Liste sollen, auch eine Methode setNext besitzen müssen. Das heißt, eine Liste für Standardtypen wie String oder Integer klappt schon einmal nicht. Du müsstest eigene Subtypen o.ä. erstellen, die die entsprechende Methode definieren.

Zudem würdest du für die Liste speicherbare Typen mit Eigenschaften/Methoden belasten, die logisch betrachtet eigentlich nicht in sie hineingehören. Es sind doch listenspezifische Logiken.

Mit einem Container dazwischen besteht das Problem nicht, denn der Container kümmert sich um die Strukturimplementation.

class MyList<T> {
  private Node<T> head;

  void add(T value) {
    Node<T> node = new Node<T>(value);

    if (head == null) {
      head = node;
      return;
    }

    // find last node ...
    last.setNext(node);
  }
}

class Node<T> {
  private Node<T> next;

  private T value;

  public Node(T value) {
    this.value = value;
  }

  public void setNext(Node<T> nextNode) {
    next = nextNode;
  }
}

Wenn eine Liste noch leer ist (also der erste Knoten null ist bzw. noch nicht existiert) und einen Wert hinzugefügt bekommen soll, wird erst einmal ein neuer Knoten erstellt und dieser als der neue Startknoten vermerkt. Die Liste besteht dann aus genau einem Knoten.

Der neue Wert wird innerhalb des neu angelegten Knotens angelegt.

Node(Irgendein Wert)

Sobald der Liste ein zweiter Wert angehängt wird, wird wieder ein neuer Knoten kreiert und der zweite Wert in diesem abgelegt.

Node(Irgendein Wert) ---> Node(Noch ein Wert)