SortedList.java
SortedList.java — 3.8 KB
Dateiinhalt
/** * Implementiert den abtrakten Datentyp sortierte doppelt verkettete Liste */ public class SortedList implements LinkedList { // der erste Knoten und der letzte Knoten der sortierten Liste public ListNode first; public ListNode last; /** * Die sortierte Liste enhält immer mindestens zwei Knoten. * Der first-Knoten wird mit -unendlich und * der last-Knoten mit +unendlich initialisiert. */ public SortedList() { this.first = new ListNode(Integer.MIN_VALUE); this.last = new ListNode(Integer.MAX_VALUE); this.last.prev = first; this.first.next = last; } public void checkInput(int value) throws IllegalArgumentException { if (value == first.value || value == last.value) { throw new IllegalArgumentException( "Die Eingabe reservierter Werte wie '" + value + "' ist nicht erlaubt."); } } @Override public ListNode search(int v) { checkInput(v); return first.search(v); } @Override public ListNode insert(int v) { checkInput(v); return this.first.insert(v); } public void delete(int v) { checkInput(v); this.first.delete(v); } public void print() { this.first.print(); } public boolean checkReferences() { return this.first.checkReferences(); } /** * Testläufe */ public static void main(String[] argv) { SortedList s = new SortedList(); System.out.println("Einfügen mit insertAfter"); ListNode first = s.first; for (int i = 1; i <= 5; i++) { if (first != null) { first = first.insertAfter(i); s.print(); checkAndPrint("Verlinkung ok? ", s.checkReferences()); checkAndPrint("Knoten vorhanden? ", s.search(i) != null && s.search(i).value == i); } } System.out.println("\nDie Ausgabe sollte so aussehen:"); System.out.println("First <--> 1 <--> 2 <--> 3 <--> 4 <--> 5 <--> Last"); System.out.println("\nSuche ausgehend von First (nach Rechts)"); for (int i = 1; i < 4; i++) { ListNode node = s.search(i); System.out.println("Knoten " + i + " gefunden? " + ((node!=null&&node.value == i) ? "Ja" : "Nein")); assert(node != null && node.value == i); } System.out.println("\nSuche ausgehend vom Knoten 4 (nach Links)"); ListNode node = s.search(4); if (node != null && node.value == 4) { for (int i = 1; i < 3; i++) { ListNode leftNode = node.search(i); System.out.println("Knoten " + i + " gefunden? " + ((leftNode!=null&&leftNode.value == i) ? "Ja" : "Nein")); assert(leftNode != null && leftNode.value == i); } } else { System.out.println("Knoten 4 nicht gefunden"); } System.out.println("\nSortiert einfügen (insert)"); for (int i = 10; i >= 6; i--) { s.insert(i); s.print(); checkAndPrint("Verlinkung ok? ", s.checkReferences()); checkAndPrint("Knoten vorhanden? ", s.search(i) != null && s.search(i).value == i); } System.out.println("\nDie Ausgabe sollte so aussehen:"); System.out.println("First <--> 1 <--> 2 <--> 3 <--> 4 <--> 5 <--> 6 <--> 7 <--> 8 <--> 9 <--> 10 <--> Last"); System.out.println("\nLöschen"); for (int i = 5; i < 10; i++) { boolean vorhanden = s.search(i) != null && s.search(i).value == i; s.delete(i); s.print(); checkAndPrint("Verlinkung ok? ", s.checkReferences()); checkAndPrint("Knoten gelöscht? ", vorhanden && (s.search(i) == null || s.search(i).value != i)); } System.out.println("\nDie Ausgabe sollte so aussehen:"); System.out.println("First <--> 1 <--> 2 <--> 3 <--> 4 <--> 10 <--> Last"); } public static void checkAndPrint(String message, boolean correct) { if (!correct) { System.out.println(message + "NEIN"); } assert(correct); } }