全国咨询/投诉热线: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的垃圾回收机制来回收对象即可。今天先到这,下一章我们来看看更为复杂的查询和迭代以及更新。

javaee

python

web

ui

cloud

test

c

netmarket

pm

Linux

movies

robot

uids

北京校区

    14天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    8天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    0天免费试学

    基础班入门课程限时免费

    申请试学名额

    12天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    10天免费试学

    基础班入门课程限时免费

    申请试学名额