链表的游标实现 (Java)
链表的游标实现不太好懂,但是我们可以将其看成两个链表,详解如下:
假设我们有一个大小为10的数组用来存储数据
在运行程序后,链表如下图所示,每一个蓝色方格表示一个节点,里面是“存储元素(角标)”,最后一个节点指向第一个节点0,初始化的节点中元素全为null,这是由代码中最底部static包裹的代码块完成的
初始化链表对象后(CursorList list = new CursorList()),链表如下图所示,绿色虚线为原来的链,红色实线为现在的链,可以看出来,通过alloc()从节点中取出了一个节点(1)作为header(alloc()方法就是取出0之后的第一个节点),其实header存储的数据还是null,但是这里为了方便表示,就写成header,实际上header就是存储数据的链表的头结点(继续看下去就知道了),除此之外,header还指向了0,这就是isEmpty()方法的原理所在
insert()方法
如果我们要在头结点(header)之后插入一个元素”a”,则需要调用insert(“a”,list.zeroth()),具体过程为——先调用alloc()方法获取一个空的节点,把”a”放入这个节点,然后把这个节点插入header之后(因为list.zeroth()返回的是header节点),结合下图很好理解:
remove()方法
假设我们已经有一个插入好的队列header→a→c→g→t→f,我们要删除g,则需要调用remove(“g”),具体过程为——先找到含有元素”g”的节点,然后将该节点从存储元素的链表中剔除,再将该节点清空,放回空节点链表(放在0之后),结合下图很容易理解:
这张图表示一个我们假设已经排序好的链表header→a→c→g→t→f,我们可以看出来,所谓两个链表,一个储存数据,一个存储空节点,只是方便我们理解,事实上,还是只有一个链表滴,存储数据的那部分最终指向0,也就是说,如果当前节点的next为0,就说明存储数据或存放空节点的那部分结束了(别忽略了,空节点那部分最终也是指向0),就像前面说的,isEmpty()方法就是利用了这一点,同样alloc()方法中也判断了是否还有空节点用以存储数据
下面两张图不再细说,还是很直观的
最后一张图是删除之后的链表
总结
诸如BASIC和FORTRAN等许多语言都不支持动态链接结构,那些使用动态链接结构的语言像C和C++偶尔重复调用new的代价是昂贵的。——《数据结构与算法分析——Java语言描述》
个人感觉游标在操作起来和普通链表并无太大不同,实际上两者的实现代码(特别是链表中函数的实现)差别不大,游标实现的链表效率会高一些,因为他是通过数组存储数据的,但是它并不能像普通链表一样实现动态增长缩减,一旦定义了数组大小,则能存储的数据的个数便不可更改了,所以更适合事先知道最大数据个数的案例
代码实现(Java)
//链表的游标实现
public class CursorListTest{
public static void main(String[] args){
CursorList l = new CursorList();
l.insert("a",l.zeroth());
l.insert("b",l.zeroth());
l.insert("c",l.find("b"));
for(int i = 0;i < 10;i++){
System.out.print(l.cursorSpace[i].element + " ");
}
System.out.println();
int p = l.find("b").current;
while(l.cursorSpace[p].element != null){
System.out.println(l.cursorSpace[p].element);
p = l.cursorSpace[p].next;
System.out.println("p--->" + p);
}
System.out.println(l.findPrevious("c").retrieve());
}
}
//节点类
//element表示存储的元素
//next表示下一个节点的序号,即下个节点在数组中的角标
class CursorNode{
CursorNode(Object theElement){
this(theElement,0);
}
CursorNode(Object theElement,int n){
element = theElement;
next = n;
}
Object element;
int next;
}
//节点迭代类,用于扫描节点,该节点有三个方法
//isPastEnd()表示是否已经扫描完了最后一个节点(链表的游标实现中最后一个元素会指向0)
//retrieve()用于获取当前扫描节点的元素
//advance()用于扫描下一个节点
class CursorListItr{
CursorListItr(int theNode){
current = theNode;
}
public boolean isPastEnd(){
return current == 0;
}
public Object retrieve(){
return isPastEnd()?null:CursorList.cursorSpace[current].element;
}
public void advance(){
if(!isPastEnd()){
current = CursorList.cursorSpace[current].next;
}
}
int current;
}
//链表类
//alloc()方法用于分配出去一个当前空闲的数组单元(节点)
//free()方法用于回收一个不再使用的数组单元(节点)
class CursorList{
private static int alloc(){
int p = cursorSpace[0].next;
cursorSpace[0].next = cursorSpace[p].next;
if(p == 0){
throw new OutOfMemoryError();
}
return p;
}
private static void free(int p){
cursorSpace[p].element = null;
cursorSpace[p].next = cursorSpace[0].next;
cursorSpace[0].next = p;
}
public CursorList(){
header = alloc();
cursorSpace[header].next = 0;
}
public boolean isEmpty(){
return cursorSpace[header].next == 0;
}
public void makeEmpty(){
while(!isEmpty()){
remove(first().retrieve());
}
}
public CursorListItr zeroth(){
return new CursorListItr(header);
}
public CursorListItr first(){
return new CursorListItr(cursorSpace[header].next);
}
public CursorListItr find(Object x){
int itr = cursorSpace[header].next;
while(itr != 0 && !cursorSpace[itr].element.equals(x)){
itr = cursorSpace[itr].next;
}
return new CursorListItr(itr);
}
public void insert(Object x,CursorListItr p){
if(p != null && p.current != 0){
int pos = p.current;
int temp = alloc();
cursorSpace[temp].element = x;
cursorSpace[temp].next = cursorSpace[pos].next;
cursorSpace[pos].next = temp;
}
}
public void remove(Object x){
CursorListItr p = findPrevious(x);
int pos = p.current;
if(cursorSpace[pos].next != 0){
int temp = cursorSpace[pos].next;
cursorSpace[pos].next = cursorSpace[temp].next;
free(temp);
}
}
public CursorListItr findPrevious(Object x){
int itr = header;
while(cursorSpace[itr].next != 0 && !cursorSpace[cursorSpace[itr].next].element.equals(x)){
itr = cursorSpace[itr].next;
}
return new CursorListItr(itr);
}
private int header;
static CursorNode[] cursorSpace;
private static final int SPACE_SIZE = 100;
static{
cursorSpace = new CursorNode[SPACE_SIZE];
for(int i = 0;i < SPACE_SIZE;i++){
cursorSpace[i] = new CursorNode(null,i + 1);
}
cursorSpace[SPACE_SIZE - 1].next = 0;
}
}
最后吐槽一点,没有图片作参考,游标实现的链表对于我这种智商捉急的人来说真的很难理解……………………找了一个小时的资料才大概懂了一点(基数排序折磨了我两天我会乱说!直到我遇到了一个高大上的flash!)