双向链表(Doubly linked list)
什么是双向链表?
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。
双向链表与单向链表的主要区别:
查找方向 : 单向链表的查找方向只能是一个方向,而双向链表可以向前或者向后查找。
删除: 单向链表的删除需要借助辅助指针,先找到要删除节点的前驱,然后进行删除。
temp.next = temp.next.next;(temp为辅助指针)
双向链表可以进行自我删除。
双向链表与单向链表的优劣:
优点:双链表结构比单链表结构更有优越性。
缺点:从存储结构来看,双向链表比单向链表多了一个指针,需要一个额外的、线性的内存使用量。(在32位操作系统中一个指针为4个字节,64位操作系统中一个指针为8个字节)。
双向链表的逻辑结构图解:
双向链表的具体操作:
添加:
图解:
代码:
//添加一个节点到最后 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); }
双向链表实例:
用双向链表创建一个学生信息管理系统,完成对学生信息的添加,删除,修改操作。
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中文网其他相关文章!

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于结构化数据处理开源库SPL的相关问题,下面就一起来看一下java下理想的结构化数据处理类库,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于PriorityQueue优先级队列的相关知识,Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列,PriorityQueue是线程不安全的,PriorityBlockingQueue是线程安全的,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于java锁的相关问题,包括了独占锁、悲观锁、乐观锁、共享锁等等内容,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于多线程的相关问题,包括了线程安装、线程加锁与线程不安全的原因、线程安全的标准类等等内容,希望对大家有帮助。

本篇文章给大家带来了关于Java的相关知识,其中主要介绍了关于关键字中this和super的相关问题,以及他们的一些区别,下面一起来看一下,希望对大家有帮助。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于枚举的相关问题,包括了枚举的基本操作、集合类对枚举的支持等等内容,下面一起来看一下,希望对大家有帮助。

封装是一种信息隐藏技术,是指一种将抽象性函式接口的实现细节部分包装、隐藏起来的方法;封装可以被认为是一个保护屏障,防止指定类的代码和数据被外部类定义的代码随机访问。封装可以通过关键字private,protected和public实现。

本篇文章给大家带来了关于java的相关知识,其中主要介绍了关于设计模式的相关问题,主要将装饰器模式的相关内容,指在不改变现有对象结构的情况下,动态地给该对象增加一些职责的模式,希望对大家有帮助。


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

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

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

Dreamweaver CS6
视觉化网页开发工具

禅工作室 13.0.1
功能强大的PHP集成开发环境

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能

SublimeText3 英文版
推荐:为Win版本,支持代码提示!

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