java數據結構-雙鏈表的刪除與更新

# 數據結構-雙鏈表的復雜刪除以及更新查詢

## 概述

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

## 雙鏈表介紹

? 雙向鏈表也叫[雙鏈表](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.鏈表只有一個節(jié)點

? 2.刪除的數據為頭節(jié)點

? 3.刪除的數據為尾節(jié)點

? 4.刪除的數據為中間節(jié)點

### 分析

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

### 定義刪除方法

```java

/**

* 刪除數據

* @param data

*/

public void remove(Object data){

//1.先根據數據data查找是否有該節(jié)點

Node node = findNodeByData(data);

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

if(node!=null){

removeNode(node);

}

}

```

### 根據數據查詢節(jié)點對象

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

```java

/**

* 根據數據查詢節(jié)點

* @param data

* @return

*/

private Node findNodeByData(Object data){

//從頭節(jié)點開始遍歷

Node node = head;

while(node!=null){

//如果找到了

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

//如果找到則跳出

break;

}else {

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

node = node.next;

}

}

return node;

}

```

### 刪除查詢到的節(jié)點對象

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

```java

/**

* 刪除節(jié)點

* @param node

*/

private void removeNode(Node node) {

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

//1.刪除只有一個節(jié)點

head=null;

rear=null;

}else if(head==node) {

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

//代碼順序不能換

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

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

}else if(rear==node) {

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

//代碼的順序不能換

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

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

}else {

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

node.prev.next=node.next;

node.next.prev=node.prev;

}

}

```

### 刪除過程解析

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

只有一個節(jié)點，直接刪除所有即可。


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


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


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


### 整體代碼

```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;//記錄當前節(jié)點的上一個節(jié)點的內存地址

Node next;//記錄當前節(jié)點的下一個節(jié)點的內存地址

Object data;//當前節(jié)點的數據

}

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

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

/**

* 刪除數據

* @param data

*/

public void remove(Object data){

//1.先根據數據data查找是否有該節(jié)點

Node node = findNodeByData(data);

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

if(node!=null){

removeNode(node);

}

}

/**

* 刪除節(jié)點

* @param node

*/

private void removeNode(Node node) {

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

//1.刪除只有一個節(jié)點

head=null;

rear=null;

}else if(head==node) {

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

//代碼順序不能換

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

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

}else if(rear==node) {

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

//代碼的順序不能換

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

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

}else {

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

node.prev.next=node.next;

node.next.prev=node.prev;

}

}

/**

* 根據數據查詢節(jié)點

* @param data

* @return

*/

private Node findNodeByData(Object data){

//從頭節(jié)點開始遍歷

Node node = head;

while(node!=null){

//如果找到了

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

//如果找到則跳出

break;

}else {

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

node = node.next;

}

}

return node;

}

/**

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

* @param data

*/

public void addFromRear(Object data){

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

Node node = new Node();

// 2. 把數據放入節(jié)點中

node.data = data;

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

if (rear == null) {

rear = node;

head = node;

} else {

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

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

rear.next = node;

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

node.prev = rear;

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

rear = node;

}

}

//[a,b,c]

@Override

public String toString() {

StringBuilder sbBuilder = new StringBuilder("[");

// 遍歷鏈表中所有的數據

Node node = head;// 從頭節(jié)點開始遍歷數據

while (node != null) {

//如果node還沒遍歷到尾部節(jié)點

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的垃圾回收機制來回收對象即可。今天先到這，下一章我們來看看更為復雜的查詢和迭代以及更新。