鏈表
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之后的結(jié)點(diǎn)：t = x.next; x.next = t.next;
循環(huán)遍歷：for ( t = head; t != null; t = t.next )
檢查鏈表是否為空：if ( head == null )
空頭結(jié)點(diǎn)，空尾指針
初始化：head = new Node(); head.next = null;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的結(jié)點(diǎn)：t = x.next; x.next = t.next;
循環(huán)遍歷：for ( t = head.next; t != null; t = t.next )
檢查鏈表是否為空：if ( head.next == null )
空頭結(jié)點(diǎn)，空尾結(jié)點(diǎn)
初始化：head = new Node(); z = new Node(); head.next = z; z.next = z;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的結(jié)點(diǎn)：t = x.next; x.next = t.next;
循環(huán)遍歷：for ( t = head.next; t != z; t = t.next )
檢查鏈表是否為空：if ( head.next == z )
循環(huán)鏈表
第一次插入：head.next = head;
在x后插入t：t.next = x.next; x.next = t;
移走x之后的結(jié)點(diǎn)：t = x.next; x.next = t.next;
循環(huán)遍歷：t = head; do { t = t.next; } while ( t != head );
檢查是否只有一個(gè)數(shù)據(jù)項(xiàng)：if ( head.next == head )
堆棧
數(shù)組實(shí)現(xiàn)
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;
}
}
鏈表實(shí)現(xiàn)
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隊(duì)列的鏈表實(shí)現(xiàn)
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;
}
}