文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2023-06-30 16:53

关注

这篇文章主要讲解了“Java数据结构之双向链表如何实现”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“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.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数据结构之双向链表如何实现”的内容了,经过本文的学习后,相信大家对Java数据结构之双向链表如何实现这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是编程网,小编将为大家推送更多相关知识点的文章,欢迎关注!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯