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

javaee

python

web

ui

cloud

test

c

netmarket

pm

Linux

movies

robot

uids

北京校区

    14天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    15天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    8天免费试学

    基础班入门课程限时免费

    申请试学名额

    20天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    0天免费试学

    基础班入门课程限时免费

    申请试学名额

    12天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    5天免费试学

    基础班入门课程限时免费

    申请试学名额

    10天免费试学

    基础班入门课程限时免费

    申请试学名额