---------------------------------------------------------------------------------------------------------------------------------------------------------
学习Java就上哪吒社区，干货满满，内有每日打卡，Java资料，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、单向链表：结点的删除非常方便，不需要像线性结构那样移动剩下的数据，但是平均的访问效率低于线性表。
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙
????????原创不易，如有错误，欢迎评论区留言指出，感激不尽?
???????????????????????如果觉得内容不错，给个三连不过分吧~ ?????? ?
????????????????????????????????????看到会回访~ ??????????????? ???????????????????? ?
🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙🌙