链表（3）：双链表

引入

我们之前学的单向链表有什么缺点呢？ 

缺点：后一个节点无法看到前一个节点的内容

那我们就多设置一个格子prev用来存放前面一个节点的地址，第一个节点的prev存最后一个节点的地址（一般是null）

这样一个无头双向链表就造好啦😊

老规矩，手搓双链表

初始

和单链表一样，我们也是实现IList接口的方法

初始化差不多，可以去看我前面的博客

数据结构：链表（1）_cx努力编程中的博客-CSDN博客

跟前驱没关系的函数我先放进来

    @Override
    public boolean contains(int key) {
        ListNode cur = this.head;
        while(cur != null){
            if(cur.val == key){
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
    @Override
    public int size() {
        int count = 0;
        ListNode cur = this.head;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
    @Override
    public void display() {
        ListNode cur = head;
        while(cur != null){
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
        System.out.println();
    }

插入

头插法

实例化一个node，如果只有一个节点的话就把head和last都放在这个节点的下面

node.next = head;

head.prev = node;

head = node;//把head的位置放到node这里

    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        if(head == null){
            head = node;
            last = node;
        }else{
            node.next = this.head;
            head.prev = node;
            head = node;
        }
    }

尾插法

跟单链表不一样的是，双链表有last，所以时间复杂度是O(1)

    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(head == null){
            head = node;
            last = node;
        }else{
            last.next = node;
            node.prev = head;
            last = node;
        }
    }

指定位置插入

比如我们实例化一个节点，想要将其插入到1和2之间

那么我们就要将cur移动到2的位置（走index步）

这个cur的前驱（节点1）的next就是这个新节点的地址

node.next = cur 

cur.prev.next = node(0x123)

node.prev = cur.prev

cur.prev = node

代码：

    @Override
    public void addIndex(int index, int data) {
        //检查index是否异常
        int len = size();
        if(index < 0 || index > len){
            System.out.println("异常索引"+index);
            return;
        }
        if(index == 0){
            //头插法
            addFirst(data);
            return;
        }
        if(index == len){
            //尾插法
            addLast(data);
            return;
        }
        
        ListNode cur = findIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

 删除

假如删除中间45这个节点，先让cur走到这个节点，再让45前一个节点的地址等于45后一个节点地址，让45后一个节点的前驱等于45前一个节点的地址

但是假如要删除的是13这个节点（头节点），那么cur.prev.next = cur.next这行代码有问题

所以我们这么干，直接把头节点的后一个节点的前驱prev置为null就行了

                if(cur == head){
                    head = head.next;
                    head.prev = null;

假如要删除的是56这个节点（尾节点），那么cur.next.prev = cur.prev这行代码有问题

那我们这么干，直接把尾节点的前一个节点的next置为null就行了

cur.prev.next = cur.next;

last = last.prev;

我们发现尾节点的删除和中间节点删除有一行代码是一样的

cur.prev.next = cur.next;

我们可以把它作为这二者的公用代码

                    cur.prev.next = cur.next;
                    if(cur.next == null){
                        last = last.prev;
                    }else {
                        cur.next.prev = cur.prev;
                    }

其实这段代码还存在问题

当链表只有一个元素的时候，

head = head.next //这行代码一走完表明head此时已经是空的了，下一行代码还说head.prev就根本不存在（注意：head.prev = null是赋值操作，首先你得有head.prev才能进行赋值）

更改代码：

整个remove代码

    @Override
    public void remove(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key){
                if(cur == head){
                    head = head.next;
                    if(head == null){
                        last = null;
                    }else{
                        head.prev = null;
                    }
                }else {
                    cur.prev.next = cur.next;
                    if(cur.next == null){
                        last = last.prev;
                    }else {
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            }else{
                cur = cur.next;
            }
        }
    }

删除指定值的所有相同值的节点

跟上面的代码很像，区别就是删除之后不要return，让cur继续往下走

    @Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while(cur != null){
            if(cur.val == key) {
                if (cur == head) {
                    head = head.next;
                    if (head == null) {
                        last = null;
                    } else {
                        head.prev = null;
                    }
                } else {
                    cur.prev.next = cur.next;
                    if (cur.next == null) {
                        last = last.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

清除链表

暴力方法：

head = null;  last = null;

细致方法：

定义一个cur，遍历整个链表，每到一个节点就把prev和next都置为空

    @Override
    public void clear() {
        ListNode cur = head;
        while(cur!=null){
            ListNode curNext = cur.next;//防止将这个节点的next置为空之后，cur没办法继续遍历
            cur.prev = null;
            cur.next = null;
            cur = curNext;
        }
    }

---

总结

ArrayList和LinkedList的区别是？（易考点）

1.如果是经常根据下标查找的（随机访问），使用顺序表（ArrayList）或者数组

ArrayList尾插/删除速度比较快，头插/中间插入/删除比较慢（元素要进行搬运）

2.LinkedList底层是一个链表，不能进行随机访问

进行头插/头删/尾插/尾删操作是O(1)复杂度，进行查找/中间位置插入删除都是O(N)复杂度

相比于ArrayList唯一的优势，就是能快速进行头删（在实现队列的时候比较有用）

3.用LinkedList是否遍历速度更快呢？

不是的，链表访问下一个元素要通过next引用，相比于顺序表的下标++多了依次内存访问的过程

而下标++通常会优化到寄存器中完成