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." *
*/
}
}
Subscribe to:
Post Comments (Atom)
Just some daily notes ...
Things I'm into now...
Blog Archive
-
▼
2007
(29)
-
▼
October
(15)
- Deconstructing a Scheme recursive function and imp...
- Anasi Boys
- Iterator for Collection and Nested Class
- The Uninvited!
- Inheritence and PolyMorphIsm
- Iterator Example
- Java Library ArrayList
- Inserting into an array non-destructively
- Singly linked list operations...
- PascalTriangles once more!
- Sieve of Erotosthenes
- Linked List Constructor Functionality Testing
- The Linked List Maker method
- Simple Linked List operations
- Old blogs before Day 0.
-
▼
October
(15)
No comments:
Post a Comment