Java数据结构之双向链表

⚡️前言⚡️
本笔记针对无头双向链表的实现来展开，在阅读该笔记时，建议读者结合博主的单链表笔记一起阅读，两者多有相似之处，结合阅读便于理解总结😇

🍉博客主页：🍁如风暖阳🍁

🍉欢迎点赞 👍收藏 ⭐留言评论 📝私信必回哟😁

🍉本文由 【如风暖阳】 原创，首发于 CSDN🙉

🍉博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言

🍉博客中涉及源码及博主日常练习代码均已上传码云(gitee)

双向链表概述

双向链表结构其实与单向链表结构非常相似，只是比单向链表多了prev域用于存储前一个节点的地址，从而实现链表的双向性，见下图

🍓节点类及链表头尾的建立

classNode{publicint data;//一个节点存在三个区域publicNode prev;publicNode next;publicNode(int data){//构造方法用于初始化实例对象this.data= data;}}publicclassMyLinkedList{publicNode head;publicNode tail;publicvoidaddFirst(int data);//1.头插法publicvoidaddLast(int data);//2.尾插法publicvoiddisplay();//3.打印链表publicbooleancontains(int key);//4.查找是否包含关键字key是否在单链表当中publicintsize();//5.求链表长度publicvoidaddIndex(int index,int data);//6.任意位置插入,第一个数据节点为0号下标publicvoidremove(int key);//7.删除第一次出现关键字为key的节点publicvoidremoveAllKey(int key);//8.删除所有值为key的节点publicvoidclear();//9.清空链表}

以下即为双向链表的各接口的实现

🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍐 🍍 🍅 🏀 💡 🔑

🍉1.头插法

💡头插节点有两种情况，第一种情况时空链表第一次插入，第二种为后续插入

💡

publicvoidaddFirst(int data){Node node=newNode(data);//将data的值new为一个节点if(this.head==null){//第一次插入this.head=node;//头尾节点都指向该节点this.tail=node;}else{
            node.next=this.head;//完成连接this.head.prev=node;//改变域值this.head=node;//头节点前移}}

🍉2.尾插法

💡与头插类似，两种情况> 💡

publicvoidaddLast(int data){Node node=newNode(data);if(this.head==null){this.head=node;this.tail=node;}else{this.tail.next=node;//续尾
            node.prev=this.tail;//变值this.tail=node;//移尾}}

🍉3.打印链表

💡遍历链表完成打印

publicvoiddisplay(){Node cur=this.head;while(cur!=null){System.out.print(cur.data+" ");
            cur=cur.next;}System.out.println();}

🍉4.查找是否包含关键字

💡遍历链表，查找是否包含关键字

publicbooleancontains(int key){Node cur=this.head;while(cur!=null){if(cur.data==key)returntrue;
            cur=cur.next;}returnfalse;}

🍉5.求链表长度

💡遍历求和

publicintsize(){int a=0;Node cur=this.head;while(cur!=null){
            a++;
            cur=cur.next;}return a;}

🍉6.任意位置（index）插入

💡完成这项任务需要分步进行
1.判断index的合法性
2.是否为头插
3.是否为尾插
4.中间插入

💡在单链表删除关键字时，还需要设置前后节点完成连接，因为双向链表中存在上一个节点的地址，所以只需要设置一个节点遍历即可完成任务

privatevoidcheckIndex(int index){//判断index位置合法性if(index<0||index>this.size()){thrownewRuntimeException("index位置不合法");}}privateNodesearchIndex(int index){//查找插入的位置Node cur=this.head;int a=0;while(a!=index){
            a++;
            cur=cur.next;}return cur;}publicvoidaddIndex(int index,int data){checkIndex(index);if(index==0){//头插this.addFirst(data);return;}if(index==this.size()){//尾插this.addLast(data);return;}Node node=newNode(data);//实例化node节点Node cur=searchIndex(index);//cur存储index位置节点
        node.next=cur;//左边四步完成连接过程，先对node中的值改变对原链表无影响
        node.prev=cur.prev;
        cur.prev.next=node;//然后连接前后
        cur.prev=node;}

🍉7.删除第一次出现关键字为key的节点

💡设置cur节点遍历链表，当cur.data==key时，删除该节点（特殊极端情况单独考虑）> 💡

publicvoidremove(int key){Node cur=this.head;while(cur!=null){if(cur.data==key){//如果找到关键字keyif(cur==this.head){//头节点的data为keythis.head=cur.next;//头节点后移完成头节点删除if(this.head!=null)//防止空指针异常this.head.prev=null;}else{//中间找到key
                    cur.prev.next=cur.next;if(cur.next!=null)
                    cur.next.prev=cur.prev;else//如果cur.next==null，尾节点即为所需删除节点this.tail=cur.prev;}break;//完成删除后跳出循环}
            cur=cur.next;//如果没有进if语句中，cur继续往后遍历}}

🍉8.删除所有值为key的节点

💡与7代码相同，只是无需跳出循环，让cur完成遍历，把关键字全部删除即可

publicvoidremove(int key){Node cur=this.head;while(cur!=null){if(cur.data==key){//如果找到关键字keyif(cur==this.head){//头节点的data为keythis.head=cur.next;//头节点后移完成头节点删除if(this.head!=null)//防止空指针异常this.head.prev=null;}else{//中间找到key
                    cur.prev.next=cur.next;if(cur.next!=null)
                    cur.next.prev=cur.prev;else//如果cur.next==null，尾节点即为所需删除节点this.tail=cur.prev;}}
            cur=cur.next;//如果没有进if语句中，cur继续往后遍历}}

🍉9.清空链表

💡在单链表清空链表时，直接将this.head置为空即可（当this.head置为空时，没有对象引用头节点，则其内存被JVM自动收回，后续节点也被收会），而当双向链表清空时，只把this.head置为空时，因为为双向链表，所以第二个节点的prev仍然指向头节点，所以无法完成清空，则需遍历链表完成置空.

publicvoidclear(){//完成遍历，所有都置为空，则内存被收回while(this.head!=null){Node cur=this.head.next;this.head.prev=null;this.head.next=null;this.head=cur;}this.tail=null;}