Java数据结构之双向链表图解
双向链表（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中双向链表详解及实例
Java中双向链表详解及实例 写在前面: 双向链表是一种对称结构,它克服了单链表上指针单向性的缺点,其中每一个节点即可向前引用,也可向后引用,这样可以更方便的插入.删除数据元素. 由于双向链表需要同时维护两个方向的指针,因此添加节点.删除节点时指针维护成本更大:但双向链表具有两个方向的指针,因此可以向两个方向搜索节点,因此双向链表在搜索节点.删除指定索引处节点时具有较好的性能. Java语言实现双向链表: package com.ietree.basic.datastructure.dublin
-
Java双向链表按照顺序添加节点的方法实例
分析过程: 首先需要比较待添加的节点编号与已有的节点编号的大小,若待添加的节点编号已经存在,则不能加入.为防止出现空指针的情况,需要对节点的位置进行判断. 示例代码: package linkedlist; public class DoubleLinkedListDemo { public static void main(String[] args) { // 测试 System.out.println("双向链表的测试"); // 创建节点 Node node1 = new No
-
JAVA实现双向链表的增删功能的方法
JAVA实现双向链表的增删功能,完整代码 package linked; class LinkedTable{ } public class LinkedTableTest { //构造单链表 static Node node1 = new Node("name1"); static Node node2 = new Node("name2"); static Node node3 = new Node("name3"); static Node
-
Java语言中链表和双向链表
链表是一种重要的数据结构,在程序设计中占有很重要的地位.C语言和C++语言中是用指针来实现链表结构的,由于Java语言不提供指针,所以有人认为在Java语言中不能实现链表,其实不然,Java语言比C和C++更容易实现链表结构.Java语言中的对象引用实际上是一个指针(本文中的指针均为概念上的意义,而非语言提供的数据类型),所以我们可以编写这样的类来实现链表中的结点. class Node { Object data; Node next;//指向下一个结点 } 将数据域定义成Object类是因为
-
java数据结构之实现双向链表的示例
复制代码 代码如下: /** * 双向链表的实现 * @author Skip * @version 1.0 */public class DoubleNodeList<T> { //节点类 private static class Node<T>{ Node<T> perv; //前节点 Node<T> next; //后节点 T data; //数据 public Node(T t){ this.data = t; } } priv
-
Java实现双向链表(两个版本)
临近春节,项目都结束了,都等着回家过年了.下面是小编给大家研究数据结构的相关知识,链表算是经常用到的一种数据结构了,现将自己的实现展示如下,欢迎大神赐教. 第一个版本,没有最后一个节点,每次从根节点开始遍历 public class LinkedList<E> { private Node head; public LinkedList() { } public E getFirst(){ if(head==null){ return null; } return head.value; }
-
java实现单链表、双向链表
本文实例为大家分享了java实现单链表.双向链表的相关代码,供大家参考,具体内容如下 java实现单链表: package code; class Node { Node next; int data; public Node(int data) { this.data=data; } } class LinkList { Node first; //头部 public LinkList() { this.first=null; } public void addNode(Node no) {
-
java 实现双向链表实例详解
java 实现双向链表实例详解 双向链表是一个基本的数据结构,在Java中LinkedList已经实现了这种结构,不过作为开发者,也要拥有自己显示这种结构的能力.话不多说,上代码: 首先是链表的节点类: /** * 链表节点 * @author Administrator * * @param <T> */ public class ChainNode<T> { private T data; //对象编号 private int dataNo; public ChainN
-
java中使用双向链表实现贪吃蛇程序源码分享
使用双向链表实现贪吃蛇程序 1.链表节点定义: package snake; public class SnakeNode { private int x; private int y; private SnakeNode next; private SnakeNode ahead; public SnakeNode() { } public SnakeNode(int x, int y) { super(); this.x = x; this.y = y; } public int getX(
-
java数据结构基础:单链表与双向链表
目录 单链表: 实现思路: 代码实现: 双向链表: 实现思路: 代码实现: 总结 单链表: 每个数据是以节点的形式存在的 每个节点分为数据域和指针域 数据域中保存该节点的数据 指针域中保存指向下一个节点的指针 实现思路: 节点类SingleNode中保存数据和指向下一个节点的指针 单链表类SingleLinkedList中保存链表的头节点,实现相关链表方法 对于链表方法,涉及到位置查找,如在指定位置增加.删除节点,需要使用一个临时变量temp从头节点开始遍历,直至找到对应的位置. 对于节点的增加