链表是一个递归的数据结构,它或者为null,或者是指向一个结点的引用,该结点含有一个泛型的元素和指向另一个链表的引用.可以用一个内部类来定义节点的抽象数据类型:
private class Node /*定义节点类*/{
Item item;
Node next;
}
根据递归的定义,我们只需一个Node类型的变量就能表示一条链表,只要保证它的值是null或者指向另一个Node对象,且该对象的next域指向了另一条链表即可.链表表示的是一列元素,虽然也可以用数组来表示一列元素,但是在链表中插入元素或者从序列中删除元素都十分方便.另外,每个修改链表的操作都需要添加检查是否要修改变量的代码.
对于链表元素的遍历,可以采用下列方式:
for(Node x=first;x!=null;x=x.next) {
//处理x.item
}
对于实现队列和堆栈,上面这种迭代方式是实现迭代器的最基本的方式.实现队列和堆栈通过内部维护一个链表,达到了操作所需的时间总是和集合的大小无关.下面是实现的代码:
import java.util.Iterator;
//链表实现的堆栈
public class Stack<Item> implements Iterable<Item>{
private Node first; //定义栈顶
private int N; //定义元素的数量
private class Node {
Item item;
Node next;
} public boolean isEmpty() {
return first==null;
}
public int size() {
return N;
}
public void push(Item item) {
//向栈顶添加元素
Node oldfirst=first;
first=new Node();
first.item=item;
first.next=oldfirst;
N++;
}
public Item pop() {
//从栈顶弹出元素
Item item=first.item;
first=first.next;
N--;
return item;
}
@Override
public Iterator<Item> iterator() {
return new StackIterator();
}
private class StackIterator implements Iterator<Item> { private Node current=first;
@Override
public boolean hasNext() {
return current!=null;
} @Override
public Item next() {
Item item=current.item;
current=current.next;
return item;
}
}
}
//链表实现的队列
import java.util.Iterator;
public class Queue<Item> implements Iterable<Item> {
private Node first; //定义表头
private Node last; //定义表尾
private int N; //定义元素的数量
private class Node /*定义节点类*/{
Item item;
Node next;
}
public boolean isEmpty() {return first==null;}
public int size() {return N;}
public void enquene(Item item) {
//向表尾添加元素
Node oldlast=last;
last=new Node();
last.item=item;
last.next=null;
if(isEmpty()) first=last; //如果添加前,列表为空,此时表头与表尾指向同一元素
else oldlast.next=last; //将之前的尾部元素的下一个元素指向新的尾部元素
N++; //增加元素数目
}
public Item dequeue() {
Item item=first.item;
first=first.next;
if(isEmpty()) last=null; //如果列表成为空,那么将尾部元素设为null
N--; //减少元素数目.
return item;
}
@Override
public Iterator<Item> iterator() {
return new QueueIterator();
}
private class QueueIterator implements Iterator<Item> /*和栈迭代器的实现完全一样*/{ private Node current=first;
@Override
public boolean hasNext() {
return current!=null;
} @Override
public Item next() {
Item item=current.item;
current=current.next;
return item;
}
}
}