Monday, October 8, 2007

Simple Linked List operations

Some Simple Linked List operations: public class IntList { // Names of simple Containers public int head; public IntList tail; // Constructor function /** List Cell containing (HEAD, TAIL). */ public IntList (int head, IntList tail) { this.head = head; this.tail = tail; } /** List of all items in P incremented by n. */ static IntList incrList (IntList P, int n) { if (P == null) return null; else return new IntList (P.head+n, incrList (P.tail, n)); } /** Iterative version */ static IntList incrListIterative (IntList P, int n) { if (P == null) return null; IntList result, last; result = last = new IntList (P.head+n, null); while (P.tail != null) { P = P.tail; last.tail = new IntList (P.head+n, null); last = last.tail; } return result; } /** List of all items in P incremented by n. May destroy original. */ static IntList dincrList (IntList P, int n) { if (P == null) return null; else { P.head += n; P.tail = dincrList (P.tail, n); return P; } } /** For version */ static IntList forDincrList (IntList L, int n) { // for is more than a loooooooooper. for (IntList p = L; p != null; p = p.tail ) p.head += n; return L; } /** The List resulting from removing all instances of X * from L non-destructively */ static IntList removeAll (IntList L, int x){ if (L == null) return null; else if (L.head == x) return removeAll (L.tail, x); else return new IntList (L.head, removeAll (L.tail, x)); } static IntList removeAllIterative (IntList L, int x) { IntList result, last; result = last = null; for ( ; L != null; L = L.tail){ /* L != null and I is true. */ if (x == L.head) continue; else if (last == null) result = last = new IntList (L.head, null); else last = last.tail = new IntList (L.head, null); } return result; /** Here, I is the Loop Invariant: * Result of all elements of L0 not equal to X up to * and not including L, and last points to the last * elements of result, if any. We use L0 here to mean * "the original value of L." * */ } }

No comments:

Just some daily notes ...

Powered By Blogger