1.双向链表

 2.模拟实现双向链表

(一).构造节点类

首先我们要明白，双向链表的每一个节点都包含一个数据域和两个指针域，一个指针域为前指针域，表示指向当前节点的前一个节点，一个指针域为后指针域，表示指向当前节点的后一个节点，所以每一个节点都是一个完整的对象，所以我们可以通过定义一个内部类

static class ListNode{
        public int val;
        public ListNode prev;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }

(二).明确要写的功能

要写的功能基本和单链表一样，所以我依旧是将他们放到了一个接口中，然后重写这些方法

(三).创建头节点和尾节点

    public ListNode head;
    public ListNode tail;

我们需要创建一个头节点来指向我们的第一个节点，同时创建一个尾节点来指向我的双向链表的尾节点

(四).头插法

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

            head.prev=node;
            head=node;
        }
    }

首先我们要先创造一个节点

然后判断head是否为空，如果head为null，说明整个链表就是空的，也就是说该节点是整个链表的第一个节点，此时该节点既是头节点，也是尾节点

如果head不为空

那就让要插入的节点的next指向头节点，同时将头节点的前驱设置为node，最后将node节点设置为新的头节点

(五).尾插法

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

首先我们先判断链表是否为空，即head是否为空

当链表为不空的时候，我们直接让tail指向的节点的后驱next指向node，同时将node的前驱prev指向tail，最后将新插入的节点node置为新的尾

(六).任意位置插入,第一个数据节点为0号下标

@Override
    public void addIndex(int index, int data) {
        //首先判断index的合法性
        try {
            ListNode node=new ListNode(data);
            if_index(index);
            if (index==0){
                addFirst(data);
                return;
            }
            if (index==size()){
                addLast(data);
                return;
            }
            ListNode cur=head;
            while (index-->0){
                //找到要插入位置的后一个节点
                cur=cur.next;
            }
            //将要插入的节点的后驱改为cur
            node.next=cur;
            //将要插入的节点的前驱改为cur的前驱
            node.prev=cur.prev;
            //将原本cur的前一个节点的后驱改为node
            cur.prev.next=node;
            //将cur的前驱改为node
            cur.prev=node;
        }catch (indexException e){
            e.printStackTrace();
        }
    }

private void if_index(int index)throws indexException{
        if (index<0||index>size()){
            throw new indexException("index下标异常");
        }
    }

首先我们先判断index的合法性，同样我们可以用异常来解决这个问题

如果不合法则直接抛出异常

如果合法，则我们需要找到要插入数据位置的后一个节点

然后我们让cur.prev.next指向node

我们要明白，cur.prev表示cur的前一个节点，让前一个节点的next指向node

同时让node的前驱指向cur的前一个节点，即node.prev=cur.prev

让node的后驱指向cur，即node.next=cur.next

让cur的前驱指向node，即cur.prev=node

上图就是经过我们插入之后的链表

(七).查找是否包含关键字key是否在双链表当中

@Override
    public boolean contains(int key) {
        ListNode cur=head;
        while(cur!=null){
            if(cur.val==key){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }

这个方法相对于来说比较简单，我们只需要遍历这个双向链表即可，一旦值一样，则返回ture，但当链表循环完之后，没有找到与key相等的值，则返回false

(八).删除第一次出现关键字为key的节点

@Override
    public void remove(int key) {
        ListNode cur=head;
        while(cur!=null){
            if (cur.val==key){
                //判断头节点的val值是否和key相同
                if (cur==head){
                    //head走向下一个节点
                    head=head.next;
                    //如果head不为null，那么说明这个链表不止1个头节点
                    //如果head为null，那么此时说明这个链表就1个头节点，那么如果执行head.prev=null就会报空指针异常
                    if (head!=null){
                        head.prev=null;
                    }
                }else{
                    //将要删除的节点的前一个节点的前驱改为要删除节点的后驱
                    cur.prev.next=cur.next;
                    //判断cur节点是否是尾节点
                    if (cur.next!=null){
                        cur.next.prev=cur.prev;
                    }else{
                        //如果是尾节点，则需要tail节点往前挪一个位置
                        tail=tail.prev;
                    }
                }
                return;
            }
            cur=cur.next;
        }
        if (cur==null){
            System.out.println("没有你要删除的数据");
            return;
        }
    }

首先如果我们找到了要删除的节点

判断是否为头节点

我们要先进行判断，判断是不是头节点，如果是头节点，那么我们让头节点指向头节点的下一个节点

同时我们要将新的头节点的前驱置为空

但是当链表只有一个头节点的时候，我们会发现问题

此时head已经空了，当我们再执行head.prev=null时，就会报出空指针异常，此时程序就会报错

所以我们在判断cur是否是头节点的时候，我们要再加一层判断

既然已经执行了head=head.next了，那么head已经指向了下一个节点，所以我们只需要判断

此时的head是否为空即可，如果不为空执行head.prev=null

判断其他节点

如果不是头节点，那么剩下的节点我们就可以平常处理了

我们可以看上面的图，我们可以看到，假设我要删除cur这个节点，我应该如何做？

1.让cur前一个节点的后驱指向cur的下一个节点

首先，我先要找到cur的前一个节点，即cur.prev，再找到他的后驱，即cur.prev.next，

此时我们已经找到了cur的前一个节点的后驱，然后我们再找到cur的下一个节点、即cur.next

然后我们将cur前一个节点的后驱指向cur的下一个节点

即cur.prev.next=cur.next

2.让cur的下一个节点的前驱指向cur的前一个节点

首先，先要找到cur的下一个节点，即cur.next，然后找到他的前驱，即cur.next.prev

再找到cur的前一个节点，即cur.prev，让后一个节点的前驱指向cur的前一个节点

即cur.next.prev=cur.prev

这样我们将该节点删除了

但是还有一种情况，如果要删除的节点是尾节点我们这样写代码还可以吗？

不可以

为什么？

因为当cur是尾节点的时候我们确实可以执行cur.prev.next=cur.next，但是cur.next.prev=cur.prev还是否可行？

答案肯定是不行的，因为想一想，cur已经是尾节点了，我执行cur.next.prev，就会报空指针异常，因为cur.next已经是空了，空的前驱肯定是会报错的

所以我们在进行删除其他节点的时候，我们要进行判断，判断是否是尾节点，如果不是尾节点，我们可以正常删除，如果是尾节点，则我们可以直接对tail进行处理

直接让tail=tail.prev即可，让链表的尾指向链表的前一个节点

(九).删除所有值为key的节点

@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){

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

这个方法和上一个第八个方法类似，第八个方法我们只是删除了一个等于key的节点，然后我们就return返回了

这个是将所有等于key的节点都删除，所以我们只需要将第八个代码中的return删掉即可

(十).计算链表的长度

@Override
    public int size() {
        ListNode cur=head;
        int count=0;
        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();
    }

同样也是遍历链表，然后打印每个节点的val值即可

(十二).清除链表

@Override
    public void clear() {
        ListNode cur=head;
        while(cur!=null){
            ListNode curNext=cur.next;
            cur.next=null;
            cur.prev=null;
            cur=curNext;
        }
        head=null;
        tail=null;
    }

清空链表，我们需要把每个节点的next域和prev域都置为null

在清空的同时，我们要记录cur的下一个节点，这样链表才能遍历起来

最后我们要将head和tail也置为空

3.链表的打印

 public static void main(String[] args) {
        LinkedList<Integer> list=new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        System.out.println("========直接打印============");
        System.out.println(list);
        System.out.println("=======for循环打印=========");
        for (int i = 0; i < list.size(); i++) {
            System.out.print(list.get(i)+" ");
        }
        System.out.println();
        System.out.println("======for-each打印=========");
        for (Integer x:list) {
            System.out.print(x+" ");
        }
        System.out.println();
        System.out.println("=======迭代器Iterator打印========");
        //先判断是否有下一个，如果有则打印下一个，并往下走一步
        Iterator<Integer> iterator=list.iterator();
        while(iterator.hasNext()){
            System.out.print(iterator.next()+" ");
        }
        System.out.println();
        System.out.println("=====迭代器ListIterator打印=======");
        ListIterator<Integer> listIterator=list.listIterator();
        while (listIterator.hasNext()){
            System.out.print(listIterator.next()+" ");
        }
        System.out.println();
        System.out.println("===迭代器ListIterator倒序打印======");
        ListIterator<Integer> listIterator1=list.listIterator(list.size());
        while (listIterator1.hasPrevious()){
            System.out.print(listIterator1.previous()+" ");
        }
    }

4.ArrayList和LinkedList的区别

ArrayList底层是一个数组，所以在存储空间上，他们是连续的

LinkedList是由一个一个的节点组成，他们通过地址进行连接，所以他们是在逻辑上是连续的，在物理上不连续

当ArrayList想要随机访问数据时，我们可以直接通过下标进行访问，所以时间复杂度是O(1)

当LinkedList想要随机访问数据时，需要从头开始遍历，所以时间复杂度是O(N)

当要插入数据时，ArrayList需要移动数据，效率很低

LinkedList只需要修改引用的指向即可，时间复杂度是O(1)

同时LinkedList不需要进行扩容，而ArrayList需要进行扩容