(java实现)双向循环链表

什么是双向循环链表

在了解双向循环链表之前，如果对链表还没有一个清晰的概念，建议你看看单链表和单向循环链表，这有利于你更好的理解下面的内容。（废话有点多[逃]

相比单链表，双向循环链表是一个更加复杂的结构。因为双向循环链表的节点不仅包含指向下一个节点的指针(next)，还包含指向前一个节点的指针(prev)。

在双向循环链表中，可见的不只有头指针head，还有尾节点end。这是和单链表的区别。
双向循环链表的头指针head的前一个节点指向end，尾节点end的后一个节点指向head。

基本操作

双向循环链表的基本操作有：增（add)，删(remove)，改(set)，查（find)，插(insert)等。在这里我们只讲解remove，insert和getNode操作，其他实现可看下方源码。

获取节点

由于双向链表有两个可见的节点（head和end），因此双向循环链表获取节点的操作和单链表有所不同。

把需要获取的节点序号和链表长度/2比较
若小于，说明节点是偏前的，因此从head开始一路next下去
若大于，说明节点是偏后的，因此从end开始一路prev上去
这样的设计能使getNode操作的时间复杂度缩短为O(logN)

删除元素

获取待删除元素的节点node
把node前一个节点的next指针设置为node的后一个节点。具体实现为：node.prev.next=node.next
把node后一个节点的prev指针设置为node的前一个节点。具体实现为：node.next.prev=node.prev
由于没有指针指向node,node会被自动清理
记录链表长度的变量-1

插入元素

获取待插入元素的节点node
创建一个节点mynode，next指向node，prev指向node.prev
把node.prev该节点的next指向mynode
把node的前一个节点prev指向mynode

双向循环链表的优劣

优势

相比单链表，双向循环链表所有基本操作均快于单链表(java源码的LinkList类就是双向循环链表)
能直接获取节点的前一个节点，十分灵活

劣势

相比单链表，双链表的空间内存明显要大很多

双链表的设计应用了算法设计的“空间换时间”思想，通过消耗更多的空间来缩小操作的时间复杂度。

源码实现

public class Node<Anytype> {

    public Anytype data;//数据

    public Node<Anytype> prev;//前一个节点

    public Node<Anytype> next;//后一个节点

    public Node(Anytype data,Node<Anytype> prev,Node<Anytype> next){

        this.data=data;

        this.prev=prev;

        this.next=next;

    }

}

----------------------------------------------

public class DoubleLink<AnyType> {

    Node<AnyType> head;//头指针

    Node<AnyType> end;//尾节点

    int size;//记录链表长度

    //初始化链表

    public void initlist(){

        end=new Node<>(null,null,null);

        head=new Node<>(null,null,end);

        end.prev=head;

        end.next=head;

        size=0;

    }

    //获取长度

    public int length(){

        return size;

    }

    //获取节点

    public Node<AnyType> getNode(int index){

        Node<AnyType> n;

        if(index>=size/2){

            n=end;

            for(int i=length();i>index;i--){

                n=n.prev;

            }

            return n;

        }

        else{

            n=head;

            for(int i=0;i<=index;i++){

                n=n.next;

            }

            return n;

        }

    }

    //添加元素

    public void add(AnyType a){

        Node<AnyType> renode=new Node<>(a,getNode(size-1),end);

        renode.prev.next=renode;

        renode.next.prev=renode;

        size++;

    }

    //插入元素

    public void insert(int i,AnyType a){

        Node<AnyType> n=getNode(i);

        Node<AnyType> renode=new Node<>(a,n.prev,n);

        n.prev.next=renode;

        n.prev=renode;

        size++;

    }

    //删除元素

    public AnyType remove(int i){

        Node<AnyType> n=getNode(i);

        AnyType data=n.data;

        n.prev.next=n.next;

        n.next.prev=n.prev;

        size--;

        return data;

    }

    //获取i位置的数据

    public AnyType get(int i){

        return getNode(i).data;

    }

    //为i位置元素重新赋值

    public AnyType set(int i,AnyType a){

        Node<AnyType> n=getNode(i);

        AnyType old=n.data;

        n.data=a;

        return old;

    }

    //清空链表

    public void clear(){

        initlist();

    }

    public void print(){

        for(int i=0;i<size;i++){

            System.out.println(getNode(i).data);

        }

    }

}

巴特西

(java实现)双向循环链表

什么是双向循环链表

基本操作

获取节点

删除元素

插入元素

双向循环链表的优劣

优势

劣势

源码实现

最新文章

热门文章