java数据结构-双链表的删除与更新

# 数据结构-双链表的复杂删除以及更新查询

## 概述

​ 上一章中，我们已经实现了双链表的简单从尾部删除节点，那么在实际的容器删除节点时应该可以发现，需求不仅仅只是从尾部删除，可能直接删除的就是数据，那么此时数据在哪呢?如何删除呢?删除了节点，链表如何连接呢?接下来，咱们来看看如何去做。

## 双链表介绍

​ 双向链表也叫[双链表](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的垃圾回收机制来回收对象即可。今天先到这，下一章我们来看看更为复杂的查询和迭代以及更新。