java數(shù)據(jù)結(jié)構(gòu)-雙鏈表的數(shù)據(jù)操作及特性

# 數(shù)據(jù)結(jié)構(gòu)-雙鏈表的數(shù)據(jù)操作及特性

## 概述

? 上一章中，我們已經(jīng)入門了單鏈表的添加數(shù)據(jù)，刪除數(shù)據(jù)及更新數(shù)據(jù)，但是在刪除的時(shí)候，或者在更新的時(shí)候，它的效率不高因?yàn)?，沒一個(gè)節(jié)點(diǎn)只記錄了它的下一個(gè)節(jié)點(diǎn)，這樣一來，遍歷節(jié)點(diǎn)就變得很慢，添加時(shí)，添加到指定的節(jié)點(diǎn)就變得效率低下。那么怎么解決呢?這一章，我們來看看雙鏈表是如何操作的，以及如何遍歷和快速的添加節(jié)點(diǎn)的。

## 雙鏈表介紹

? 雙向鏈表也叫[雙鏈表](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)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。


## 定義節(jié)點(diǎn)及鏈表對象

```java

/**

* 雙鏈表

* @title DoubleLink.java

*

description

*

company: www.itheima.com

* @author 三國的包子

* @version 1.0

*

*/

public class DoubleLink {

//節(jié)點(diǎn)對象

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)

}

```

#### 從尾部添加節(jié)點(diǎn)到鏈表

##### 分析

從尾部添加節(jié)點(diǎn)，首先在鏈表中，有一個(gè)head 指向頭節(jié)點(diǎn) 有一個(gè)rear指向尾部節(jié)點(diǎn)，并且如果只有一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)既是頭節(jié)點(diǎn)也是尾節(jié)點(diǎn)，如果有多個(gè)節(jié)點(diǎn)，那么根據(jù)節(jié)點(diǎn)的增加，尾部節(jié)點(diǎn)(rear)指向的節(jié)點(diǎn)不同。

添加的過程：

? 1.創(chuàng)建數(shù)據(jù)節(jié)點(diǎn)

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

? 3.判斷尾部節(jié)點(diǎn)是否為空，如果為空，說明鏈表還是空的，此時(shí) 新增節(jié)點(diǎn)即為頭節(jié)點(diǎn)和尾節(jié)點(diǎn)

? 4.如果尾部節(jié)點(diǎn)不為空，鏈表存在，需要將新增的節(jié)點(diǎn)加入到列表中(即原尾部節(jié)點(diǎn)的后面)，并移動(dòng)rear 執(zhí)行新增的節(jié)點(diǎn)。

##### 編寫添加的代碼

```java

/**

* 從尾部添加節(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)是否為空 如果為空說明鏈表還是空的

if (rear == null) {

rear = node;

head = node;

} else {

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

//將新增的節(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;

}

}

```

##### 代碼實(shí)現(xiàn)的過程如下


## 重寫toString

### 分析

? 添加完成節(jié)點(diǎn)之后，需要遍歷節(jié)點(diǎn)打印 查看鏈表的內(nèi)容。所以這里我們重寫toString方法。

重寫toString ，需要在鏈表中從頭節(jié)點(diǎn)開始遍歷，遍歷到尾部節(jié)點(diǎn)之后將每一個(gè)節(jié)點(diǎn)的數(shù)據(jù)連接起來。這里我們實(shí)現(xiàn)一個(gè)字符串連接。

### 實(shí)現(xiàn)

?

```java

//[a,b,c]

@Override

public String toString() {

StringBuilder sbBuilder = new StringBuilder("[");

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

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

while (node != null) {

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

if (node != rear) {

//就有逗號

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

} else {

sbBuilder.append(node.data);

}

// 條件的改變:將下一個(gè)節(jié)點(diǎn)賦值給當(dāng)前node 引用。直到node.next=null 說明已經(jīng)到尾部節(jié)點(diǎn)

node = node.next;

}

sbBuilder.append("]");

return sbBuilder.toString();

}

```

## 測試

```java

package com.itheima.link;

public class TestDoubleLink {

public static void main(String[] args) {

DoubleLink doubleLink = new DoubleLink();

doubleLink.addFromRear("abc1");

doubleLink.addFromRear("abc2");

doubleLink.addFromRear("abc3");

System.out.println(doubleLink);

}

}

```

測試效果：

```java

[abc1, abc2, abc3]

```

## 總結(jié)

? 通過添加節(jié)點(diǎn)，我們發(fā)現(xiàn)，雙向鏈表是 有一個(gè)前驅(qū) 和 后繼節(jié)點(diǎn)指針。這樣就可以從任意的節(jié)點(diǎn)處添加節(jié)點(diǎn)了。只需要改變prev next 即可。下一章節(jié)，我們來討論如何從中間位置添加節(jié)點(diǎn)以及從頭部添加節(jié)點(diǎn)。這樣大家就可以很好對比單鏈表了。今天先入門到這里。