Question

前言

今儿是大年初二，没事继续复习数据结构与算法。复习完双向链表下面就开始栈与队列的复习了。搞完这篇先去北京路溜达溜达。晚上在继续 PMP 和数据结构预算的学习

什么是双向循环链表

• 在单链袤的每个结点中，再设置一个指向其前驱结点的指针 域 。所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接 前驱。

双向循环链表的生活情境

• 比出 ,你是一业务员，家在上海。儒要经常出差，行程就是上海到北京一路上的 城市，找客户谈生意或分公司办理业务。你从上海出发，乘火车路经多个城市停留 后，再乘飞机返回上海，以后，每隔一段时间，你基本还要按照这样的行程开展业务

• 你平时都是从上海一路停留到北京的，可是这一次，你得先到北京开会，谁叫北京是首都呢，会就是多。开完会后，你需要例行公事，走访各个城市，此时 你怎么办?。有人又出主意了，你可以先飞回上海，一路再乘火车走遍这儿个城市，到了北京后，你在飞回上海。你会感慨，人生中为什么总会有这样出馒主意的人 存在呢?真要气死人才行。哪来这么麻烦，我一路从北京坐火车或汽车回去不就完了吗。
• 对呀，其实生活中类似的小智慧比比皆是，并不会那么的死板教条。我们的单链表，总是从头到尾找结点，难道就不可以正反遍历都可以吗?当然可以，只不过需要加点东西而已。

循环链袭和双向链表的主要差异

• 双向链表和单向的循环链表操作节本相同，只是在添加和删除操作时多 了一个改变前指针的操作

• 我们在单链表中，有了 next 指针，这就使得我们要查找下一结点的时同复杂度为 0(1)。可是如果我们要查找的是上一结点的话，那最坏的时间复杂度就是 O(n) 了，因为我们每次都要从头开始遍历查找。双向链表就可以解决此类问题

代码实现

public class MyLinkedList {
   Node head; // 头指针
    Node current;   // 当前结点对象
    int size;// 结点个数


    // 初始化头结点，让头指针指向头结点。并且让当前结点对象等于头结点。
    public MyLinkedList() {
        this.head = current = new Node(null);
        this.size = 0;// 单向链表，初始长度为零。
        this.head.next = head; //最后一个元素指针域指向头结点
        this.head.prior=head;
    }

    //使用当前结点对象 定位到要操作结点的前一个结点。
    public void index(int index) throws Exception {
        if (index < -1 || index > size - 1) {
            throw new Exception("参数错误！");
        }
        // 说明在头结点之后操作。
        if (index == -1){
            // 第一个数据元素结点的下标是 0，那么头结点的下标自然就是-1
            return;
        }
        current = head.next;
        int temp=0;	 	//临时变量 用户循坏判断当前节点是否到达
        while (current!=head && temp<index){
            //循环找到插入节点的前一个节点
            current=current.next;
            temp++;
        }
    }


    /**
     * 删除思路：
     *
     * 1。定位到当前要删除的下标的对像的前一个节点
     * 2. 通过改变当前删除对象前一个节点的指针域。》指向当前要删除对象的指针域指向的下一个节点。
     * 3. 改变删除结点的下一个结点的前指针，指向删除结点的前一个结点
     * @param index
     * @throws Exception
     */
    public void delete(int index) throws Exception {
        // 判断链表是否为空
        if (isEmpty()) {
            throw new Exception("链表为空，无法删除！");
        }
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index - 1);// 定位到要操作结点的前一个结点对象。
        //改变删除结点的前一个节点的 next 指向为要删除结点的下一个结点
        current.setNext(current.next.next);
        /**
         * 执行 current.setNext(current.next.next) 后删除结点的前结点的 next 就指向了，删除结点的下一个结点了
         * 比如,a,b,c 三个结点 删除 b 的话 此时 a->next 就指向了 c 但是 c 的前指针还是指向 b
         * 所以这个时就改变 c 的前指针指向 a 就完成删除操作了
         */
        current.next.setPrior(current);
        size--;
    }

    /**
     * 获取思路：
     * 		从头节点开始遍历。用临时变量 temp 记录遍历的次数。一直遍历等于 index 就不会再行循坏，直接取出当前下标的节点
     * @param index
     * @return
     * @throws Exception
     */
    public Object get(int index) throws Exception {
        if (index < -1 || index > size - 1) {
            throw new Exception("参数非法！");
        }
        index(index);
        return current.getElement();
    }

    /**
     * 指定位置插入节点
     * @param index
     * @param obj
     * @throws Exception
     */
    public void insert(int index, Object obj) throws Exception {
        if (index < 0 || index > size) {
            throw new Exception("参数错误！");
        }
        index(index-1);//定位到要操作结点的前一个结点对象。
        current.setNext(new Node(obj,current.next));
        current.next.setPrior(current);
        current.next.next.setPrior(current.next);
        size++;

    }

    /**
     * 未指定下标末尾插入
     * @param obj
     * @throws Exception
     */
    public void insert(Object obj) throws Exception {
        /**
         * 1.判断当前节点指向一下节点的指针域是否为空
         * 如果指针域为空 说明是此节点是末尾节点
         * 直接在尾部修改默认节点的指针域执指向新增的节点，并把新增的节点的指针域指向 null
         */
        while (current.next!=null){
            //循环判断当前节点指针域是否有下一个节点
            current=current.next;
        }
        //找到末尾节点后。在末尾插入新的结点
        current.setNext(new Node(obj, current.next));
        //当前末尾节点的下一个节点 也就是新增加的结点的前指针指向当前找到的末尾结点
        current.next.setPrior(current);
        //当前末尾结点 next-next 也就是刚插入的结点的下一个结点前指针指向当前插入的结点
        current.next.next.setPrior(current.next);
        size++;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return this.size;
    }

    public static void main(String[] args) throws  Exception {
        MyLinkedList list=new MyLinkedList();
        list.insert(0,0);
        list.insert(1,111);
        list.insert(2,222);
        System.out.println("删除之前：");
        for (int i = 0; i < list.size; i++) {
            System.out.print(list.get(i) + " ");
        }
        System.out.println();
        list.delete(1);
        System.out.println("删除之后：");
        for (int i = 0; i < list.size; i++) {
            System.out.print(list.get(i) + " ");
        }
    }
}

结点模型

public class Node {
	Object element; //数据域
	Node next;  //后继指针域
	Node prior; //前驱指针域

	//头结点的构造方法
	public Node(Node nextval) {
		this.next = nextval;
	}

	//非头结点的构造方法
	public Node(Object obj, Node nextval) {
		this.element = obj;
		this.next = nextval;
	}

	//获得当前结点的后继结点
	public Node getNext() {
		return this.next;
	}

	//获得当前结点的前驱结点
	public Node getPrior() {
		return this.prior;
	}

	//获得当前的数据域的值
	public Object getElement() {
		return this.element;
	}

	//设置当前结点的后继指针域
	public void setNext(Node nextval) {
		this.next = nextval;
	}

	//设置当前结点的前驱指针域
	public void setPrior(Node priorval) {
		this.prior = priorval;
	}

	//设置当前结点的数据域
	public void setElement(Object obj) {
		this.element = obj;
	}

	public String toString() {
		return this.element.toString();
	}


}