Workshop verkettete Liste

Eine Verkettete List ist eine dem Array ähnliche Datenstruktur, jedoch besteht jedes Item in der Liste aus einem Objekt mit zwei Eigenschaften:

• der wert Eigenschaft, die den eigentlichen Inhalt des Knoten enthält.
• die naechster Eigenschaft, welche auf das nächste Objekt in der Liste verweist.

The linked list data structure value can be of any valid JavaScript data types (string, number, boolean, object, etc).

Eine verkettete Liste kann man sich als eine Serie von aufgehängten Früchtekörben vorstellen:

Bei der Analogie Früchtekorb sind die Knoten für die Aufnahme von Früchten gedacht. Eine verkettete Liste kann für alle gültigen Datentypen konzipiert werden (string, number, boolean, object etc.). Das Objektdiagramm zeigt die Idee vom Stativ, das auf den ersten Knoten zeigt und die rekursive Struktur der Knoteneigenschaft naechster, die erneut auf einen Knoten zeigt.

Die Illustration zeigt eine typische Verkettete Liste, die nur über den Zeiger erster des Objekts Stativ zugänglich ist:

Werfen wir einen Blick auf die folgende basale Verkettete Liste, welche drei Items aufweist:

Die Verkettete Liste erscheint in der Konsole als Serie von Objekten. Grafisch lässt sich diese Struktur wie folgt als am Stativ hängende Liste darstellen:

Obwohl eine Verkettete List einem Array gleicht, ist der Zugriff auf ein bestimmtes Element komplizierter und langsamer, da kein direkter Zugriff auf ein bestimmtes Element über einen Index möglich ist. Man muss die Liste vom Kopf her bis zum gewünschten Element durchlaufen. Das LIFO-Prinzip (Last in – First out) lässt sich mit dieser Art Liste jedoch bestens realisieren.

Für einen schnelleren Zugang zum letzten Element der Liste, könnte man die Stativ-Klasse mit einem zweiten Zeiger letzter ergänzen. Dies würde die Implementierung einer Warteschlage nach dem FIFO-Prinzip (First in – First out) vereinfachen.

Folgende drei Varianten von Verketteter Listen sind verbreitet:

• Einfach verkettete Liste: jeder Knoten hat nur einen Zeiger auf den nächsten Knoten.
• Doppelt verkettete Liste: jeder Knoten hat je einen Zeiger auf den nächsten und auf den vorherigen Knoten.
• Zirkulär verkettete Listen: hier zeigt der letzte Knoten der Liste auf den ersten Knoten der Liste.

Zirkuläre Listen können einfach oder doppelt verkettet sein.

Nun wollen wir in Etappen eine einfache, nicht zirkuläre Verkettete Liste implementieren.

Wir implementieren eine Liste nur mit einem Zeiger mit Namen erster, eine nach dem LIFO-Prinzip funktionierende Liste. Dazu sind folgende Etappen notwendig:

• eine Funktion erstellen, die einen neuen Knoten mit Inhalt generiert
• die Klasse stativList inkl. Konstruktor erstellen
• die Klasse um die Methoden einfuegen ergänzen, zum Einfügen eines Knotens
• die Methode auflisten ergänzen, welche die Knoten der Reihe nach listet
• die Methode entfernen erstellen, zum Löschen eines Knoten

Einer Funktion wird der Inhalt für den Knoten übergeben und die Funktion liefert ein Knotenobjekt mit dem erwünschten naechster (Inhalt) und einem leeren Zeiger naechster zurück.

function erstelleKnoten(farbe) {
  return {
  wert: farbe,
  naechster: null
  };
}

Jedes Mal wenn ein neuer Knoten erwünscht ist, kann nun die Funktion erstelleKnoten() aufgerufen werden:

let neuerKnoten = erstelleKnoten(8);

console.log(neuerKnoten);

// { wert: 8, naechster: null }

Nun schreiben wir die stativLink Klasse mit passendem Konstruktor:

class stativList {
  constructor() {
    this.erster = null;
  }

}

Eine neue Instanz vom Typ stativLink weist nur eine einzige Eigenschaft erster auf, die zu Beginn den Wert null besitzt. Sobald ein erster Knoten eingefügt ist, soll erster auf diesen Knoten der Verketteten Liste zeigen.

Die Methode einfuegen soll einen einzigen Parameter entgegennehmen, den Wert für den Knoten. Die Syntax der Funktion sieht wie folgt aus:

  einfuegen(farbeNr) {
    let neuerKnoten = erstelleKnoten(farbeNr);
    neuerKnoten.naechster = this.erster;
    this.erster = neuerKnoten;
  }

Die Funktion erstellt einen neuen Knoten und weist der Eigenschaft naechster den bisherigen Inhalt des Zeigers erster der Verketteten Liste zu. Anschliessend wird der Zeiger erster auf neuerKnoten gesetzt. Damit ist das Einfügen an erster Stelle der Liste geglückt. Die zentralen Schritte sind in der folgenden Darstellung gezeigt:

Um die in der Verketteten Liste vorhandenen Knoten anzuzeigen, ergänzen wir die Methode auflisten . Diese startet beim ersten Knoten und geht die Liste vom ersten bis zum letzten Element durch. Die while -Schleife hangelt von einem Knoten zu nächsten, bis der Knoten gleich null ist. In der Schleife wird von jedem Knoten sein wert ausgegeben und dem aktuellen Knoten der Knoten aus der Eigenschaft naechster zugewiesen.

  auflisten() {
    let aktueller = this.erster;
    while (aktueller != null) {
      console.log("farbNr: " + aktueller.wert) ;
      aktueller = aktueller.naechster;
    }
    console.log("========");
  }

Nun fügen wir mit einfuegen einige Knoten in die Liste ein und lassen zur Kontrolle an zwei Stellen die Verkettete Liste mit Hilfe der Methode auflisten anzeigen:

const meineListe = new stativList();

meineListe.einfuegen(0);
meineListe.einfuegen(1);
meineListe.auflisten();
meineListe.einfuegen(2);
meineListe.einfuegen(3);
meineListe.einfuegen(4);
meineListe.auflisten();

Zuerst muss die entfernen Methode überprüfen, ob der Zeiger erster nicht auf null zeigt. In diesem Fall wäre die Liste leer und der Versuch einen Knoten zu löschen unsinnig.

Die Schritte um den ersten Knoten zu entfernen sind:

• zuerst wird der erste Knoten mit Hilfe der Eigenschaft erster identifiziert
• der Zeiger erster der Liste muss nun auf den in der Eigenschaft naechster definierten Knoten zeigen.
• Der entfernte Knoten wird zurückgegeben, damit ev. dessen Wert ausgelesen werden kann.

Die beiden zentralen Schritte des Löschens sind in der Darstellung ersichtlich:

Hier der Code der Methode entferne:

  entferne() {
    if (this.erster != null) {
      let ersterKnoten = this.erster;
      this.erster = ersterKnoten.naechster;
      return ersterKnoten;
    }
  }

Nun können Knoten entfernt und die Wirkung in der Konsole mit Hilfe der Methode auflisten überprüft werden:

  meineListe.entferne();
  meineListe.entferne();
  meineListe.auflisten();

Um die Liste grafisch auf dem Canvas darzustellen, soll der Code mit der p5js-Systemfunktion setup erweitert werden. Dabei gilt es folgende Punkte zu beachten:

• Die Funktion erstelleKnoten und die Klasse stativList sind global zu definieren.
• Das Objekt meineListe ist ebenfalls ausserhalb der Systemfunktion als Konstante zu deklarieren.
• Innerhalb von setup ist ein Canvas von 200 px mal 800 px zu kreieren.
• Die Knoten müssen innerhalb von setup der Liste zugefügt werden.

Die ergänzte setup -Funktion präsentiert sich wie folgt:

  // Instanz der Klasse stativList erstellen
const meineListe = new stativList();

function setup() {
  createCanvas(200, 800);
  textAlign(CENTER);
  textSize(44);
  background(240);
  colorMode(HSB, 12, 100, 100);
  
  // ...
  
}

Dabei verweisen die Auslassungszeichen auf die Befehle zum einfügen, entfernen und auflisten der Knoten hin.

Nun kann der Klasse stativList eine weitere Methode zeichne eingefügt werden. Diese funktioniert der Methode auflisten ähnlich: statt bei jedem Knoten den Wert auszugeben, wird ein circle mit dem Wert entsprechender Farbe ausgegeben. Dies lässt sich z.B. mit colorMode(HSB, 18,100,100) einfach realisieren. Dann entsprechen die Werte den 18 definierten HSB-Farbwerten:

  zeichne() {
    let aktueller = this.erster;
    let aktY = 30;
    while (aktueller != null) {
      fill(aktueller.wert, 100, 100);
      circle(100, aktY, 60);
      aktY = aktY + 60;
      aktueller = aktueller.naechster;
    }
  }

Das Ergebnis der Methode zeichne  präsentiert sich auf dem Canvas wie folgt: