莱州市规划建设管理局网站,湖南网站排名,wordpress标签后缀名html,石家庄做企业网站最好的公司文章目录一、什么是双向链表二、双向链表的简单实现一、什么是双向链表
我们来看一下这个例子#xff1a;
在一个教室里#xff0c;所有的课桌排成一列#xff0c;如图
相信在你们的读书生涯中#xff0c;老师肯定有要求你们记住自己的前后桌是谁。所以该例子中#x…
文章目录一、什么是双向链表二、双向链表的简单实现一、什么是双向链表
我们来看一下这个例子
在一个教室里所有的课桌排成一列如图
相信在你们的读书生涯中老师肯定有要求你们记住自己的前后桌是谁。所以该例子中老师就要求学生们记住自己的前后桌其中坐在第一排的学生需要记住自己是第一排的学生以及自己的后桌是谁最后一排的学生要记住自己的前桌是谁以及自己是最后一排的学生。如图
这一列座位就相当于一个 双向链表。
假如有一天老师还没记住每个学生的名字于是就问这一列第三个人叫什么名字这时就要从第一个学生开始数例如从图中坐在第一个的 小5 开始数第一个人是 小5他的后桌是 小7因此第二个人就是 小7他的后桌是 小1因此第三个人就是 小1 了。此时老师问 小1你的前桌叫什么名字你的后桌叫什么名字
因为刚开始老师就让每个学生记住了自己的前桌以及后桌所以此时 小1 能很快地告诉老师他的前桌是 小7他的后桌是 小6。
但是我们设想一下如果是上一篇文章的 链表结构 的例子中如果老师在得知了第三个人是 小1 以后询问 小1 的前桌叫什么名字小1 能回答上来吗并不能因为老师只让每个学生记住了自己的后桌所以此时想要得知 小1 的前桌叫什么名字只能这样第三个学生叫 小1那么他的前桌就坐在第二个位置所以从第一个学生开始数第一个学生是 小5他的后桌是 小7因此第二个学生就是 小7。当然本文举得例子中学生数量有点少但一旦数量多起来了每次问一个学生他的前桌叫什么名字的时候都要从头开始数。
从中可以看出让每个学生记住自己的前桌后桌是非常有必要的因为在某些情况下可以快速地解决问题。
上面讲了那么多接下来我们就来看一下 双向链表 是什么样的如图 可以看到对比 链表结构双向链表 多了一个指针 tail它是指向最后一个元素的就相当于例子中的学生记住了自己是最后一排。
双向链表与单链表基本相似但是最大的区别在于双向链表在节点中除了指向下一节点的next指针外还有指向前一节点的prev指针这使得双向链表在可以在任意节点从头尾两个方向进行遍历是“双向”的。
和单链表相比双向链表在删除和查询等方面明显在操作上更具有灵活性但是会消耗更多的内存需要根据使用条件进行取舍。
java中的LinkedHashMap的本质即是一个双向链表。
二、双向链表的简单实现
修改原来的Node类在里面添加一个新成员变量Node prev
/*** Authorhuang* Date2023-03-23 20:10* Description节点类*/
public class Node {//节点序号int num;//数据Object data;//下一个节点Node next;//上一节点Node prev;public Node(int num, Object data) {this.num num;this.data data;}Overridepublic String toString() {return Node{ num num , data data };}
}添加 添加与单向链表代码逻辑一样但是新节点在添加时需要修改prev指针指向原来的尾节点。 举个例子对于无排序插入原本有节点A现在要插入一个B
找到A然后让A.next指向B让B.prev指向A
而对于排序插入就是原有节点AC要在中间插入B
找到A让B.prev指向A让B.next指向A.next也就是让B的next指向C让A.next.prev指向B也就是让C的prev指向B让A.next指向B
/*** 添加节点到链表* param node 要插入的节点*/
public void add(Node node) {Node temp head;//遍历链表while (true) {if (temp.next null) {break;}//不是尾节点就继续遍历下一个节点temp temp.next;}//将尾节点指向即将插入的新节点temp.next node;node.prev temp;
}/*** 按顺序添加节点到链表* param node 要插入的节点*/
public void addByOrder(Node node) {Node temp head;//遍历链表while (true) {//如果链表到底了就直接插入if (temp.next null) {temp.next node;node.prev temp;return;}else if (temp.next.num node.num){//如果后一节点比当新节点大就插入当前节点node.prev temp;node.next temp.next;temp.next.prev node;temp.next node;return;}else if (temp.next.num node.num){//如果后一节点等于新节点抛异常throw new RuntimeException(插入节点与已有节点序号重复);}//如果后一节点比当前节点小就继续遍历temp temp.next;}
}删除 由于相对单链表双向链表的节点可以自己找到上一节点所以删除的时候可以直接找到要删除的节点进行操作。
举个例子假设有节点ABC现在要删除B
找到B让B.prev.nextB.next也就是让A的next指向C让B.next.prevB.prev也就是让C的prev指向A
如果要删除的节点已经是尾节点了那就跟单链表一样了。
/*** 删除节点* param num 要删除的节点编号*/
public void delete(int num) {Node temp head;//判断链表是否为空if (temp.next null) {throw new RuntimeException(链表为空);}//遍历链表while (true) {//如果链表到底了if (temp.next null) {throw new RuntimeException(编号为 num 的节点不存在);}//如果找到了待删除节点的前一个节点if (temp.num num) {//判断待删除节点是否为尾节点if (temp.next null){temp.prev.next null;}else {temp.prev.next temp.next;temp.next.prev temp.prev;}return;}//继续遍历下一节点temp temp.next;}
}修改查询与单链表一致 由于修改和查询与单链表基本一致这里就不在赘述了直接放代码
/*** 展示链表*/
public void show() {//判断链表是否为空if (head.next null) {throw new RuntimeException(链表为空);}Node temp head.next;//遍历链表while (true) {if (temp null) {break;}System.out.println(temp.toString());temp temp.next;}
}/*** 根据序号获取节点* param num 要获取的节点序号* return*/
public Node get(int num){//判断链表是否为空if (head.next null) {throw new RuntimeException(链表为空);}Node temp head.next;//遍历链表while (true) {if (temp null) {throw new RuntimeException(编号为 num 的节点不存在);}if (temp.num num) {return temp;}temp temp.next;}
}/*** 修改节点* param node 要更新的节点*/
public void update(Node node) {Node temp head;//判断链表是否为空if (temp.next null) {throw new RuntimeException(链表为空);}//获取要更新的节点序号int nodeNum node.num;//遍历链表while (true) {//如果已经遍历完链表if (temp null) {throw new RuntimeException(编号为 temp.num 的节点不存在);}//如果找到了该节点if (temp.num nodeNum) {temp.data node.data;return;}//继续遍历下一节点temp temp.next;}
}
