Einfache verkettete Liste mit Java

Dieses Buch bei Amazon

Dies ist Lektion (n+1) unserer Reihe "Einfache Datenstrukturen mit Java". Heute geht es um eine einfache verkettete Liste.

Unsere erste Klasse ListElem repräsentiert ein Element oder einen "Knoten" der Liste und bietet einige Methoden zur Manipulation derselben und zur Abfrage des Inhaltes eines Knotens und des nächsten Knotens an: 

/**
 * Diese Klasse repräsentiert einzelnen Knoten
 * der verketteten
 * Liste. Sie bietet primitive Methoden zum
 * Setzen des Datums
 * und des next-Pointers. 
 * @author Helmut Mucker
 * @version 1.0,
 */
public class ListElem {

  /**
   * Das Datum, welches im Knoten gespeichert wird.
   */
  private Integer data;

  /**
   * Ein Zeiger auf den nächsten Listen-Knoten.
   */
  private ListElem next;

  /**
   * Ein Konstruktor ohne Parameter
   */
  public ListElem() {
    next = null;
  }

  public ListElem(Integer d) {
    data = d;
    next = null;
  }

  /**
   * Liefert den Inhalt des Knotens. 
   * @return data
   */
  public Integer getData() {
    return data;
  }

  /**
   * Liefert den Zeiger auf den nächsten Knoten. 
   * @return next
   */
  public ListElem getNext() {
    return next;
  }

  /**
   * Setzt den Inhalt des Knotens. 
   */
  public void setData(Integer d) {
    data = d;
  }

  /**
   * Setzt den Inhalt des Zeigers auf den nächsten
   * Knoten. 
   */
  public void setNext(ListElem n) {
    next = n;
  }

  /**
   * Liefert den Inhalt des Knotens als String. 
   * @return String data
   */
  public String toString() {
    return data.toString();
  }

}
Die Klasse List repräsentiert dann die eigentliche Liste. Zum Probieren hat sie eine "main" Methode: In ihr sieht man beispielhaft, wie die Liste als Datenstruktur zu verwenden ist: 
import java.io.*;

/**
 * Diese Klasse repräsentiert eine
 * verkettete Liste. 
 *
 * @author Helmut Mucker
 * @version 1.0
 */
public class List {

  /**
   * Ein Zeiger auf das erste Element der Liste
   */
  private ListElem first;

  /**
   * Der default Konstruktor
   */
  public List() {
    first = null;
  }

  /**
   * Dieser Konstruktor nimmt eine Zahl
   * als Parameter und erzeugt eine Liste.
   */
  public List(Integer d) {
    first = new ListElem(d);
  }

  /**
   * Dieser Konstruktor nimmt ein ListElem
   * als Parameter und erzeugt eine Liste.
   */
  public List(ListElem e) {
    first = e;
  }

  /**
   * Anhängen eines Elementes an die Liste
   * @return Die aktuelle Liste
   */
  public List append(Integer d) {

    if (first == null) {
      first = new ListElem(d);
    } else {
      ListElem n = new ListElem(d);
      n.setNext(first);
      first = n;
    }

    return this;
  }

  /**
   * Liefert die gesamte Liste konkateniert als String.
   * @return Die aktuelle Liste
   */
  public String toString() {

    String result = "";
    ListElem n = first;

    while (n != null) {

      result = result + " " + n.getData();
      n = n.getNext();
    }

    return result;
  }

  /**
   * Zeigt an, on die Liste leer ist
   * @return true wenn leer, sonst false
   */
  public boolean isEmpty() {
    if (first == null) {
      return true;
    } else {
      return false;
    }
  }

  /**
   * Liefert eine Liste, bestehend aus dem ersten
   * Element.
   * @return Liste oder null wenn leer.
   */
  public List getFirst() {
    if (first != null) {
      List l = new List(first);
      return l;
    } else {
      return null;
    }
  }

  /**
   * Liefert eine Liste, bestehend aus allen
   * Elementen * ausser dem ersten Element.
   * @return Liste oder null wenn leer.
   */
  public List getRest() {
    if (first != null) {
      List l = new List(first.getNext());
      return l;
    } else {
      return null;
    }
  }

  /**
   * Liefert eine Liste, bestehend aus dem
   * letzten Element * der aktuellen Liste
   * @return Liste oder null wenn leer.
   */
  public List getLast() {
    List loop = new List(first);
    List current = new List(first);
    if (loop != null) {
      // not empty
      while (loop.getRest() != null) {
        // next is defined
        current = loop;
        loop = loop.getRest();
      }
    }
    return current;
  }

  public List concat(List l) {

    ListElem glue = new ListElem();
    List last = this.getLast();
    if (last == null) {
      first = l;
    } else {
    }
  }
  
  public static void main(String argv[]) {

    List l = new List(new Integer(2));
    l.append(new Integer(3));
    l.append(new Integer(6));

    System.out.println(l.toString());
    List r = l.getLast();
    System.out.println(r.toString());
  }

}

Alle Touren

Schneebergwege

Raxsteige

Geführte Touren

Perl

Literatur

Musik