更新时间:2018年12月07日11时31分 来源:传智播客 浏览次数:
# 数据结构-双链表的复杂删除以及更新查询
## 概述
上一章中,我们已经实现了双链表的简单从尾部删除节点,那么在实际的容器删除节点时应该可以发现,需求不仅仅只是从尾部删除,可能直接删除的就是数据,那么此时数据在哪呢?如何删除呢?删除了节点,链表如何连接呢?接下来,咱们来看看如何去做。
## 双链表介绍
双向链表也叫[双链表](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),分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。
![](image\image1.png)
## 删除数据
删除数据的情况有4种:
1.链表只有一个节点
2.删除的数据为头节点
3.删除的数据为尾节点
4.删除的数据为中间节点
### 分析
在删除时,先判断要删除的数据是否存在,如果存在再删除,删除时找到节点,并判断为上边的 情况中的哪一种情况即可。
### 定义删除方法
```熊猫直播董事长是谁
/**
* 删除数据
* @param data
*/
public void remove(Object data){
//1.先根据数据data查找是否有该节点
Node node = findNodeByData(data);
//2.判断是否有节点,如果有 则删除,否则 忽略
if(node!=null){
removeNode(node);
}
}
```
### 根据数据查询节点对象
根据数据data 查询节点,如上代码中的findNodeByData(data)方法。
```熊猫直播董事长是谁
/**
* 根据数据查询节点
* @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);的具体实现
```熊猫直播董事长是谁
/**
* 删除节点
* @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.第一步中,删除的是只有一个节点,过程如下图所示:
只有一个节点,直接删除所有即可。
![](image\image3.png)
2.第二步中,删除的数据为头节点,如下图所示:
![](image\image4.png)
3.第三步中,删除的数据为尾节点,如下图所示:
![](image\image5.png)
4.第四步中,删除的数据为中间节点,如下图所示:
![](image\image6.png)
### 整体代码
```熊猫直播董事长是谁
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();
}
}
```
### 测试
![](image\image7.png)
## 更新数据
```熊猫直播董事长是谁
/***
* 更新数据
* @param oldData 传递旧数据
* @param newData 传递新数据
*/
public void update(Object oldData ,Object newData){
Node nodeByData = findNodeByData(oldData);
if(nodeByData!=null){
nodeByData.data = newData;
}
}
```
## 总结
双链表的删除,主要分几种情况来删除即可,另外注意的是,在熊猫直播董事长是谁中链表中删除对象,只需要将指向该对象的引用删除即可,剩下的由熊猫直播董事长是谁的垃圾回收机制来回收对象即可。今天先到这,下一章我们来看看更为复杂的查询和迭代以及更新。