Rekursive Datenstruktur

Implementierung

Mit Node von Singly Linked List

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; }
}

public class RingQueue {
private ListNode nil;
public RingQueue() {
nil = new ListNode(null, null);
nil.setNext(nil);
}
public void add(String v) {
nil.setValue(v);
ListNode newNil = new ListNode(null, nil.next());
nil.setNext(newNil);
nil = newNil();
}
public String poll() {
ListNode n = nil.next();
nil.setNext(n.next());
return n.value();
}
public String peek() { return nil.next().value(); }
public boolean element (String v) {
ListNode n = nil.next();
while (n != nil && !(v == null ? v == n.value() : v.equals(n.value()))) {
n = n.next ();
}
return n != nil;
}
public boolean isEmpty (){ return nil.next() == nil; }
}

Mit Node von Doubly Linked List

public class DLNode {
private String value ;
private DLNode prev, next;
public DLNode(String v) {
value = v;
prev = next = this;
}
private DLNode(String v, DLNode p, DLNode n) {
value = v; prev = p; next = n;
}
public String value() { return value ; }
public DLNode next() { return next; }
public DLNode previous() { return prev; }
public void setValue(String v) { value = v; }
public DLNode add(String v) { //add between this and this.next
return next = next.prev = new DLNode(v, this , next);
}
public DLNode remove() { //removes this, connects next and prev
next.prev = prev;
prev.next = next;
return this;
}
}

public class RingDEQueue {
private DLNode nil;
public RingDEQueue() { nil = new DLNode(null); }
public void addFirst(String v) { nil.add(v); }
public void addLast(String v) {
//nil.value = v
nil.setValue(v);
//adds new node (val = null) between nil and nil.next
//then nil = nil.next
nil = nil.add(null);
}public String pollFirst() {
return nil.next().remove().value();
}
public String pollLast() {
return nil.previous().remove().value();
}public String peekFirst() {
return nil.next().value();
}public String peekLast() {
return nil.previous().value();
}
public boolean isEmpty(){
return nil.next() == nil;
}
}

Zeichnungen zeigen