# 数据结构-双链表的复杂删除以及更新查询
## 概述
上一章中，我们已经实现了双链表的简单从尾部删除节点，那么在实际的容器删除节点时应该可以发现，需求不仅仅只是从尾部删除，可能直接删除的就是数据，那么此时数据在哪呢?如何删除呢?删除了节点，链表如何连接呢?接下来，咱们来看看如何去做。
## 双链表介绍
双向链表也叫[双链表](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的垃圾回收机制来回收对象即可。今天先到这，下一章我们来看看更为复杂的查询和迭代以及更新。
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/253344.html