数据结构与算法—一文多图搞懂双链表 agile Posted on Jul 13 2023 数据结构与算法 ### 前言 前面有很详细的讲过线性表(顺序表和链表)，当时讲的链表以但链表为主，但实际上在实际应用中双链表的应用多一些就比如LinkedList。  #### 双链表与单链表区别 逻辑上它们均是线性表的链式实现，主要的区别是节点结构上的构造有所区别，这个区别从而引起操作的一些差异。 **单链表：** 单链表的一个节点，有储存数据的`data`，还有后驱节点`next`(指针)。也就是这个单链表想要一些遍历的操作都得通过**前节点—>后节点**。  **双链表：** 双链表的一个节点，有存储数据的`data`,也有后驱节点`next`(指针)，这和单链表是一样的，但它还有一个前驱节点`pre`(指针)。  #### 双链表结构的设计 上文讲单链表的时候，我们当时设计的是一个带头结点的链表就错过了不带头结点操作方式，这里双链表咱们就**不带头结点设计实现**。并且上文单链表实现的时候是没有尾指针tail的，在这里我们设计的双链表**带尾指针**。 所以我们构造的这个双链表是：**不带头节点、带尾指针(tail)、双向链表。** **对于node节点：** ```java class node<T> { T data; node<T> pre; node<T> next; public node() { } public node(T data) { this.data = data; } } ``` **对于链表：** ```java public class doubleList<T> { private node<T> head;// 头节点 private node<T> tail;// 尾节点 private int length; //各种方法 } ``` ### 具体操作分析 对于一个链表主要的操作还是增删。增删的话不光需要考虑链表是否带头节点，还有头插、尾插、中间插等多种插入删除形式，其中的一些细节处理也是比较重要的(防止链表崩掉出错)，如果你对这块理解不够深入很容易写错也很难排查出来。当然，链表的查找、按位修改操作相比增删操作还是容易很多。 #### 初始化 双链表在最初的时候头指针指向为`null`。那么对于这个不带头节点的双链表而言。它的`head`**始终指向第一个真实有效的节点**。`tail`也指向最后一个有效的节点。在最初的时候`head=null`，并且`tail=head`，此时链表为空，等待节点插入。 ```java public doubleList() { head = null; tail = head; length = 0; } ``` #### 插入 **空链表插入** - 对于空链表来说。增加第一个元素可以特殊考虑。因为在链表为空的时候`head`和`tail`均为null。但head和tail又需要实实在在指向链表中的真实数据(带头指针就不需要考虑)。所以这时候就新建一个`node`让**head、tail等于它**。 ```java node<T> teamNode = new node(data); if (isEmpty()) { head = teamNode; tail = teamNode; } ``` **头插** >对于头插入来说。步骤很简单，只需考虑head节点的变化。 1. 新建插入节点node 2. head前驱指向node 3. node后驱指向head 4. head指向node。(这时候head只是表示第二个节点，而head需要表示第一个节点故改变指向)  尾插： >对于尾插入来说。只需考虑尾节点tail节点的变化。 1. 新建插入节点node 2. node前驱指向tail 3. tail后驱指向node 4. tail指向node。(这时候tail只是表示倒数第二个节点，而tail需要表示最后节点故指向node)  **按编号插入** >对于编号插入来说。要考虑查找和插入两部，而插入既和head无关也和tail无关。 1 新建插入节点node 2 找到欲插入node的前一个节点`preNode`。和后一个节点`nextNode` 3 **node后驱指向nextNode,nextNode前驱指向node**(此时node和后面与链表已经联立，但是和前面处理分离状态)  4 **preNode后驱指向node。node前驱指向preNode**(此时插入完整操作完毕)  整个流程的动态图为：  #### 删除 **只有单个节点删除** >无论头删还是尾删，遇到单节点删除的需要将链表从新初始化！ ```java if (length == 1)// 只有一个元素 { head = null; tail = head; length--; } ``` **头删除** >头删除需要注意的就是删除不为空时候头删除只和head节点有关 流程大致分为： 1 head节点的**后驱节点**的**前指针pre**改为null。(head后面节点本指向head但是要删除第一个先让后面那个和head`断绝关系`)  2 head节点指向head.next(这样head就指向我们需要的第一个节点了，前面节点就被删除成功，如果有c++等语言第一个被孤立的节点删除释放即可，但Java会自动释放)  **尾删除** >尾删除需要注意的就是删除不为空时候尾删除**只和tail节点有关**。记得在普通链表中，我们删除尾节点需要找到尾节点的前驱节点。需要遍历整个表，而双向链表可以直接从尾节点遍历到前面。 尾删除就是删除双向链表中的最后一个节点，也就是尾指针所指向的那个节点，思想和头删除的思想一致，具体步骤为： 1. `tail.pre.next=null`尾节点的前一个节点(pre)的后驱节点等于null 2. `tail=tail.pre `尾节点指向它的前驱节点，此时尾节点由于步骤`1`next已经为null。完成删除  **普通删除** >普通删除需要重点掌握，普通删除要妥善处理好待删除节点的前后关系，具体流程如下： 1：找打待删除节点node的前驱节点prenode(prenode.next是要删除的节点) 2 : `prenode.next.next.pre=prenode`.（将待删除node的后驱节点aftnode的pre指针指向prenode，等价于`aftnode.pre=prenode`）  3: `prenode.next=prenode.next.next;`此时node被跳过成功删除。  完成删除整个流程的动态图为：  ### 实现与测试 通过上面的思路简单的实现一下双链表，当然有些地方命名不太规范，实现效率有待提升，主要目的还是带着大家理解。 代码： ```java /* * 不带头节点的 */ public class doubleList<T> { class node<T> { T data; node<T> pre; node<T> next; public node() { } public node(T data) { this.data = data; } } private node<T> head;// 头节点 private node<T> tail;// 尾节点 private int length; public doubleList() { head = null; tail = head; length = 0; } boolean isEmpty() { return length == 0 ? true : false; } void addFirst(T data) { node<T> teamNode = new node(data); if (isEmpty()) { head = teamNode; tail = teamNode; } else { teamNode.next = head; head = teamNode; } length++; } void add(T data)// 默认尾节点插入 { node<T> teamNode = new node(data); if (isEmpty()) { head = teamNode; tail = teamNode; } else { tail.next = teamNode; teamNode.pre=tail; tail = teamNode; } length++; } int length() { return length; } T getElum(int index)//为了简单统一从头找 { node<T> team=head; for(int i=0;i<index;i++)//不带头节点 遍历次数-1 { team=team.next; } return team.data; } void add(int index, T data)// 编号插入 { if (index == 0) { addFirst(data); } else if (index == length) { add(data); } else {// 重头戏 node teampre = head;// 为插入的前驱 // 无头节点，index-1位置找到前驱节点 for (int i = 0; i < index -1; i++) { teampre = teampre.next; } node<T> team = new node(data);// a c 中插入B 找打a team.next = teampre.next;// B.next=c teampre.next.pre = team;// c.pre=B team.pre = teampre;// 关联a B teampre.next = team; length++; } } void deleteFirst()// 头部删除 { if (length == 1)// 只有一个元素 { head = null; tail = head; length--; } else { head = head.next; length--; } } void deleteLast() { if(length==1) { head=null; tail=head; length--; } else { tail.pre.next=null; tail=tail.pre; length--; } } void delete(int index) { if(index==0)deleteFirst(); else if (index==length-1) { deleteLast(); } else {//删除 为了理解统一从头找那个节点 node<T>team=head; for(int i=0;i<index-1;i++) { team=team.next; } //team 此时为要删除的前节点 a c 插入B a为team team.next.next.pre=team;//c的前驱变成a team.next=team.next.next;//a的后驱变成c length--; } } void set(int index,T data) { node<T>team=head; for(int i=0;i<index-1;i++) { team=team.next; } team.data=data; } @Override public String toString() { node<T> team = head; String vaString = ""; while (team != null) { vaString += team.data + " "; team = team.next; } return vaString; } } ``` 测试：  ### 结语 在插入删除的步骤，很多人可能因为繁琐的过程而弄不明白，但实际上这个操作的写法可能是多样的，但本质操作都是一致的，所以看到其他不同版本有差距也是正常的。 还有很多人可能对一堆next.next搞不清楚，那我教你一个技巧，如果在等号右侧，那么它表示一个节点，如果在等号左侧，那么除了最后一个.next其他的表示节点。例如node.next.next.next可以看成(node.next.next).next。 在做数据结构与算法链表相关题的时候，不同题可能给不同节点去完成插入、删除操作。这种情况操作时候要谨慎先后顺序防止破坏链表结构。 代码操作可能有些优化空间，还请各位大佬指正！  数据结构与算法—图论之dfs、bfs(深度优先搜索、宽度优先搜索) 数据结构与算法—栈详解
