【Java数据结构和算法】006-链表：双向链表

梦里梦外; 2023-10-05 13:02 21阅读 0赞

# **目录** #

0、警醒自己

一、双向链表概述

1、双向链表简介

2、双向链表图解

3、单向链表和双向链表的优缺点及适用场景

单向链表：

双向链表：

二、双链表应用实例

1、双链表属性的内容

举例：

2、添加节点思路分析

图解：

思路分析：

遍历思路分析：

代码演示：

运行结果：

3、删除节点思路分析

图解：

思路分析：

代码实现：

运行结果：

4、插入节点

图解：

思路分析：

代码演示：

运行结果：

--------------------

# 0、警醒自己 #

**1、学习不用心，骗人又骗己；**

**2、学习不刻苦，纸上画老虎；**

**3、学习不惜时，终得人耻笑；**

**4、学习不复习，不如不学习；**

**5、学习不休息，毁眼伤身体；**

**6、狗才等着别人喂，狼都是自己寻找食物；**

# 一、双向链表概述 #

## 1、双向链表简介 ##

在单向链表中，我们能够通过next连接到下一个节点，我们很容易得到下一个节点，但是我们很难得到上一个节点，双向链表就是在单向链表的基础上添加一个pre，连接上一个节点；

## 2、双向链表图解 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70][]

## 3、单向链表和双向链表的优缺点及适用场景 ##

### 单向链表： ###

**描述：**只有一个指向下一个节点的指针；

**优点：**

①单向链表增加删除节点简单；

②单链表不能自我删除，需要靠辅助节点；

**缺点：**只能从头到尾遍历，只能找到后继，无法找到前驱，也就是只能前进；

**适用场景：**适用于节点的增加删除；

### 双向链表： ###

**描述：**有两个指针，一个指向前一个节点，一个后一个节点；

**优点：**

①可以找到前驱和后继，可进可退；

②双链表能自我删除；

**缺点：**增加删除节点复杂，需要多分配一个指针存储空间；

**适用场景：**需要双向查找节点值的情况；

# 二、双链表应用实例 #

## 1、双链表属性的内容 ##

唯一ID + 类原始属性 + 下一个节点+上一个节点；

**（在双向链表中，我们就以实际代码演示中情况写了）**

### 举例： ###

public class HeroNode{
        private int id;
        private String name;
        private String nickname;
        private HeroNode next;
        private HeroNode pre;
    }

## 2、添加节点思路分析 ##

### 图解： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1][]

### 思路分析： ###

第一步：遍历原链表，找到最后一个节点，假设为temp；

第二步：将temp的next连接到新节点；

第三步：将新节点的pre连接到temp；

### 遍历思路分析： ###

双链表的遍历与单链表的遍历思路一摸一样，不再做过多赘述；

### 代码演示： ###

（双链表添加节点的写法与单链表很相似，这里我又对上一篇笔记单链表打印头节点内容的情况随进行了优化！）

### 运行结果： ###

及时雨宋江添加成功！
    豹子头林冲添加成功！
    玉麒麟卢俊义添加成功！
    智多星吴用添加成功！
    1及时雨宋江
    3豹子头林冲
    5玉麒麟卢俊义
    7智多星吴用

## 3、删除节点思路分析 ##

### 图解： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2][]

### 思路分析： ###

第一步：遍历链表，（根据id或者其他条件）找到要删除的节点，假设为temp；

第二步：将temp的“上一个节点的下一个节点”指向temp的下一个节点，将temp的“下一个节点的上一个节点”指向temp的上一个节点即可；

**（注意：在实际的使用中我们需要灵活，这里给的思路分析是理想状态下的，比如假如要删除的节点是最后一个节点，那么就temp的next为null，temp.next.pre就会报错，所以实际使用的时候需要灵活运用！）**

### 代码实现： ###

**（在上面的基础上，注意由于我们的目的是实现节点的删除，所以这里的代码演示对需求进行了简化，不考虑链表为空、没找到对应id等情况，在实际工作中需要根据当时的实际需求进行优化完善！）**

package com.zb.ds;
    
    //测试双向链表
    public class TestLinkedList {
        public static void main(String[] args) {
            //测试双链表
            SingleLinkedList list = new SingleLinkedList();
            list.add(new HeroNode(1,"宋江","及时雨"));
            list.add(new HeroNode(3,"林冲","豹子头"));
            list.add(new HeroNode(5,"卢俊义","玉麒麟"));
            list.add(new HeroNode(7,"吴用","智多星"));
            //遍历
            list.show();
            //删除id位3的节点
            list.remove(3);
            list.show();
        }
    }
    //定义一个双链表，来管理我们的英雄
    class SingleLinkedList{
        //初始化一个头节点，头节点不要动
        private final HeroNode head = new HeroNode(0,"","");
    
        //添加节点
        public void add(HeroNode heroNode){
            HeroNode temp = head;
            while (temp.next != null) {
                //拿到下一个节点
                temp = temp.next;
            }
            //当前while循环退出，说明拿到了next为null的节点，也就是最后一个节点
            temp.next = heroNode;
            heroNode.pre = temp;
            System.out.println(heroNode.nickname + heroNode.name + "添加成功！");
        }
    
        //删除节点：通过id删除
        public void remove(int id){
            HeroNode temp = head;
            while (temp.next != null) {
                if(temp.next.id == id){
                    temp = temp.next;
                    //此时的temp就是要删除的节点
                    temp.pre.next = temp.next;
                    temp.next.pre = temp.pre;
                    break;
                }
                //拿到下一个节点
                temp = temp.next;
            }
        }
    
        //遍历输出
        public void show(){
            HeroNode temp = head;
            while (temp.next != null){
                System.out.println(temp.next.id + temp.next.nickname + temp.next.name);
                temp = temp.next;
            }
        }
    }
    
    //英雄
    class HeroNode{
        final int id;
        final String name;
        final String nickname;
        HeroNode next;
        HeroNode pre;
    
        public HeroNode(int id, String name, String nickname) {
            this.id = id;
            this.name = name;
            this.nickname = nickname;
        }
    }

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 3][]

## 4、插入节点 ##

### 图解： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 4][]

### 思路分析： ###

第一步：根据插入位置的条件（比如id），找到要插入位置的前一个节点，假设为t，假设要插入的节点为temp；

第二步：将t的下一个节点（next）保存起来，假设为p；

第三步：将t的下一个节点（next）设置为temp，将p的上一个节点（pre）设置为temp；

第四步：将temp的上一个节点（pre）设置为t，将t的下一个节点（next）设置为p；

### 代码演示： ###

package com.zb.ds;
    
    //测试双向链表
    public class TestLinkedList {
        public static void main(String[] args) {
            //测试双链表
            SingleLinkedList list = new SingleLinkedList();
            list.add(new HeroNode(1,"宋江","及时雨"));
            list.add(new HeroNode(3,"林冲","豹子头"));
            list.add(new HeroNode(5,"卢俊义","玉麒麟"));
            list.add(new HeroNode(7,"吴用","智多星"));
            //遍历
            list.show();
            //删除id位3的节点
            list.remove(3);
            list.show();
            //插入节点
            list.insert(5,new HeroNode(5,"呜啦啦","诸神天王"));
            list.show();
        }
    }
    //定义一个双链表，来管理我们的英雄
    class SingleLinkedList{
        //初始化一个头节点，头节点不要动
        private final HeroNode head = new HeroNode(0,"","");
    
        //添加节点
        public void add(HeroNode heroNode){
            HeroNode temp = head;
            while (temp.next != null) {
                //拿到下一个节点
                temp = temp.next;
            }
            //当前while循环退出，说明拿到了next为null的节点，也就是最后一个节点
            temp.next = heroNode;
            heroNode.pre = temp;
            System.out.println(heroNode.nickname + heroNode.name + "添加成功！");
        }
    
        //插入节点，根据id
        public void insert(int id,HeroNode temp){
            HeroNode t = head;
            while (t.next != null) {
                if(t.next.id == id){
                    //t为要插入节点位置的上一个节点
                    t = t.next;
                    HeroNode p = t.next;
                    t.next = temp;
                    p.pre = temp;
                    temp.pre = t;
                    temp.next = p;
                    break;
                }
                //拿到下一个节点
                t = t.next;
            }
        }
    
        //删除节点：通过id删除
        public void remove(int id){
            HeroNode temp = head;
            while (temp.next != null) {
                if(temp.next.id == id){
                    temp = temp.next;
                    //此时的temp就是要删除的节点
                    temp.pre.next = temp.next;
                    temp.next.pre = temp.pre;
                    break;
                }
                //拿到下一个节点
                temp = temp.next;
            }
        }
    
        //遍历输出
        public void show(){
            HeroNode temp = head;
            while (temp.next != null){
                System.out.println(temp.next.id + temp.next.nickname + temp.next.name);
                temp = temp.next;
            }
        }
    }
    
    //英雄
    class HeroNode{
        final int id;
        final String name;
        final String nickname;
        HeroNode next;
        HeroNode pre;
    
        public HeroNode(int id, String name, String nickname) {
            this.id = id;
            this.name = name;
            this.nickname = nickname;
        }
    }

### 运行结果： ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 5][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201102124147270.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201102125921319.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201102132034302.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201102134559505.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20201102140642552.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20201102142355463.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI5Njg5MzQz,size_16,color_FFFFFF,t_70