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