Humboldt-Universität zu Berlin - Mathematisch-Naturwissenschaftliche Fakultät - Wissensmanagement in der Bioinformatik

Dateiinhalt

/**
 * Ein Knoten für eine doppelt verkettete Liste
 */
public class ListNode implements LinkedList {
  public int value;
  
  // Zeiger auf den Nachfolger und Vorgänger
  public ListNode next;
  public ListNode prev;
  
  // Zeiger auf die obere und untere Ebene 
  // (wird erst für Skiplisten benötigt)
  public ListNode up;
  public ListNode down;
  
  public ListNode(int value) {
    this.value = value;
  }
  
  /** 
   * Liefert den Knoten mit dem gesuchten Wert v, falls vorhanden;
   * andernfalls den Knoten mit dem zu v nächstkleineren Wert. 
   */
  @Override
  public ListNode search(int v) {
    // TODO
    return null;    
  }        
  
  /** 
   * Ein neuer Knoten mit dem Wert v wird hinter dem aktuellen Knoten eingefügt.
   * Dieser neue Knoten wird zurückgegeben.
   */  
  protected ListNode insertAfter(int v) {
    // TODO
    return null;
  }
  
  /** 
   * Falls noch kein Knoten mit dem Wert v in der sortierten Liste enthalten ist, wird ein solcher eingefügt und zurückgeben; 
   * andernfalls wird keine Veränderung an der Liste vorgenommen und der existierende Knoten mit Wert v zurückgegeben.
   */
  @Override  
  public ListNode insert(int v) {
    // TODO 
    return null;    
  }
  
  /** 
   * Der Knoten mit Wert v wird aus der sortierten Liste entfernt. Falls kein Knoten mit Wert v existiert, wird die Liste nicht verändert.   
   */
  public void delete(int v) {
    // TODO
  }
  
  /**
   * Hilfsmethode zum Überprüfen der Referenzen
   */
  public boolean checkReferences() {
    ListNode sorted = this;
    while (sorted.next != null) {
      // überprüfe die Nachfolger- und Vorgänger-Verknüpfungen
      if (sorted.next.prev != sorted) {
        return false;
      }
      // prüfe, ob die Elemente sortiert sind
      if (sorted.value > sorted.next.value) {
        return false;
      }
      sorted = sorted.next;
    }
    return true;
  }
  
  /**
   * Gibt den Inhalt der sortierten Liste aus.
   */
  public void print() {
    ListNode lowest = this;
    while (lowest.down != null) {
      lowest = lowest.down;        
    }
    
    ListNode sorted = this;    
    while (sorted != null) {    
      
      while (lowest.value != sorted.value) {
        lowest = lowest.next;
        System.out.print("------->");
      }      
      
      System.out.print(sorted.toString());
            
      if (sorted.next != null) {
        if (sorted.next.prev != null) {
          System.out.print("<");
        }
        System.out.print("-->");
      }

      sorted = sorted.next;
      lowest = lowest.next;
    }
    System.out.println("");
  }
  
  @Override
  public String toString() {
    if (this.value == Integer.MIN_VALUE) {
      return "First ";
    }
    else if (this.value == Integer.MAX_VALUE) {
      return " Last";
    }
    return String.format("%3d ", value);
  }

}