java數(shù)據(jù)結(jié)構(gòu)-雙鏈表的刪除與更新

# 數(shù)據(jù)結(jié)構(gòu)-雙鏈表的復(fù)雜刪除以及更新查詢

## 概述

? 上一章中，我們已經(jīng)實(shí)現(xiàn)了雙鏈表的簡(jiǎn)單從尾部刪除節(jié)點(diǎn)，那么在實(shí)際的容器刪除節(jié)點(diǎn)時(shí)應(yīng)該可以發(fā)現(xiàn)，需求不僅僅只是從尾部刪除，可能直接刪除的就是數(shù)據(jù)，那么此時(shí)數(shù)據(jù)在哪呢?如何刪除呢?刪除了節(jié)點(diǎn)，鏈表如何連接呢?接下來(lái)，咱們來(lái)看看如何去做。

## 雙鏈表介紹

? 雙向鏈表也叫[雙鏈表](https://baike.baidu.com/item/%E5%8F%8C%E9%93%BE%E8%A1%A8)，是鏈表的一種，它的每個(gè)數(shù)據(jù)結(jié)點(diǎn)中都有兩個(gè)[指針](https://baike.baidu.com/item/%E6%8C%87%E9%92%88)，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個(gè)結(jié)點(diǎn)開(kāi)始，都可以很方便地訪問(wèn)它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。


## 刪除數(shù)據(jù)

刪除數(shù)據(jù)的情況有4種：

? 1.鏈表只有一個(gè)節(jié)點(diǎn)

? 2.刪除的數(shù)據(jù)為頭節(jié)點(diǎn)

? 3.刪除的數(shù)據(jù)為尾節(jié)點(diǎn)

? 4.刪除的數(shù)據(jù)為中間節(jié)點(diǎn)

### 分析

? 在刪除時(shí)，先判斷要?jiǎng)h除的數(shù)據(jù)是否存在，如果存在再刪除，刪除時(shí)找到節(jié)點(diǎn)，并判斷為上邊的 情況中的哪一種情況即可。

### 定義刪除方法

```java

/**

* 刪除數(shù)據(jù)

* @param data

*/

public void remove(Object data){

//1.先根據(jù)數(shù)據(jù)data查找是否有該節(jié)點(diǎn)

Node node = findNodeByData(data);

//2.判斷是否有節(jié)點(diǎn)，如果有 則刪除，否則 忽略

if(node!=null){

removeNode(node);

}

}

```

### 根據(jù)數(shù)據(jù)查詢節(jié)點(diǎn)對(duì)象

? 根據(jù)數(shù)據(jù)data 查詢節(jié)點(diǎn)，如上代碼中的findNodeByData(data)方法。

```java

/**

* 根據(jù)數(shù)據(jù)查詢節(jié)點(diǎn)

* @param data

* @return

*/

private Node findNodeByData(Object data){

//從頭節(jié)點(diǎn)開(kāi)始遍歷

Node node = head;

while(node!=null){

//如果找到了

if(node.data.equals(data) && node.data.hashCode()==data.hashCode()){

//如果找到則跳出

break;

}else {

//如果沒(méi)找到 繼續(xù)往下找，將Node的引用指向下一個(gè)節(jié)點(diǎn)

node = node.next;

}

}

return node;

}

```

### 刪除查詢到的節(jié)點(diǎn)對(duì)象

? 依次判斷刪除的為哪一種情況，并刪除值。以下代碼為方法：removeNode(node);的具體實(shí)現(xiàn)

```java

/**

* 刪除節(jié)點(diǎn)

* @param node

*/

private void removeNode(Node node) {

if(head==node && rear==node) {

//1.刪除只有一個(gè)節(jié)點(diǎn)

head=null;

rear=null;

}else if(head==node) {

//2.刪除的是頭節(jié)點(diǎn) 后面一定有節(jié)點(diǎn)

//代碼順序不能換

head=head.next;//將頭結(jié)點(diǎn)的引用指向原頭節(jié)點(diǎn)的下一個(gè)。

head.prev=null;//頭節(jié)點(diǎn)的prev為Null即可

}else if(rear==node) {

//3.刪除的是尾節(jié)點(diǎn) 前面一定有節(jié)點(diǎn)

//代碼的順序不能換

rear=rear.prev;//將尾節(jié)點(diǎn)的引用指向原尾節(jié)點(diǎn)的上一個(gè)

rear.next=null;//將尾節(jié)點(diǎn)的next 賦值為null即可

}else {

//4.刪除的是中間節(jié)點(diǎn) 前后都要有節(jié)點(diǎn)

node.prev.next=node.next;

node.next.prev=node.prev;

}

}

```

### 刪除過(guò)程解析

1.第一步中，刪除的是只有一個(gè)節(jié)點(diǎn)，過(guò)程如下圖所示：

只有一個(gè)節(jié)點(diǎn)，直接刪除所有即可。


2.第二步中，刪除的數(shù)據(jù)為頭節(jié)點(diǎn)，如下圖所示：


3.第三步中，刪除的數(shù)據(jù)為尾節(jié)點(diǎn)，如下圖所示：


4.第四步中，刪除的數(shù)據(jù)為中間節(jié)點(diǎn)，如下圖所示：


### 整體代碼

```java

package com.itheima;

/**

* @author 三國(guó)的包子

* @version 1.0

* @description 描述

* @title 標(biāo)題

* @date 2018/7/10

* @package com.itheima

*/

public class DoubleLink {

private class Node{

Node prev;//記錄當(dāng)前節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)的內(nèi)存地址

Node next;//記錄當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的內(nèi)存地址

Object data;//當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)

}

private Node head;//頭節(jié)點(diǎn)

private Node rear;//尾節(jié)點(diǎn)

/**

* 刪除數(shù)據(jù)

* @param data

*/

public void remove(Object data){

//1.先根據(jù)數(shù)據(jù)data查找是否有該節(jié)點(diǎn)

Node node = findNodeByData(data);

//2.判斷是否有節(jié)點(diǎn)，如果有 則刪除，否則 忽略

if(node!=null){

removeNode(node);

}

}

/**

* 刪除節(jié)點(diǎn)

* @param node

*/

private void removeNode(Node node) {

if(head==node && rear==node) {

//1.刪除只有一個(gè)節(jié)點(diǎn)

head=null;

rear=null;

}else if(head==node) {

//2.刪除的是頭節(jié)點(diǎn) 后面一定有節(jié)點(diǎn)

//代碼順序不能換

head=head.next;//將頭結(jié)點(diǎn)的引用指向原頭節(jié)點(diǎn)的下一個(gè)。

head.prev=null;//頭節(jié)點(diǎn)的prev為Null即可

}else if(rear==node) {

//3.刪除的是尾節(jié)點(diǎn) 前面一定有節(jié)點(diǎn)

//代碼的順序不能換

rear=rear.prev;//將尾節(jié)點(diǎn)的引用指向原尾節(jié)點(diǎn)的上一個(gè)

rear.next=null;//將尾節(jié)點(diǎn)的next 賦值為null即可

}else {

//4.刪除的是中間節(jié)點(diǎn) 前后都要有節(jié)點(diǎn)

node.prev.next=node.next;

node.next.prev=node.prev;

}

}

/**

* 根據(jù)數(shù)據(jù)查詢節(jié)點(diǎn)

* @param data

* @return

*/

private Node findNodeByData(Object data){

//從頭節(jié)點(diǎn)開(kāi)始遍歷

Node node = head;

while(node!=null){

//如果找到了

if(node.data.equals(data) && node.data.hashCode()==data.hashCode()){

//如果找到則跳出

break;

}else {

//如果沒(méi)找到 繼續(xù)往下找，將Node的引用指向下一個(gè)節(jié)點(diǎn)

node = node.next;

}

}

return node;

}

/**

* 從尾部添加節(jié)點(diǎn)

* @param data

*/

public void addFromRear(Object data){

// 1. 創(chuàng)建新的節(jié)點(diǎn)

Node node = new Node();

// 2. 把數(shù)據(jù)放入節(jié)點(diǎn)中

node.data = data;

// 3. 判斷尾部節(jié)點(diǎn)是否為空 如果為空說(shuō)明鏈表還是空的

if (rear == null) {

rear = node;

head = node;

} else {

// 4. 判斷如果尾部節(jié)點(diǎn)不為空，說(shuō)明 鏈表是存在的

//將新增的節(jié)點(diǎn)的內(nèi)存地址付給 原尾節(jié)點(diǎn)的的next 屬性

rear.next = node;

//將原尾節(jié)點(diǎn)的地址 付給 新增節(jié)點(diǎn)的 prev 屬性

node.prev = rear;

//最后 將新增的節(jié)點(diǎn) 付給尾節(jié)點(diǎn)引用

rear = node;

}

}

//[a,b,c]

@Override

public String toString() {

StringBuilder sbBuilder = new StringBuilder("[");

// 遍歷鏈表中所有的數(shù)據(jù)

Node node = head;// 從頭節(jié)點(diǎn)開(kāi)始遍歷數(shù)據(jù)

while (node != null) {

//如果node還沒(méi)遍歷到尾部節(jié)點(diǎn)

if (node != rear) {

//就有逗號(hào)

sbBuilder.append(node.data + ", ");

} else {

sbBuilder.append(node.data);

}

// 條件的改變

node = node.next;

}

sbBuilder.append("]");

return sbBuilder.toString();

}

}

```

### 測(cè)試

? 

## 更新數(shù)據(jù)

```java

/***

* 更新數(shù)據(jù)

* @param oldData 傳遞舊數(shù)據(jù)

* @param newData 傳遞新數(shù)據(jù)

*/

public void update(Object oldData ,Object newData){

Node nodeByData = findNodeByData(oldData);

if(nodeByData!=null){

nodeByData.data = newData;

}

}

```

## 總結(jié)

? 雙鏈表的刪除，主要分幾種情況來(lái)刪除即可，另外注意的是，在java中鏈表中刪除對(duì)象，只需要將指向該對(duì)象的引用刪除即可，剩下的由java的垃圾回收機(jī)制來(lái)回收對(duì)象即可。今天先到這，下一章我們來(lái)看看更為復(fù)雜的查詢和迭代以及更新。