教育行业A股IPO第一股(股票代码 003032)

全国咨询/投诉热线:400-618-4000

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

更新时间: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.删除的数据为中间节点

### 分析

​ 在删除时,先判断要删除的数据是否存在,如果存在再删除,删除时找到节点,并判断为上边的 情况中的哪一种情况即可。

### 定义删除方法

```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.第一步中,删除的是只有一个节点,过程如下图所示:

只有一个节点,直接删除所有即可。

![](image\image3.png)

2.第二步中,删除的数据为头节点,如下图所示:

![](image\image4.png)

3.第三步中,删除的数据为尾节点,如下图所示:

![](image\image5.png)

4.第四步中,删除的数据为中间节点,如下图所示:

![](image\image6.png)

### 整体代码

```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();

}

}

```

### 测试

​ ![](image\image7.png)

## 更新数据

```java

/***

* 更新数据

* @param oldData 传递旧数据

* @param newData 传递新数据

*/

public void update(Object oldData ,Object newData){

Node nodeByData = findNodeByData(oldData);

if(nodeByData!=null){

nodeByData.data = newData;

}

}

```

## 总结

​ 双链表的删除,主要分几种情况来删除即可,另外注意的是,在java中链表中删除对象,只需要将指向该对象的引用删除即可,剩下的由java的垃圾回收机制来回收对象即可。今天先到这,下一章我们来看看更为复杂的查询和迭代以及更新。

0 分享到:
和我们在线交谈!