全国咨询热线:400-618-4000

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

创建时间:2018年12月07日11时35分

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

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

![](image\image1.png)

## 定义节点及链表对象

```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;

}

}

```

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

![](image\image2.png)

## 重写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 即可。下一章节,我们来讨论如何从中间位置添加节点以及从头部添加节点。这样大家就可以很好对比单链表了。今天先入门到这里。