java數據結構-雙鏈表的數據操作及特性

# 數據結構-雙鏈表的數據操作及特性

## 概述

? 上一章中，我們已經入門了單鏈表的添加數據，刪除數據及更新數據，但是在刪除的時候，或者在更新的時候，它的效率不高因為，沒一個節(jié)點只記錄了它的下一個節(jié)點，這樣一來，遍歷節(jié)點就變得很慢，添加時，添加到指定的節(jié)點就變得效率低下。那么怎么解決呢?這一章，我們來看看雙鏈表是如何操作的，以及如何遍歷和快速的添加節(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)，分別指向直接后繼和直接前驅。所以，從雙向鏈表中的任意一個結點開始，都可以很方便地訪問它的前驅結點和后繼結點。


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

```java

/**

* 雙鏈表

* @title DoubleLink.java

*

description

*

company: www.itheima.com

* @author 三國的包子

* @version 1.0

*

*/

public class DoubleLink {

//節(jié)點對象

private class Node{

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

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

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

}

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

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

}

```

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

##### 分析

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

添加的過程：

? 1.創(chuàng)建數據節(jié)點

? 2.將數據放入節(jié)點中

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

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

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

```java

/**

* 從尾部添加節(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;

}

}

```

##### 代碼實現的過程如下


## 重寫toString

### 分析

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

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

### 實現

?

```java

//[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);

}

// 條件的改變:將下一個節(jié)點賦值給當前node 引用。直到node.next=null 說明已經到尾部節(jié)點

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é)點，我們發(fā)現，雙向鏈表是 有一個前驅 和 后繼節(jié)點指針。這樣就可以從任意的節(jié)點處添加節(jié)點了。只需要改變prev next 即可。下一章節(jié)，我們來討論如何從中間位置添加節(jié)點以及從頭部添加節(jié)點。這樣大家就可以很好對比單鏈表了。今天先入門到這里。