java数据结构-双链表的数据操作及特性

# 数据结构-双链表的数据操作及特性

## 概述

​ 上一章中，我们已经入门了单链表的添加数据，删除数据及更新数据，但是在删除的时候，或者在更新的时候，它的效率不高因为，没一个节点只记录了它的下一个节点，这样一来，遍历节点就变得很慢，添加时，添加到指定的节点就变得效率低下。那么怎么解决呢?这一章，我们来看看双链表是如何操作的，以及如何遍历和快速的添加节点的。

## 双链表介绍

​ 双向链表也叫[双链表](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)，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。


## 定义节点及链表对象

“`java

/**

* 双链表

* @title DoubleLink.java

*

description

*

company: www.itheima.com

* @author 三国的包子

* @version 1.0

*

*/

public class DoubleLink {

//节点对象

private class Node{

Node prev;//记录当前节点的上一个节点的内存地址

Node next;//记录当前节点的下一个节点的内存地址

Object data;//当前节点的数据

}

private Node head;//头节点

private Node rear;//尾节点

}

“`

#### 从尾部添加节点到链表

##### 分析

从尾部添加节点，首先在链表中，有一个head 指向头节点 有一个rear指向尾部节点，并且如果只有一个节点，这个节点既是头节点也是尾节点，如果有多个节点，那么根据节点的增加，尾部节点(rear)指向的节点不同。

添加的过程：

​ 1.创建数据节点

​ 2.将数据放入节点中

​ 3.判断尾部节点是否为空，如果为空，说明链表还是空的，此时 新增节点即为头节点和尾节点

​ 4.如果尾部节点不为空，链表存在，需要将新增的节点加入到列表中(即原尾部节点的后面)，并移动rear 执行新增的节点。

##### 编写添加的代码

“`java

/**

* 从尾部添加节点

* @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;

}

}

“`

##### 代码实现的过程如下


## 重写toString

### 分析

​ 添加完成节点之后，需要遍历节点打印 查看链表的内容。所以这里我们重写toString方法。

重写toString ，需要在链表中从头节点开始遍历，遍历到尾部节点之后将每一个节点的数据连接起来。这里我们实现一个字符串连接。

### 实现

​

“`java

//[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=null 说明已经到尾部节点

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]

“`

## 总结

​ 通过添加节点，我们发现，双向链表是 有一个前驱 和 后继节点指针。这样就可以从任意的节点处添加节点了。只需要改变prev next 即可。下一章节，我们来讨论如何从中间位置添加节点以及从头部添加节点。这样大家就可以很好对比单链表了。今天先入门到这里。