链表
class Node {
Object item; Node next;
Node (Object v) {
item = v; next = null;
}
}
头指针，空尾指针
初始化：head = null;
在x后插入t：
if ( x == null)
{ head = t; head.next = null; }
else { t.next = x.next; x.next = t; }
移走x之后的结点：t = x.next; x.next = t.next;
循环遍历：for ( t = head; t != null; t = t.next )
检查链表是否为空：if ( head == null )
空头结点，空尾指针
初始化：head = new Node(); head.next = null;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的结点：t = x.next; x.next = t.next;
循环遍历：for ( t = head.next; t != null; t = t.next )
检查链表是否为空：if ( head.next == null )
空头结点，空尾结点
初始化：head = new Node(); z = new Node(); head.next = z; z.next = z;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的结点：t = x.next; x.next = t.next;
循环遍历：for ( t = head.next; t != z; t = t.next )
检查链表是否为空：if ( head.next == z )
循环链表
第一次插入：head.next = head;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的结点：t = x.next; x.next = t.next;
循环遍历：t = head; do { t = t.next; } while ( t != head );
检查是否只有一个数据项：if ( head.next == head )
堆栈
数组实现
class Stack {
private Object[] s;
private int n;
Stack ( int maxN ) {
s = new Object[maxN]; n = 0;
}
boolean isEmpty() { return ( n == 0 ); }
void push ( Object item ) { s[n++] = item; }
Object pop() {
Object t = s[--n]; s[n] = null; return t;
}
}
链表实现
class Stack {
private Node head;
private class Node {
Object item; Node next;
Node ( Object item, Node next ) {
this.item = item; this.next = next;
}
}
Stack ( Object maxN ) { head = null; }
boolean isEmpty() { return ( head ==null ); }
void push ( Object item ) { head = new Node(item, head); }
Object pop() {
Object v = head.item;
Node t = head.next;
head = t;
return v;
}
}
FIFO队列的链表实现
class Queue {
private class Node {
Object item; Node next;
Node ( Object item ) {
this.item = item; this.next = null;
}
}
Private Node head, tail;
Queue ( Object max ) { head = null; tail = null; }
boolean isEmpty() { return ( head ==null ); }
void put ( Object item ) {
Node t = tail;
tail = new Node(item);
if ( empty() )
head = tail;
else t.next = tail
}
Object get() {
Object v = head.item;
Node t = head.next;
head = t;
return v;
}
}