---------------------------------------------------------------------------------------------------------------------------------------------------------
学习Java就上哪吒社区，干货满满，内有每日打卡，Java资料，Java学习路线，福利多多哦，既能学习又能获得小礼物，岂不美哉？
【哪吒社区】点此进入.
---------------------------------------------------------------------------------------------------------------------------------------------------------

【前言】在《通过Java理解和实现——顺序表和单链表》一文中已经讲完了顺序表和单链表，接下来就是双向链表了，其实和单链表非常相似，需要注意的就是一些小细节

?无头双向链表

?双链表概念及结构

【为什么引入双链表？】
 单链表的结点中只有一个指向其后继的指针，使得单链表要访问某个结点的前驱结点时，只能从头开始遍历，访问后驱结点的复杂度为O(1)，访问前驱结点的复杂度为O(n)。为了克服上述缺点，引入了双链表。
 双链表的结点中有两个指针prev和next，分别指向前驱结点和后继结点。

?无头双向非循环链表接口实现（注释非常详细，我??都能看懂）

先写两个类，一个是链表类（包含有一个【可变的头结点】和【可变尾节点】和【实现各种功能的接口】，因为是无头链表，所以这个头结点和尾节点是可变的），另一个是节点类（成员属性有value和prev（前驱）和next（后驱））

接下来的接口都是写在链表类里的，因为链表是一个对象，我们要实现的就是一个链表对象所有的功能

?打印双链表

打印链表其实和打印顺序表类似，遍历链表就好了，不过要注意一个点，这里需要引入一个局部变量cur来代替头节点去遍历，因为头结点在没添加或者删除节点之前是固定的，不要让头结点变来变去

//打印双链表
   public void display() {
       //和单链表的打印方式是一样的
       ListNode cur = this.head;//利用临时变量cur代替头结点遍历
       while (cur != null){
           System.out.print(cur.val+" ");
           cur = cur.next;//依次往后走
       }
       System.out.println();
   }

?头插法插入

顾名思义，头插法就是从头部插入节点，使新创建的节点成为新的头结点，这里需要额外考虑一个点，就是头结点是否存在（链表是否为空），（注意，不光要设置后驱还要注意前驱，这比单链表多一个前驱节点）

//头插法
   public void addFirst(int data) {
       ListNode node = new ListNode(data);//创建一个新节点，储存要插入的数据
       if (this.head==null){//判断头结点是否为空，头结点空说明链表为空
           //头结点null属于第一次插入，直接将头结点尾节点都指向插入节点即可
           this.head=node;
           this.last=node;
       }else{//如果不是第一次插入
           node.next=this.head;//将原头结点变成新插入节点的后驱，实现头插
           head.prev=node;//再将新插入节点变成原头结点的前驱
           this.head=node;//最后将新插入的节点设置成头结点
       }
   }

?尾插法插入

尾插法和头插法类似，必须先判断链表是否为空（判断头结点是否为null），双链表区别于单链表，不用每次遍历来找尾节点，双链表本身就有一个尾节点last，我们只需要找到这个last，然后将新节点插入即可

//尾插法
   public void addLast(int data){
       ListNode node = new ListNode(data);//创建一个新节点，储存要插入的数据
       if (this.head==null){//判断头结点是否为空，头结点空说明链表为空
           //头结点null属于第一次插入，直接将头结点尾节点都指向插入节点即可
           this.head=node;
           this.last=node;
       }else{//如果不是第一次插入
           this.last.next=node;//将新结点变成原尾节点的后驱，实现尾插
           node.prev=last;//再将原尾节点变成新插入节点的前驱
           this.last=node;//最后将新插入节点设置成尾节点
       }
   }

?查找是否包含关键字key在双链表当中

传入关键字key，依旧是引入局部变量cur遍历链表，哪个节点的value等于key了，说明链表里有这个关键字，返回true，否则返回false，和单链表一模一样

//查找是否包含关键字key是否在单链表当中
   public boolean contains(int key){
       ListNode cur = this.head;//引入局部变量cur遍历链表
       while(cur != null){
           if(cur.val==key){//如果当前节点的val等于关键字
               return true;//返回true
           }
           cur = cur.next;//否则继续往后遍历
       }
       return false;//遍历完成都没有找到key值，返回false
   }

?得到双链表的长度

依旧采取引用局部变量cur来遍历链表，还要多设置一个局部变量size来计数，只要节点不为null，size就+1，最后返回size的值就是链表长度了（其实和单链表也一模一样）

//得到双链表的长度
   public int size() {
       int size=0;//设置一个计数变量用于计数
       ListNode cur = this.head;//利用cur代替头结点遍历链表
       while (cur != null){//遍历链表，节点不为空
           size++;//计数器+1
           cur = cur.next;//往后走一步
       }
       return size;//遍历完链表返回计数器的值，就是链表长度了
   }

?任意位置插入,第一个数据节点为0号下标

插入原理：临时变量cur代替头结点，cur先走到要插入的位置，然后将新节点插到cur和cur前一节点的中间，替代了cur的原位置，实现按位置插入节点

//任意位置插入,第一个数据节点为0号下标
   public void addIndex(int index,int data){
       ListNode node = new ListNode(data);//创建一个新节点储存要插入的数据
       ListNode cur = this.head;//临时变量cur代替头结点遍历链表
       if (index > 0 && index <size()) {//插入位置不是头也不是尾
           for (int i = 0; i < index; i++){//先让cur走到要插入的位置处
               cur = cur.next;
           }
           cur.prev.next=node;//将插入位置前一节点的后驱指向新节点
           node.prev=cur.prev;//将新节点的前驱指向插入位置的前一节点即 cur.prev
           node.next=cur;//将新节点后驱指向当前cur，也就实现了插入，插到cur和cur前一节点的中间，替代了cur的原位置
       }
       if (index ==size()){//插入位置在尾部
           addLast(data);//直接尾插法
       }
       if (index==0){//插入位置在头部
           addFirst(data);//直接头插法
      }
       display();//打印增加后的链表
   }

?删除第一次出现关键字为key的节点

首先判断头结点是否为null（链表是否为空），然后找要删除的节点，要删除的节点有三种情况
①关键字在头节点：将头节点下一个节点设置为新头节点
②关键字在尾巴结点：将尾节点上一个节点设置为新尾节点
③关键字不在头结点：则将key节点的前一个节点的后驱指向key节点的后一个节点，key节点的后一节点的前驱指向key节点前一节点

//删除第一次出现关键字为key的节点
   public void remove(int key){
       ListNode cur = this.head;//设置cur代替头节点遍历链表
       while(cur != null){
           if(cur.val==key){//如果找到了要删除的点，分以下三种情况
               if(cur==head){//在头部
                   head=head.next;//将要删除的节点的下一节点设为新头节点
                   if (head==null) {//如果这个双链表只有一个元素，要检查
                       break;
                   }
                   head.prev=null;//如果不止一个元素，则将头结点的前驱指向置空
                   break;
               }
               if (cur==last){//在尾部
                   last=last.prev;//要删除节点的上一节点设为新尾节点
                   last.next=null;//将新尾节点后驱置空
                   break;
               } >               if (cur.prev!=null && cur.next!=null){//在中间
                   cur.prev.next=cur.next;//将key节点前一节点的后驱指向key节点的后一节点
                   cur.next.prev=cur.prev;//将key节点后一节点的前驱指向key节点的前一节点
                   break;
               }
           }
           cur=cur.next;//如果没找到目标点则往后走一步
       }
       display();//打印删除后的双链表
   }

?删除所有值为key的节点

和上边删除第一次出现的key类似（注释可以看上边删除第一次出现的key），只不过在删除节点过后不要break，让遍历循环继续进行

//删除所有值为key的节点
   public void removeAllKey(int key){
       ListNode cur = this.head;
       while(cur != null){
           if(cur.val==key){
               if(cur==head){//在头部
                   head=head.next;
                   if (head==null) {//只有一个元素，要检查
                       break;
                   }
                   head.prev=null;
               }
               if (cur==last){//在尾部
                   last=last.prev;
                   last.next=null;
               }
               if (cur.prev!=null && cur.next!=null){//在中间
                   cur.prev.next=cur.next;
                   cur.next.prev=cur.prev;
               }
           }
           cur=cur.next;
       }
       display();
   }

?清空链表

暴力清空，直接将头尾结点置空，这样整个链表就无法找到了

//清空链表
   public void clear() {
       head=null;
       last=null;
   }

?单链表和双链表到底有啥区别

一、指代不同
1、双向链表：也叫双链表，是链表的一种，每个数据结点中都有两个指针，分别指向直接后继和直接前驱
2、单向链表：是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始。
二、优点不同
1、双向链表：从双向链表中的任意一个结点开始，都可以很方便地访问前驱结点和后继结点。
2、单向链表：单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小，结点的访问方便，可以通过循环或者递归的方法访问到任意数据。
三、缺点不同
1、双向链表：增加删除节点复杂，需要多分配一个指针存储空间。
2、单向链表：结点的删除非常方便，不需要像线性结构那样移动剩下的数据，但是平均的访问效率低于线性表。

?????????????????????????
       ❤原创不易，如有错误，欢迎评论区留言指出，感激不尽❤
       ❤               如果觉得内容不错，给个三连不过分吧~        ❤
       ❤                            看到会回访~                                      ❤
??????????????????????