Rekursive Datenstrukturen

Implementierung

public class ListNode {
private String value;
private ListNode next;
public ListNode (String v, ListNode n) {
value = v;
next = n;
}
//getter
public String value() { return value; }
public ListNode next() { return next; }
//setter
public void setNext (ListNode n) { next = n; }
public void setValue (String v) { value = v; }
}

private static void useListNode() {
ListNode list = null;
for (char c = ’a’; c <= ’z’; c++) {
list = new ListNode ("" + c, list);
}
while (list != null) {
System.out.println(list.value());
list = list.next();
}
}

Stack

public class ListStack {
private ListNode head;
public void push(String v) {
head = new ListNode(v, head);
}
public String pop () {
if (head != null) {
String result = head.value();
head = head.next();
return result;
}
return null;
}
public String peek() {
return head == null ? null : head.value();
}
}

Queue

Ineffiziente Variante → die effiziente Variante funktioniert mit doubly linked list

public class ListQueueSimple {
private ListNode head;public void add(String v) {
if (head == null) {
head = new ListNode (v, null);
} else {
ListNode last = head;
while (last.next () != null) {
last = last.next ();
}
last.setNext(new ListNode (v, null));
}
}public String poll () {
if (head != null) {
String result = head.value();
head = head.next();
return result;
}
return null;
}public String peek () {
return head == null ? null : head.value();
}
}

public class ListQueue {
private ListNode head, last;public void add(String v) {
if (head == null) {
head = last = new ListNode(v, null);
} else {
last.setNext (last = new ListNode(v, null));
}
}public String poll() {
if (head != null) {
String result = head.value();
head = head.next();
if (head == null) { last = null; }
return result ;
}
return null;
}public String peek() {
return head == null ? null : head.value ();
}public int indexOf(String v) {
int i = 0;
ListNode n = head;
while (n != null && !(v == null ? v == n.value() : v.equals(n.value()))) {
i++;
n = n.next();
}
return n == null ? -1 : i;
}
public String valueAt(int i) {
for (ListNode n = head; n != null; n = n.next()) {
if (i-- == 0) { return n.value(); }
}
return null;
}}