链表的游标实现 (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！）