BubbleSort

Bubble Sort für Singly Linked List

public interface List extends Collection {
int indexOf(String element);
String get(int index);
boolean add(int index, String element);
String set(int index, String element);
String remove(int index);
void sort();
Iterator sortedIterator();
}

public class LinearList implements List {
private ListNode head;public void sort () {
if (head != null) {
boolean modified ;
do {
modified = false;
ListNode m, n = head;
while ((n = (m = n). next ()) != null) {
String x=m. value (), y=n.value ();
if (x != null && (y == null	|| x. compareTo (y) < 0)) {
m. setValue (y);
n. setValue (x);
modified = true;
}
}
} while ( modified );
}
}public Iterator sortedIterator() {
return new SortedListNodeIter(head);
}// zahlreiche weitere Methoden zu implementieren . . .
}

MergeSort

public class LinearList implements List {
private ListNode head;// Alternative Implementierung von sort – siehe Listing 3.34
public void sort() {
if (head != null) {
head = head.mergesort(false);
}
}
}

public class ListNode {
private String value;
private ListNode next;private static boolean cmp(ListNode a, ListNode b) {
return a.value == null || (b.value != null && a.value.compareTo(b.value) < 0);
}public ListNode mergesort(boolean reverse) {
if (next == null) {
return this;
}
ListNode[] xs = new ListNode[2];
ListNode h, n = this;
for (int i = 0; n != null; i = (i + 1) & 1) {
h = n;
n = h.next;
h.next = xs[i];
xs[i] = h;
}
xs[0] = xs[0].mergesort(!reverse);
xs[1] = xs[1].mergesort(!reverse);
while (xs[0] != null) {
int i = (xs[1] == null || cmp(xs[0], xs[1]) == reverse) ? 0 : 1;
h = xs[i];
xs[i] = h.next;
h.next = n;
n = h;
}
while (xs[1] != null) {
h = xs[1];
xs[1] = h.next;
h.next = n;
n = h;
}
return n;
}
}

Sortierender Iterator

Iterator sucht nach dem kleinsten noch nicht bearbeiteten Eintrag

Obwohl in List Einträge durch sort() sortierbar sind, kann die Sortierung durch add (neu einfügen) oder set (bestehenden Eintrag ersetzen) an einem bestimmten Index wieder verletzt werden.

Ein Iterator kann Elemente geordnet zurückgeben.

public class SortedListNodeIter implements Iterator {
private ListNode head, next;public SortedListNodeIter(ListNode head) {
this.head = head;
setNext();
}private static boolean prec(ListNode a, ListNode b, int c) {
String x = a.value(), y = b.value();
if (y == null) {
return x == null && c == 0;
}
return x == null || y.compareTo(x) >= c;
}private void setNext() {
int c = 0;
ListNode n = head, min = null;
while (n != null) {
if (n == next) {
c = 1;
} else if ((next == null || prec(next, n, c)) &&
(min == null || prec(n, min, 0))) {
min = n;
}
n = n.next();
}
next = min;
}public boolean hasNext() {
return next != null;
}public String next() {
if (next == null) {
return null;
}
String result = next.value();
setNext();
return result;
}
}