Listen sind verkettete Datenstrukturen, die im Gegensatz zu Feldern dynamisch wachsen können um beliebig viele Elemente (Knoten) zu verwalten. Sie werden anstatt Felder verwendet wenn

• die maximale Größe nicht vorab bekannt ist
• kein wahlfreier Zugriff auf beliebige Listenelemente (bzw. Knoten) benötigt wird.
• die Reihenfolge der Knoten wichtig ist.

Typische Operationen die für Listen zur Verfügung stehen sind:

Mit Hilfe von Listen können auch spezialisiertere Datenstrukturen wie Warteschlangen (engl. queues) oder Stapel (engl. stack) implementiert werden.

Listen in Java

Eine verkettete Datenstruktur kann mit jeder Javaklasse aufgebaut werden die in der Lage ist auf Objekte der gleichen Klasse zu zeigen.

Eine solche Verkettung kann man zum Beispiel mit jeder Klasse implementieren, die die folgende Schnittstelle implementiert:

package s2.listen;
/**
 *
 * @author s@scalingbits.com
 */
public interface EinfacherListenknoten {
    /**
     * Einfuegen eines Nachfolgers
     * @param n einzufuegender Listenknoten
     */
   public void setNachFolger(EinfacherListenknoten n);
   /**
    * Auslesen des Nachfolgers
    * @return der Nachfolger
    */
   public EinfacherListenknoten getNachfolger();
}

Dies geschieht im folge für die Klasse Ganzzahl, die neben der Listeneigenschaft auch in der Lage ist eine Ganzzahl zu verwalten:  

package s2.listen;

/**
*
* @author s@scalingbits.com
*/
public class Ganzzahl implements EinfacherListenknoten {

   public int wert;
   private EinfacherListenknoten naechsterKnoten;

   public Ganzzahl(int i) {
      wert = i;
      naechsterKnoten = null;
   }
   /**
   * Einfuegen eines Nachfolgers
   * @param n einzufuegender Listenknoten
   */
   @Override
   public void setNachFolger(EinfacherListenknoten n) {
      naechsterKnoten = n;
   }
   /**
   * Auslesen des Nachfolgers
   * @return der Nachfolger
   */
   @Override
   public EinfacherListenknoten getNachfolger() {
      return naechsterKnoten;
   }

   /**
   * Hauptprogramm zum Testen
   * @param args
   */
   public static void main(String[] args) {
      Ganzzahl z1 = new Ganzzahl(11);
      Ganzzahl z2 = new Ganzzahl(22);
      Ganzzahl z3 = new Ganzzahl(33);
      z1.setNachFolger(z2);
      z2.setNachFolger(z3);
   }
}

In UML:

Zum Zugriff auf diese Liste reicht jetzt die Referenzvariable z1. Alle anderen Knoten können mit Hilfe der Methode getNachfolger() erreicht werden. Es existiert jedoch kein wahlfreier Zugriff auf die Knoten der Liste.

Werden die beiden Variablen z2 und z3 dereferenziert, können die einzelnen Knoten nach wie vor erreicht werden:

z2 = null;
z3 = null;

Wird die Variable z1 dereferenziert,

 z1 = null;

sind alle drei Objekte nicht mehr erreichbar und können vom Garbagekollektor gelöscht werden.

Unsortierte Listen

Im einfachsten Fall kann eine Liste als einfach verzeigerte Liste implementiert die nur auf den Kopfknoten zeigt.

• Das Einfügen und Löschen am Kopfende hat einen konstanten Aufwand
• Das Suchen bzw. Löschen von Knoten hat einen Aufwand von O(n)
• Relativer Zugriff von einem bekannten Knoten ist nur in Richtung der Nachfolger möglich.

Bei Listen kann man auch das Ende der Liste im Listenobjekt mit pflegen. Einfüge- und Entnahmeoperationen werden hierdurch aufwendiger zu implementieren. Der Vorteil liegt jedoch darin, dass auf das Ende der Liste wahlfrei zugegriffen werden kann.

Vorteile einfach verzeigerter Listen mit Referenz auf das Ende der Liste

• Zugriff auf das und erste und letzte Element der Liste mit konstantem Aufwand
• Iterieren über die Menge aller Listenelemente ist möglich
• Löschen des letzten Elements ist mit konstantem Aufwand möglich (Hierdurch kann eine Warteschlange implementiert werden)

Nachteile

• Kein wahlfreier Zugriff auf alle Elemente
• Man kann nur auf ein Nachbarelement (den Nachfolger) mit konstantem Aufwand zugreifen

Zweiseitig verzeigerte Listen haben den Vorteil, dass sie einen direkten Zugriff auf den Vorgängerknoten sowie auf den Nachfolgerknoten haben:

Vorteile (über die einfach verzeigerte Liste hinaus):

• Iterieren ist in zwei Richtungen möglich
• Der Vorgängerknoten eines Listenknoten kann auch mit konstantem Aufwand errreicht werden