社区
学习
工具库
AI工具
休闲
搜索
简体中文
目录
双向链表（Doubly linked list）
双向链表的具体操作： 
双向链表实例：
首页 Java java教程 Java数据结构之双向链表的实现方式

Java数据结构之双向链表的实现方式

王林
王林
May 06, 2023 pm 07:04 PM
java

双向链表（Doubly linked list）

什么是双向链表？

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。

双向链表与单向链表的主要区别： 

查找方向 ： 单向链表的查找方向只能是一个方向，而双向链表可以向前或者向后查找。
删除： 单向链表的删除需要借助辅助指针，先找到要删除节点的前驱，然后进行删除。
           temp.next = temp.next.next;(temp为辅助指针)
           双向链表可以进行自我删除。 

双向链表与单向链表的优劣： 

优点：双链表结构比单链表结构更有优越性。

缺点：从存储结构来看，双向链表比单向链表多了一个指针，需要一个额外的、线性的内存使用量。（在32位操作系统中一个指针为4个字节，64位操作系统中一个指针为8个字节）。

双向链表的逻辑结构图解：

Java数据结构之双向链表如何实现

双向链表的具体操作： 

添加：
图解：

Java数据结构之双向链表如何实现

代码：

//添加一个节点到最后
    public void add(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                // 当temp.next 为空时，证明temp为最后一个元素。
                temp.next = newNode; //temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }
 
    //按学号顺序添加节点
    public void Sortadd(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                //说明要添加的节点序号在当前链表中最大，因此直接添加在末尾。
                temp.next = newNode;//temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            } else if (temp.next.ID > newNode.ID) {
                //当前节点的下一位节点的编号大于 要添加的新节点，则证明新节点要添加在temp节点之后
                newNode.next = temp.next;//要添加节点的下一位 指向temp当前节点的下一位
                temp.next.pre = newNode;//temp当前节点的下一位的前一位 指向 新节点构成双向链表
                temp.next = newNode; // 再让当前节点的下一位指向 新节点
                newNode.pre = temp;//新节点的前一位 指向 当前节点temp
                //这样连接完成后就将  新节点插入 到 原本链表的temp节点与temp.next节点之间
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }
登录后复制

删除 ：
图解：

Java数据结构之双向链表如何实现

代码：

 //删除一个节点。
    //自我删除
    public void DoubleDelete(int id) {
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                System.out.printf("要删除的%d节点不存在\n", id);
                break;
            } else if (temp.ID == id) {
                //找到要删除节点
                // 此时temp 就代表将要被删除节点
                //temp.pre.next 指 当前要被删除节点 的前一位 的后一位
                // temp.next  指 当前要被删除节点的后一位
                temp.pre.next = temp.next;
                // （当前要被删除节点 的前一位 的后一位）指向 （当前要被删除节点的后一位）
                //这样就完成了 temp节点的删除操作
 
                // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                }
                break;
            }
            temp = temp.next;
        }
    }
登录后复制

修改：
侃侃：它实际上与单链表的删除是一样。

代码：

//修改链表节点
    public void DoubleUpdate(DoubleNode newNode) {
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            } else if (temp.ID == newNode.ID) {
                //找到要修改的节点
                temp.name = newNode.name;
                temp.mark = newNode.mark;
                return;
            }
            temp = temp.next;
        }
        System.out.printf("要修改的%d节点不存在\n", newNode.ID);
    }
登录后复制

双向链表实例：

用双向链表创建一个学生信息管理系统，完成对学生信息的添加，删除，修改操作。

package Linkedlist;
 
//双向链表。
public class DoubleLinkedListDemo {
    public static void main(String agrs[]) {
        DoubleNode stu1 = new DoubleNode(6, "张三", 99);
        DoubleNode stu2 = new DoubleNode(2, "李四", 99);
        DoubleNode stu3 = new DoubleNode(3, "王五", 99);
        DoubleNode stu4 = new DoubleNode(5, "王二", 99);
        DoubleNode stu5 = new DoubleNode(4, "小红", 99);
        DoubleNode stu6 = new DoubleNode(1, "小明", 99);
        DoubleNode stu7 = new DoubleNode(1, "小明", 99);
 
        DoubleLinkedlist doubleLinkedlist = new DoubleLinkedlist();
 
       /* doubleLinkedlist.add(stu1);
        doubleLinkedlist.add(stu2);
        doubleLinkedlist.add(stu3);
        doubleLinkedlist.add(stu4);
        doubleLinkedlist.add(stu5);
        doubleLinkedlist.add(stu6);
        doubleLinkedlist.add(stu7);*/
 
        doubleLinkedlist.Sortadd(stu1);
        doubleLinkedlist.Sortadd(stu2);
        doubleLinkedlist.Sortadd(stu3);
        doubleLinkedlist.Sortadd(stu4);
        doubleLinkedlist.Sortadd(stu5);
        doubleLinkedlist.Sortadd(stu6);
        doubleLinkedlist.add(stu7);
 
        System.out.println("原链表展示！");
        doubleLinkedlist.ShowList();
        System.out.println();
 
        doubleLinkedlist.DoubleDelete(6);
        doubleLinkedlist.DoubleDelete(15);
        System.out.println("删除后链表展示！");
        doubleLinkedlist.ShowList();
        System.out.println();
 
 
        DoubleNode stu8 = new DoubleNode(1, "李思成", 100);
        DoubleNode stu9 = new DoubleNode(20, "李成", 100);
        doubleLinkedlist.DoubleUpdate(stu8);
        doubleLinkedlist.DoubleUpdate(stu9);
        System.out.println("修改后链表展示！");
        doubleLinkedlist.ShowList();
        System.out.println();
    }
}
 
class DoubleLinkedlist {
    private DoubleNode head = new DoubleNode(0, "", 0);
 
    public DoubleNode getHead() {
        return head;
    }
 
    //添加一个节点到最后
    public void add(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                // 当temp.next 为空时，证明temp为最后一个元素。
                temp.next = newNode; //temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }
 
    //按学号顺序添加节点
    public void Sortadd(DoubleNode newNode) {
        DoubleNode temp = head;
        while (true) {
            if (temp.next == null) {
                //说明要添加的节点序号在当前链表中最大，因此直接添加在末尾。
                temp.next = newNode;//temp节点的下一位指向新节点
                newNode.pre = temp;//新节点的前一位指向temp
                //这两步构成双向链表
                break;
            } else if (temp.next.ID > newNode.ID) {
                //当前节点的下一位节点的编号大于 要添加的新节点，则证明新节点要添加在temp节点之后
                newNode.next = temp.next;//要添加节点的下一位 指向temp当前节点的下一位
                temp.next.pre = newNode;//temp当前节点的下一位的前一位 指向 新节点构成双向链表
                temp.next = newNode; // 再让当前节点的下一位指向 新节点
                newNode.pre = temp;//新节点的前一位 指向 当前节点temp
                //这样连接完成后就将  新节点插入 到 原本链表的temp节点与temp.next节点之间
                break;
            }else if (temp.next.ID == newNode.ID) {
                //ID相同证明 已经存在该学生。
                System.out.printf("要插入学号为%d的学生已经存在。\n", newNode.ID);
                break;
            }
            temp = temp.next;
        }
    }
 
    //删除一个节点。
    //自我删除
    public void DoubleDelete(int id) {
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                System.out.printf("要删除的%d节点不存在\n", id);
                break;
            } else if (temp.ID == id) {
                //找到要删除节点
                // 此时temp 就代表将要被删除节点
                //temp.pre.next 指 当前要被删除节点 的前一位 的后一位
                // temp.next  指 当前要被删除节点的后一位
                temp.pre.next = temp.next;
                // （当前要被删除节点 的前一位 的后一位）指向 （当前要被删除节点的后一位）
                //这样就完成了 temp节点的删除操作
 
                // 如果是最后一个节点，就不需要执行下面这句话，否则出现空指针
                if (temp.next != null) {
                    temp.next.pre = temp.pre;
                }
                break;
            }
            temp = temp.next;
        }
    }
 
    //修改链表节点
    public void DoubleUpdate(DoubleNode newNode) {
        if (head.next == null) {
            System.out.println("链表为空！");
            return;
        }
        DoubleNode temp = head.next;
        while (true) {
            if (temp == null) {
                break;
            } else if (temp.ID == newNode.ID) {
                //找到要修改的节点
                temp.name = newNode.name;
                temp.mark = newNode.mark;
                return;
            }
            temp = temp.next;
        }
        System.out.printf("要修改的%d节点不存在\n", newNode.ID);
    }
 
    public void ShowList() {
        // 判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        // 因为头节点，不能动，因此我们需要一个辅助变量来遍历
        DoubleNode temp = head.next;
        while (true) {
            // 判断是否到链表最后
            if (temp == null) {
                break;
            }
            System.out.println(temp);// 输出节点的信息
            temp = temp.next;
        }
    }
}
 
class DoubleNode {
    public int ID; // 编号。
    public String name;
    public int mark;
    public DoubleNode next;
    public DoubleNode pre; // 前一个（Previous）
 
    public DoubleNode(int ID, String name, int mark) {
        this.ID = ID;
        this.name = name;
        this.mark = mark;
    }
 
    @Override
    public String toString() {
        return "DoubleNode{" + "ID=" + ID + ", name='" + name + '\'' + "mark=" + mark + '}';
    }
}
登录后复制

以上是Java数据结构之双向链表的实现方式的详细内容。更多信息请关注PHP中文网其他相关文章！

本站声明
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序，用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

显示更多

热门文章

R.E.P.O.能量晶体解释及其做什么（黄色晶体）
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O.最佳图形设置
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影：贝壳谜语解决方案
2 周前 By DDD
R.E.P.O.如果您听不到任何人，如何修复音频
3 周前 By 尊渡假赌尊渡假赌尊渡假赌
WWE 2K25：如何解锁Myrise中的所有内容
4 周前 By 尊渡假赌尊渡假赌尊渡假赌
显示更多

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版，非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

显示更多

热门话题

gmail邮箱登陆入口在哪里
7481
15
CakePHP 教程
1377
52
steam的账户名称是什么格式
77
11
win11激活密钥永久
51
19
NYT连接提示和答案
19
34
显示更多
Related knowledge
Java 中的完美数 Java 中的完美数 Aug 30, 2024 pm 04:28 PM

Java 完美数指南。这里我们讨论定义，如何在 Java 中检查完美数？，示例和代码实现。

Java 中的随机数生成器 Java 中的随机数生成器 Aug 30, 2024 pm 04:27 PM

Java 随机数生成器指南。在这里，我们通过示例讨论 Java 中的函数，并通过示例讨论两个不同的生成器。

Java中的Weka Java中的Weka Aug 30, 2024 pm 04:28 PM

Java 版 Weka 指南。这里我们通过示例讨论简介、如何使用weka java、平台类型和优点。

Java 中的史密斯数 Java 中的史密斯数 Aug 30, 2024 pm 04:28 PM

Java 史密斯数指南。这里我们讨论定义，如何在Java中检查史密斯号？带有代码实现的示例。

Java Spring 面试题 Java Spring 面试题 Aug 30, 2024 pm 04:29 PM

在本文中，我们保留了最常被问到的 Java Spring 面试问题及其详细答案。这样你就可以顺利通过面试。

突破或从Java 8流返回？ 突破或从Java 8流返回？ Feb 07, 2025 pm 12:09 PM

Java 8引入了Stream API，提供了一种强大且表达力丰富的处理数据集合的方式。然而，使用Stream时，一个常见问题是：如何从forEach操作中中断或返回？ 传统循环允许提前中断或返回，但Stream的forEach方法并不直接支持这种方式。本文将解释原因，并探讨在Stream处理系统中实现提前终止的替代方法。 延伸阅读： Java Stream API改进 理解Stream forEach forEach方法是一个终端操作，它对Stream中的每个元素执行一个操作。它的设计意图是处

Java 中的时间戳至今 Java 中的时间戳至今 Aug 30, 2024 pm 04:28 PM

Java 中的时间戳到日期指南。这里我们还结合示例讨论了介绍以及如何在java中将时间戳转换为日期。

创造未来：面向零基础的 Java 编程 创造未来：面向零基础的 Java 编程 Oct 13, 2024 pm 01:32 PM

Java是热门编程语言，适合初学者和经验丰富的开发者学习。本教程从基础概念出发，逐步深入讲解高级主题。安装Java开发工具包后，可通过创建简单的“Hello,World!”程序实践编程。理解代码后，使用命令提示符编译并运行程序，控制台上将输出“Hello,World!”。学习Java开启了编程之旅，随着掌握程度加深，可创建更复杂的应用程序。

See all articles