Java数据结构之双向链表(配图详解,简单易懂)

2022-10-24 08:36:29

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;}


  • 作者:如风暖阳
  • 原文链接:https://blog.csdn.net/qq_60856948/article/details/122735696
    更新时间:2022-10-24 08:36:29