|
# 数据结构-双链表的复杂删除以及更新查询 ![]()
## 概述 上一章中，我们已经实现了双链表的简单从尾部删除节点，那么在实际的容器删除节点时应该可以发现，需求不仅仅只是从尾部删除，可能直接删除的就是数据，那么此时数据在哪呢?如何删除呢?删除了节点，链表如何连接呢?接下来，咱们来看看如何去做。 ## 双链表介绍 双向链表也叫[双链表](https://baike.baidu.com/item/%E5%8F%8C%E9%93%BE%E8%A1%A8)，是链表的一种，它的每个数据结点中都有两个[指针](https://baike.baidu.com/item/%E6%8C%87%E9%92%88)，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。  ## 删除数据 删除数据的情况有4种： 1.链表只有一个节点 2.删除的数据为头节点 3.删除的数据为尾节点 4.删除的数据为中间节点 ### 分析 在删除时，先判断要删除的数据是否存在，如果存在再删除，删除时找到节点，并判断为上边的 情况中的哪一种情况即可。 ### 定义删除方法 ```java /** * 删除数据 * @param data */ public void remove(Object data){ //1.先根据数据data查找是否有该节点 Node node = findNodeByData(data); //2.判断是否有节点，如果有 则删除，否则 忽略 if(node!=null){ removeNode(node); } } ``` ### 根据数据查询节点对象 根据数据data 查询节点，如上代码中的findNodeByData(data)方法。 ```java /** * 根据数据查询节点 * @param data * @return */ private Node findNodeByData(Object data){ //从头节点开始遍历 Node node = head; while(node!=null){ //如果找到了 if(node.data.equals(data) && node.data.hashCode()==data.hashCode()){ //如果找到则跳出 break; }else { //如果没找到 继续往下找，将Node的引用指向下一个节点 node = node.next; } } return node; } ``` ### 删除查询到的节点对象 依次判断删除的为哪一种情况，并删除值。以下代码为方法：removeNode(node);的具体实现 ```java /** * 删除节点 * @param node */ private void removeNode(Node node) { if(head==node && rear==node) { //1.删除只有一个节点 head=null; rear=null; }else if(head==node) { //2.删除的是头节点 后面一定有节点 //代码顺序不能换 head=head.next;//将头结点的引用指向原头节点的下一个。 head.prev=null;//头节点的prev为Null即可 }else if(rear==node) { //3.删除的是尾节点 前面一定有节点 //代码的顺序不能换 rear=rear.prev;//将尾节点的引用指向原尾节点的上一个 rear.next=null;//将尾节点的next 赋值为null即可 }else { //4.删除的是中间节点 前后都要有节点 node.prev.next=node.next; node.next.prev=node.prev; } } ``` ### 删除过程解析 1.第一步中，删除的是只有一个节点，过程如下图所示： 只有一个节点，直接删除所有即可。  2.第二步中，删除的数据为头节点，如下图所示：  3.第三步中，删除的数据为尾节点，如下图所示：  4.第四步中，删除的数据为中间节点，如下图所示：  ### 整体代码 ```java package com.itheima; /** * @author 三国的包子 * @version 1.0 * @description 描述 * @title 标题 * @date 2018/7/10 * @package com.itheima */ public class DoubleLink { private class Node{ Node prev;//记录当前节点的上一个节点的内存地址 Node next;//记录当前节点的下一个节点的内存地址 Object data;//当前节点的数据 } private Node head;//头节点 private Node rear;//尾节点 /** * 删除数据 * @param data */ public void remove(Object data){ //1.先根据数据data查找是否有该节点 Node node = findNodeByData(data); //2.判断是否有节点，如果有 则删除，否则 忽略 if(node!=null){ removeNode(node); } } /** * 删除节点 * @param node */ private void removeNode(Node node) { if(head==node && rear==node) { //1.删除只有一个节点 head=null; rear=null; }else if(head==node) { //2.删除的是头节点 后面一定有节点 //代码顺序不能换 head=head.next;//将头结点的引用指向原头节点的下一个。 head.prev=null;//头节点的prev为Null即可 }else if(rear==node) { //3.删除的是尾节点 前面一定有节点 //代码的顺序不能换 rear=rear.prev;//将尾节点的引用指向原尾节点的上一个 rear.next=null;//将尾节点的next 赋值为null即可 }else { //4.删除的是中间节点 前后都要有节点 node.prev.next=node.next; node.next.prev=node.prev; } } /** * 根据数据查询节点 * @param data * @return */ private Node findNodeByData(Object data){ //从头节点开始遍历 Node node = head; while(node!=null){ //如果找到了 if(node.data.equals(data) && node.data.hashCode()==data.hashCode()){ //如果找到则跳出 break; }else { //如果没找到 继续往下找，将Node的引用指向下一个节点 node = node.next; } } return node; } /** * 从尾部添加节点 * @param data */ public void addFromRear(Object data){ // 1. 创建新的节点 Node node = new Node(); // 2. 把数据放入节点中 node.data = data; // 3. 判断尾部节点是否为空 如果为空说明链表还是空的 if (rear == null) { rear = node; head = node; } else { // 4. 判断如果尾部节点不为空，说明 链表是存在的 //将新增的节点的内存地址付给 原尾节点的的next 属性 rear.next = node; //将原尾节点的地址 付给 新增节点的 prev 属性 node.prev = rear; //最后 将新增的节点 付给尾节点引用 rear = node; } } //[a,b,c] @Override public String toString() { StringBuilder sbBuilder = new StringBuilder("["); // 遍历链表中所有的数据 Node node = head;// 从头节点开始遍历数据 while (node != null) { //如果node还没遍历到尾部节点 if (node != rear) { //就有逗号 sbBuilder.append(node.data + ", "); } else { sbBuilder.append(node.data); } // 条件的改变 node = node.next; } sbBuilder.append("]"); return sbBuilder.toString(); } } ``` ### 测试  ## 更新数据 ```java /*** * 更新数据 * @param oldData 传递旧数据 * @param newData 传递新数据 */ public void update(Object oldData ,Object newData){ Node nodeByData = findNodeByData(oldData); if(nodeByData!=null){ nodeByData.data = newData; } } ``` ## 总结 双链表的删除，主要分几种情况来删除即可，另外注意的是，在java中链表中删除对象，只需要将指向该对象的引用删除即可，剩下的由java的垃圾回收机制来回收对象即可。今天先到这，下一章我们来看看更为复杂的查询和迭代以及更新。
| 
收藏
淘帖
踩
