Java数据结构：双向链表的实现

柔情只为你懂 2023-09-24 13:33 54阅读 0赞

![在这里插入图片描述][11679f55924b489bbccdb68873ed705b.png]

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

### 文章目录 ###

*  1 双向链表
 *   *  1.1 双向链表介绍
     *  1.2 双向链表实现思路
 *  2 双向链表实现完整代码
 *   *  2.1 节点类 Student.java
     *  2.2 双向链表实现类 StudentDoubleLinkedList.java
     *  2.3 测试类 StudentDoubleLinkedListDemo.java
     *  2.4 结果
 *  3 双向链表小结
 *  写在最后

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

# 1 双向链表 #

## 1.1 双向链表介绍 ##

相较单链表，双向链表除了data与next域，还多了一个pre域用于表示每个节点的前一个元素。这样做给双向链表带来了很多优势：

1.  单向链表查找的方向只能是一个方向，而双向链表可以向前或者向后查找；
2.  单链表如果想要实现删除操作，需要找到待删除节点的前一个节点。而双向链表可以实现自我删除。

**双向链表结构示意图如下：**  
![在这里插入图片描述][771c1489b5214e0584823694417f8220.png]

## 1.2 双向链表实现思路 ##

与单链表实现类似，交集部分不再赘述，详情可参考文章：[Java数据结构：单链表的实现与面试题汇总][Java]

**遍历：**  
与单链表遍历方式一样，同时，双向链表可以支持向前和向后两种查找方式

**添加：**

*  **添加到末尾**
    
     *  先找到双向链表最后一个节点
     *  cur.next = newNode；
     *  newNode.pre = cur；
 *  **按照no顺序添加**
    
     *  先判断该链表是否为空，如果为空则直接添加
     *  如果不为空则继续处理
     *  根据no遍历链表，找到合适的位置
     *  newNode.next = cur.next;
     *  cur.next = newNode;
     *  newNode.pre = cur;

**修改操作与单链表实现步骤一致**

**删除操作：**

*  双向链表可以实现自我删除
 *  直接找到待删除的节点
 *  cur.pre.next = cur.next;
 *  cur.next.pre = cur.pre;
 *  需要特别注意是否为最后一个元素，如果为最后一个元素，cur.next为null，此时使用cur.next.pre会出现空指针异常，所以，如果为最后一个元素，则该步骤可以省略，cur.next为null即可。

**以删除红色的2号节点为例：**  
![在这里插入图片描述][9b94027460cc45fd87099db9aa72b3c1.png]

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

# 2 双向链表实现完整代码 #

## 2.1 节点类 Student.java ##

/**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 学生类节点
     */
    public class StudentNode {
        
        public String no; //学号
        public String name; //姓名
        public int age; //年龄
        public StudentNode pre; //指向前一个节点
        public StudentNode next; //指向下一个节点
    
        //构造器
        public StudentNode(String no, String name, int age ){
        
            this.no = no;
            this.name = name;
            this.age = age;
        }
    
        //为了显示方便
        @Override
        public String toString() {
        
            return "StudentNode{" +
                    "no='" + no + '\'' +
                    ", name='" + name + '\'' +
                    ", age=" + age +
                    '}';
        }
    }

## 2.2 双向链表实现类 StudentDoubleLinkedList.java ##

/**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 学生双向链表的具体实现
     */
    public class StudentDoubleLinkedList {
        
        //定义头节点
        private StudentNode head = new StudentNode("", "", 0);
    
        //获取头节点
        public StudentNode getHead(){
        
            return head;
        }
    
        //遍历双向链表的方法
        public void showList(){
        
            //判断链表是否为空
            if (head.next == null){
        
                System.out.println("当前链表为空");
                return;
            }
            //遍历 使用辅助指针
            StudentNode temp = head;
            while (temp != null){
        
                //更新指针
                temp = temp.next;
                if (temp.next == null){
        
                    System.out.print(temp);
                    break;
                }
                System.out.print(temp + "--->");
            }
        }
    
        //添加节点的方法
        //添加到尾部
        public void add(StudentNode newNode){
        
            //先找到最后一个节点
            StudentNode cur = head;
            while (true){
        
                //到达最后退出循环
                if (cur.next == null){
        
                    break;
                }
                //更新指针
                cur = cur.next;
            }
            //添加操作
            newNode.next = cur.next; //也可以省略，因为恒为null
            cur.next = newNode;
            newNode.pre = cur;
        }
    
        //添加节点的方法
        //根据学号顺序添加
        public void addByOrder(StudentNode newNode){
        
            //如果当前链表为空，则直接添加
            if (head.next == null){
        
                head.next = newNode;
                newNode.pre = head;
                return;
            }
            //按照学号找到对应位置
            StudentNode cur = head;
            boolean flag = false; //标识待添加的no是否存在
            while (true){
        
                if (cur.next == null){
        
                    //已经到达链表的尾部
                    break;
                } else if (Integer.parseInt(cur.next.no) == Integer.parseInt(newNode.no)){
        
                    //已经存在
                    flag = true;
                    break;
                }else if (Integer.parseInt(cur.next.no) > Integer.parseInt(newNode.no)){
        
                    //位置找到
                    break;
                }
                cur = cur.next;
            }
            if (flag){
        
                System.out.println("当前no已经存在，无法添加!");
            }else {
        
                //添加操作
                newNode.next = cur.next;
                cur.next = newNode;
                newNode.pre = cur;
            }
        }
    
        //根据no学号修改学生信息
        public void update(StudentNode studentNode){
        
            if (head.next == null){
        
                System.out.println("当前链表为空, 无法修改");
                return;
            }
            StudentNode temp = head.next;
            boolean flag = false; //表示是否找到节点
            while (true){
        
                if (temp == null){
        
                    break;
                }
                if (temp.no == studentNode.no){
        
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag){
        
                temp.name = studentNode.name;
                temp.age = studentNode.age;
                System.out.println("更新成功!");
            }else {
        
                System.out.println("没有找到");
            }
        }
    
        //从双向链表中删除节点
        public void delete(String no){
        
            //直接找到对应no的节点直接删除
            StudentNode cur = head.next;
            boolean flag = false; //标记是否找到
            while (true){
        
                if (cur == null){
        
                    break;
                }
                if (cur.no.equals(no)){
        
                    flag = true; //找到了
                    break;
                }
                cur = cur.next;
            }
            if (flag){
        
                //删除操作
                //注意考虑最后一个节点后一个为空的情况
                if (cur.next != null) {
        
                    cur.next.pre = cur.pre;
                }
                cur.pre.next = cur.next;
                System.out.println("删除成功!");
            }else {
        
                System.out.println( no + "节点不存在，无法删除！");
            }
        }
    }

## 2.3 测试类 StudentDoubleLinkedListDemo.java ##

/**
     * @author 兴趣使然黄小黄
     * @version 1.0
     * 双向链表测试类
     */
    public class DoubleLinkedListDemo {
        
        public static void main(String[] args) {
        
            StudentDoubleLinkedList doubleLinkedList = new StudentDoubleLinkedList();
            doubleLinkedList.addByOrder(new StudentNode("1", "黄小黄", 20));
            doubleLinkedList.addByOrder(new StudentNode("3", "懒羊羊", 20));
            doubleLinkedList.addByOrder(new StudentNode("2", "沸羊羊", 25));
            doubleLinkedList.addByOrder(new StudentNode("4", "美羊羊", 15));
            System.out.println("遍历:");
            doubleLinkedList.showList();
    
            //测试更新方法
            System.out.println("\n更新编号为4的信息后:");
            doubleLinkedList.update(new StudentNode("4", "祢豆子", 14));
            doubleLinkedList.showList();
    
            //测试删除方法
            System.out.println("\n删除第一个和最后一个:");
            doubleLinkedList.delete("1");
            doubleLinkedList.delete("4");
            doubleLinkedList.showList();
        }
    }

## 2.4 结果 ##

遍历:
    StudentNode{no='1', name='黄小黄', age=20}--->StudentNode{no='2', name='沸羊羊', age=25}--->StudentNode{no='3', name='懒羊羊', age=20}--->StudentNode{no='4', name='美羊羊', age=15}
    更新编号为4的信息后:
    更新成功!
    StudentNode{no='1', name='黄小黄', age=20}--->StudentNode{no='2', name='沸羊羊', age=25}--->StudentNode{no='3', name='懒羊羊', age=20}--->StudentNode{no='4', name='祢豆子', age=14}
    删除第一个和最后一个:
    删除成功!
    删除成功!
    StudentNode{no='2', name='沸羊羊', age=25}--->StudentNode{no='3', name='懒羊羊', age=20}
    Process finished with exit code 0

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

# 3 双向链表小结 #

*  单向链表查找的方向只能为一个方向，双向链表解决了这个缺点，可以实现双向查找；
 *  单链表进行删除操作必须找到待删除元素的前一个元素，才能完成删除操作。而双向链表就简单多了，只需要找到待删除的节点，进行自我删除；
 *  本节介绍了双向链表的遍历、添加、按顺序添加、更新、删除方法的实现，可以尝试像单链表篇一样，尝试求有效节点数量，以及如何逆序输出双向链表加强练习！

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

# 写在最后 #

**本文被 [Java数据结构][Java 1] 收录[点击订阅专栏][Java 1]** ， 持续更新中。  
 创作不易，如果你有任何问题，欢迎私信，感谢您的支持！  
![在这里插入图片描述][33ad3bfbfa084fe792cdcea04e64ede9.gif_pic_center]  
![在这里插入图片描述][ad16d93416c74666a97b046cb173134c.gif_pic_center]

[11679f55924b489bbccdb68873ed705b.png]: https://img-blog.csdnimg.cn/11679f55924b489bbccdb68873ed705b.png
[771c1489b5214e0584823694417f8220.png]: https://img-blog.csdnimg.cn/771c1489b5214e0584823694417f8220.png
[Java]: https://hxh2001.blog.csdn.net/article/details/127486706
[9b94027460cc45fd87099db9aa72b3c1.png]: https://img-blog.csdnimg.cn/9b94027460cc45fd87099db9aa72b3c1.png
[Java 1]: https://blog.csdn.net/m0_60353039/category_12062687.html
[33ad3bfbfa084fe792cdcea04e64ede9.gif_pic_center]: https://img-blog.csdnimg.cn/33ad3bfbfa084fe792cdcea04e64ede9.gif#pic_center
[ad16d93416c74666a97b046cb173134c.gif_pic_center]: https://img-blog.csdnimg.cn/ad16d93416c74666a97b046cb173134c.gif#pic_center