Kleines Nachschlagewerk Informatik
SDT Verkettung (Liste)
Worum geht es?
Arrays sind einfach und schnell in Bezug auf den Zugriff. Allerdings sind sie in ihrer Größe fest. Um diesen Missstand zu beheben, kann man auf die Verkettung zurückgreifen.

Für Verkettung wird oft der Begriff Liste verwendet, der auch als ADT bekannt ist.
Einfache Verkettung
Bei einer Verkettung gibt es einen Anfang (Listenheader, hierzu reicht eine Referenz auf den ersten Eintrag) und Objekte, die sich einen Nachfolger merken können.

      public class Node
      {
          public Node next;
          public int data;
      }
            
Ein simples Objektdiagramm zeigt eine Liste, die 3, 5, 1 und 23 gespeichert hat.



Zugriff auf n-tes Element
Möchte man das n-te Element haben, muss man (n-1)-Mal den Nachfolger erfragen. Vorher sollte man testen, ob es diesen überhaupt gibt.

      hilfsNode = anfang
      solange n > 0
          hilfsNode = hilfsNode.next
          n = n-1
      gib hilfsnode zurueck
            
Suchen
Sucht man einen Inhalt, so muss man sich von Anfang bis Ende durch die Liste hangeln und enden. Findet man den Eintrag, verlässt man die Schleife und gibt die Nummer zurück.

      hilfsNode = anfang
      n = 0
      wenn hilfsnode = null
          Rückgabe -1
      gefunden = false
      solange hilfsNode != null
          wenn hilfsNode.data = wert
              Rückgabe n
          hilfsNode = hilfsNode.next
      Rückgabe -1
            




Einfügen
Möchte man an einer Stelle etwas einfügen, muss man sich bis zum Vorgänger hangeln, den Nachfolger merken, beim Vorgänger die neue Node als Nachfolger eintragen und bei der neuen Node den bisherigen Nachfolger eintragen. Vorher empfiehlt sich immer noch ein Test, ob die Position auch möglich ist.

Position 0 heißt, dass die neue Node am Anfang eingefügt wird.

      neueNode erzeugen
      neueNode.data = wert
    
      wenn position = 0
          neueNode.next = anfang
          anfang = neueNode
      sonst
          vorgaenger = anfang
          solange position > 0
              vorgaenger = vorgaenger.next
              position = position - 1
          neueNode.next = vorgaenger.next
          vorgaenger.next = neueNode
            
Löschen
Beim Löschen muss man eigentlich nur dem Vorgänger den eigenen Nachfolger als neuen Nachfolger übergeben. Wie immer wurde der Test, ob die Aktion möglich ist, weggelassen.

      wenn position = 0
          anfang = anfang.next
      sonst
          hilfsNode = anfang
          solange position > 0
              hilfsNode = hilfsNode.next
              position = position - 1
          hilfsNode.next = hilfsNode.next.next
            
Doppelte Verkettung
In einer Liste muss man sich immer von vorn nach hinten durchhangeln, wenn man etwas sucht. Man kann den Aufwand etwas reduzieren, wenn man eine doppelte Verkettung zulässt, also auch auf den Vorgänger zeigt. So, wie das letzte Element keinen Nachfolger hat, hat das erste keinen Vorgänger.

      public class Node
      {
          public Node next;
          public Node prev;
          public int data;
      }