搜索
首页Javajava教程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无尽的。

显示更多

热门文章

刺客信条阴影：贝壳谜语解决方案
3 周前ByDDD
Windows 11 KB5054979中的新功能以及如何解决更新问题
2 周前ByDDD
在哪里可以找到原子中的起重机控制钥匙卡
3 周前ByDDD
节省R.E.P.O.解释（并保存文件）
1 个月前By尊渡假赌尊渡假赌尊渡假赌
刺客信条阴影 - 如何找到铁匠，解锁武器和装甲定制
3 周前ByDDD
显示更多

热工具

SublimeText3汉化版

SublimeText3汉化版

中文版，非常好用

MinGW - 适用于 Windows 的极简 GNU

MinGW - 适用于 Windows 的极简 GNU

这个项目正在迁移到osdn.net/projects/mingw的过程中，你可以继续在那里关注我们。MinGW：GNU编译器集合（GCC）的本地Windows移植版本，可自由分发的导入库和用于构建本地Windows应用程序的头文件；包括对MSVC运行时的扩展，以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

mPDF

mPDF

mPDF是一个PHP库，可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件，并处理不同的语言。与原始脚本如HTML2FPDF相比，它的速度较慢，并且在使用Unicode字体时生成的文件较大，但支持CSS样式等，并进行了大量增强。支持几乎所有语言，包括RTL（阿拉伯语和希伯来语）和CJK（中日韩）。支持嵌套的块级元素（如P、DIV），

禅工作室 13.0.1

禅工作室 13.0.1

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

显示更多

热门话题

gmail邮箱登陆入口在哪里
7563
15
CakePHP 教程
1384
52
steam的账户名称是什么格式
84
11
win11激活密钥永久
60
19
NYT连接提示和答案
28
99
显示更多