ListNode.java
ListNode.java
— 2.8 KB
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); } }