由于单向链表永远只能从头节点开始搜索,而双向链表既可以从前向后搜索又可以从后向前搜索。因此,使用双向链表可以提升链表的综合性能。

**注:**Java自带的java.util.LinkedList类就是一个双向链表。

1、双向链表(DoubleLinkedList)

与单向链表相比,双向链表具有以下特点:

  • 双向链表类的成员既有指向头节点的指针first,也有一个指向尾节点的指针last
  • 双向链表的每个节点既包含一个指向下一节点的指针next,又包含一个指向上一节点的prev指针。
双向链表

2、双向链表的设计

(1)类的结构设计

在编程之前,我们需要先对双向链表类(DoubleLinkedList)的结构进行设计。

双向链表类需要的成员主要包括:

  • 链表存放元素的数量。

    1
    private int size; 

    size = 元素(Element)数目 = 节点(Node)数目。

  • 第一个节点的引用。

    1
    private Node<E> first; 

    first指向链表的第一个(头)节点。

  • 最后一个节点的引用。

    1
    private Node<E> last;

    last指向链表的最后一个(尾)节点。

  • 内部静态节点(Node)类。

    由于该节点类仅供链表类使用,因此,需将该节点类定义为链表类的内部类。该类的成员包括:

    • 上一个节点的引用

      1
      Node<E> prev;

      prev指向链表的上一个节点。

    • 该节点内部的泛型元素

      1
      E element;

      泛型元素既可以是基本数据类型,也可以是类的对象。

    • 下一个节点的引用

      1
      Node<E> next;

    next指向链表的下一个节点。

    • 构造函数

    • 析构函数(Java语言没有)

​ **注:**内部类的成员可以不写访问权限。

(2)接口设计

双向链表的接口和单向链表类似。主要包括:

  • int size(); //元素的数量
  • boolean isEmpty(); //是否为空
  • boolean contains(E element); //是否包含某元素
  • E get(int index); //获取index位置对应的元素
  • E set(int index, E element); //设置index位置的元素(覆盖)
  • void add(E element); //添加元素到尾部
  • void add(int index, E element); //在index位置添加元素
  • E remove(int index); //删除index位置对应的元素
  • int indexOf(E element); //查看元素的位置
  • void clear(); //清除所有元素

**注:**接口是供别人在外部通过对象调用的,所以要设计成公有(public)成员。

3、双向链表的实现

3.1、编程实现

在单向链表项目的基础上:

①再新建一个名称为DoubleLinkedList(包名为:com.atangbiji)的类,用来自己实现双向链表;

②仍然使用名称为Main(包名为:com.atangbiji)的类,来调用(测试)自己封装的双向链表。

双向链表封装测试类

③接口实现,我们这里直接考虑链表元素均为泛型的情况。

(1)定义私有成员变量和内部静态节点(Node)类

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package com.atangbiji;

public class DoubleLinkedList<E> {
private int size; //链表存放元素的数量
private Node<E> first; //第一个结点的引用
private Node<E> last; //最后一个结点的引用

//内部静态结点类
private static class Node<E> {
Node<E> prev; //上一个结点的引用
E element; //该结点内部的泛型元素
Node<E> next; //下一个结点的引用

//构造函数
public Node(Node<E> prev, E element, Node<E> next) {
this.prev = prev;
this.element = element;
this.next = next;
}
}
}

(2)实现size()接口

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
/*
* 元素的数量
* @param
* @return
* */
public int size() {
return size; //直接返程size成员变量即可
}

(3)实现isEmpty()接口

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
/*
* 是否为空
* @param
* @return
* */
public boolean isEmpty() {
return size == 0; //size为0为空,否则不为空
}

(4)实现get(int index)接口

  • 获取索引为index的节点对象

为了方便获取任意节点,我们定义一个私有方法Node用来获取索引为index的节点。当index<size/2时,从前向后找;当index>=size/2时,从后向前找。

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/*
* 获取索引为index的结点对象
* @param: index
* @return:索引为index的结点对象
* */
private Node<E> node(int index) {
//判断索引是否越界
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("索引出错,Index = " + index +"; Size =" + size); //抛出异常
}

if (index < (size >> 1)) {
//当index < size/2时,从前向后找到第index个结点
Node<E> node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}else {
//当index >= size/2时,从后向前找到第index个结点
Node<E> node = last;
for (int i = size - 1; i > index; i--) {
node = node.prev;
}
return node;
}
}
  • 获取节点元素

获取链表索引为index的元素,只需:

1
2
3
a.首先从链表中获取索引为index的节点对象;

b.再从该节点对象中获取其中的元素即可。

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
/*
* 获取index位置对应的元素
* @param: index
* @return
* */
public E get(int index) {
return node(index).element;
}

(5)实现set(int index, E element)接口

类似地,设置链表索引为index的元素,只需:

1
2
3
a.首先从链表中获取索引为index的节点对象;

b.再设置该节点对象中的元素即可。

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
* 设置index位置的元素(覆盖)
* @param: index
* @param: element
* @return: 原来的元素
* */
public E set(int index, E element) {
//从链表中获取索引为index的节点对象
Node<E> node = node(index);
E old = node.element;
//设置该节点对象中的元素
node.element = element;

return old;
}

(6)实现indexOf(E element)接口

只需遍历链表中的元素,判断链表中是否存在该元素即可。若存在,返回索引。若不存在,返回-1。

双向链表的indexOf(E element)接口与动态数组的indexOf(E element)接口类似,这里不再赘述。

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private static final int ELEMENT_NOT_FOUND = -1; //未找到
/*
* 查看元素的位置
* @param: element
* @return: 元素的位置
* */
public int indexOf(E element) {
//若元素为空(null)
if (element == null) {
//遍历链表
Node<E> node = first;
for (int i = 0; i < size; i++) {
// node.element可以是null,也可以不是null。
if (node.element == null) {
return i;
}
node = node.next;
}
}else {
//若元素不为空(null)。
//遍历链表
Node<E> node = first;
for (int i = 0; i < size; i++) {
// node.element可以是null,也可以不是null。
if(element.equals(node.element))
{
return i;
}
node = node.next;
}
}
return ELEMENT_NOT_FOUND;
}

(7)实现contains(E element)接口

在链表中查找该元素,若返回不为-1,则说明该元素存在。

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
/*
* 是否包含某元素
* @param: element
* @return
* */
public boolean contains(E element) {
return indexOf(element) != ELEMENT_NOT_FOUND;
}

(8)实现clear()接口

清空链表只需将所有节点的内存释放,同时将size置为0即可。

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
9
10
11
/*
* 清除所有元素
* @param
* @return
* */
public void clear() {
//将第一个结点和最后一个结点的引用设为空(null),即可实现所有结点的内存释放。
first = null;
last = null;
size = 0;
}

:将第一个节点和最后一个结点的引用设为空(null)后,虽然各节点还在被循环引用。但JVM的内存处理机制是:没有被“GC Root对象”引用的对象就会被当做垃圾清除

GC Root对象主要包括:被栈指针(局部变量)指向的对象等多种对象。当我们在调用接口时,我们所使用的DoubleLinkedList对象就是一种GC Root对象。所以,Java中,将第一个节点和最后一个结点的引用设为空(null),即可实现所有节点的内存释放。

**附:**为了证明该方法的确释放了所有节点的内存,我们同样可以在内部静态节点(Node)类中重写Java中自带的finalize()方法进行测试。测试过程与动态数组泛化后的clear()接口测试方法类似,这里不再赘述。

(9)实现remove(int index)接口

删除双向链表某一节点的元素只需:

1
2
3
4
5
6
7
①找到被删除节点;

②获取被删除节点的前一节点和后一节点;

③让前一节点的next直接指向后一节点,让后一节点的prev直接指向前一节点;

④链表存放元素的数量-1。

此时,被删除节点便没有被任何“GC Root对象”引用,进而被当做垃圾清除。

注意分析头节点(index=0)、尾节点(index=size-1)和size=1的情况。

  • 删除一般节点:

    删除一般节点
  • 删除头节点(index=0):

    删除头节点
  • 删除尾节点(index=size):

    删除尾节点
  • size=1时:

    size=1

    当删除双向链表中唯一存在的元素时,直接让firstlast都指向空(null)即可。

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
* 删除index位置对应的元素
* @param: index
* @return: 被删除的元素
* */
public E remove(int index) {

//1、找到被删除节点
Node<E> removeNode = node(index);
//2、获取被删除节点的前一节点和后一节点
Node<E> prevNode = removeNode.prev;
Node<E> nextNode = removeNode.next;
//3、让前一节点的next直接指向后一节点,让后一节点的prev直接指向前一节点
if (1 == size) {
//当删除双向循环链表中唯一存在的元素时
first = null;
last = null;
} else if (0 == index) {
//若删除的是头节点
nextNode.prev = null;
first = nextNode;
}else if ((size - 1) == index) {
//若删除的是尾节点
prevNode.next = null;
last = prevNode;
}else {
//若删除的为中间节点
prevNode.next = nextNode;
nextNode.prev = prevNode;
}

//4、链表存放元素的数量-1
size--;

return removeNode.element;
}

(10)实现add(int index,E element)接口

链表添加新元素不用考虑是否需要扩容的问题。与单向链表一样,双向链表在index处添加新元素只需:

1
2
3
4
5
6
7
①创建一个新节点;

②分别获取新节点的前一节点和后一节点;

③断开index结点与前一结点的连接,并将新节点分别与前一节点和后一节点相连;

④链表存放元素的数量+1。

注意分析头节点(index=0)、尾节点(index=size)和size=0的情况。

  • 添加一般节点:

    添加一般节点
  • 添加头节点(index=0):

    添加头节点
  • 添加尾节点(index=size):

    添加尾节点
  • 当size=0时:

    size=0

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
/*
* 在index位置添加元素
* @param: index
* @param: element
* @return
* */
public void add(int index,E element) {
//判断索引是否越界
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException("索引出错,Index = " + index +"; Size =" + size); //抛出异常
}
if (size == 0) {
//1、创建一个新节点
Node<E> newNode = new Node<E>(null,element,null);

//2、首节点和尾节点均指向新节点
first = newNode;
last = newNode;

} else if (size == index) {
//1、创建一个新节点
Node<E> newNode = new Node<E>(null,element,null);

//2、分别获取新节点的前一节点和后一节点
Node<E> nextNode = null;//获取新节点的后一结点(即:index节点)
Node<E> prevNode = last;//获取新节点的前一结点(即:index结点的前一结点)

//3、再将新结点分别与前一节点和后一节点相连
newNode.next = nextNode;
prevNode.next = newNode;

newNode.prev = prevNode;
last = newNode;

} else if (0 == index) {
//1、创建一个新节点
Node<E> newNode = new Node<E>(null,element,null);

//2、分别获取新节点的前一节点和后一节点
Node<E> nextNode = first;//获取新节点的后一结点(即:index节点)
Node<E> prevNode = null;//获取新节点的前一结点(即:index结点的前一结点)

//3、再将新结点分别与前一节点和后一节点相连
newNode.next = nextNode;
first = newNode;

newNode.prev = prevNode;
nextNode.prev = newNode;

} else {
//1、创建一个新节点
Node<E> newNode = new Node<E>(null,element,null);

//2、分别获取新节点的前一节点和后一节点
Node<E> nextNode = node(index);//获取新节点的后一结点(即:index节点)
Node<E> prevNode = nextNode.prev;//获取新节点的前一结点(即:index结点的前一结点)

//3、再将新结点分别与前一节点和后一节点相连
newNode.next = nextNode;
prevNode.next = newNode;

newNode.prev = prevNode;
nextNode.prev = newNode;
}
//4、链表存放元素的数量+1
size++;
}

(11)实现add(E element)接口

add(E element)接口是add(int index,E element)接口的特例。我们只需在size处添加新元素即可。

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
/*
* 添加元素到尾部
* @param: element
* @return
* */
public void add(E element) {
add(size,element);
}

(12)打印链表中的所有元素

同动态数组一样,为了打印对象链表中的所有元素,我们可以通过重写(也称覆盖)toString()方法,并在其中完成字符串的拼接的方式即可实现。

为了更加直观地展现双向链表,我们在输出各节点元素时打印**“上一节点元素←该节点元素→下一节点元素”**。

注:Java中字符串拼接建议使用StringBuilder类。

DoubleLinkedList.java文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/*
* 打印链表中的所有元素:重载toString()函数
* @param
* @return 链表元素
* */
@Override
public String toString() {
//新建StringBuilder
StringBuilder string = new StringBuilder();

//拼接字符串
string.append("双向链表 size = ").append(size).append("; [");
Node<E> node = first;
for (int i = 0; i < size; i++) {
//若首节点指向null,则只打印本节点;否则输出上一节点
if (node.prev != null) {
string.append(node.prev.element).append("<-");
}

string.append(node.element);

//若尾节点指向null,则只打印本节点;否则输出下一节点
if (node.next != null) {
string.append("->").append(node.next.element);
}

if (i != size - 1) {
string.append(", ");
}

node = node.next;
}
string.append("]");

return string.toString();
}

3.2、接口测试

双向链表同样要注意边界测试,如:当index0size - 1size时的情况。

Main类(Main.java文件)中新建一个DoubleLinkedList对象,用来测试自己封装的双向链表。这里仅以添加和删除元素接口为例进行测试,其它接口的测试方法与此类似,这里不再赘述。

Main.java文件:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package com.atangbiji;

public class Main {
public static void main(String[] args) {
DoubleLinkedList<Integer> linkedList = new DoubleLinkedList <Integer>();

linkedList.add(11);
linkedList.add(22);
linkedList.add(33);
linkedList.add(44);
linkedList.add(linkedList.size() - 1,null);
linkedList.add(55);
linkedList.add(linkedList.size(),66);
linkedList.add(0,0);
linkedList.add(0,null);

System.out.println(linkedList);

linkedList.remove(linkedList.size() - 1);
System.out.println(linkedList);

linkedList.remove(5);
System.out.println(linkedList);

int linkedListSize = linkedList.size();

for (int i = 0; i < linkedListSize; i++) {
linkedList.remove(0);
System.out.println(linkedList);
}

}
}

运行该程序,输出结果为:

测试结果

4、java.util. LinkedList类源码分析

Java自带的java.util.LinkedList类就是一个双向链表。自行分析,这里不再赘述。

5、总结

(1)时间复杂度(双向链表VS单向链表)

  • 粗略对比一下两者删除元素时程序指令的执行次数。

    • 单向链表

      $ 1+2+3+…+n= \frac{(1+n)×n}{2}=\frac{n^2}{2} +\frac{n}{2} ,除以n平均为:,除以`n`平均为:\frac{n}{2} +\frac{1}{2}$ 。

    • 双向链表

      $ (1+2+3+…+\frac{n}{2})×2= \frac{(1+\frac{n}{2})×\frac{n}{2}}{2}×2=\frac{n^2}{4} +\frac{n}{2} ,除以n平均为:,除以`n`平均为:\frac{n}{4} +\frac{1}{2}$ 。

​ 所以,两者的平均时间复杂度均为O(n),但双向链表的程序指令执行次数比单向链表缩减了近一半。

  • 是不是有了双向链表,单向链表就没有用了呢?

​ 并不是,在哈希表的设计中就用到了单向链表。至于原因,会在哈希表中讲解。

(2)性能对比(双向链表VS动态数组)

  • **动态数组:**开辟、销毁内存空间的次数相对较少,但可能造成内存空间的浪费(可以通过缩容来优化)。
  • **双向链表:**开辟、销毁内存空间的次数相对较多,但不会造成内存空间的浪费。

(3)实际开发过程中,如何选择?

  • 如果频繁在尾部进行添加、删除操作,选择动态数组和双向链表均可。此时,两者时间复杂度均为O(1)。
  • 如果频繁在头部进行添加、删除操作,建议使用双向链表。此时,动态数组的时间复杂度为O(n),双向链表的时间复杂度为O(1)。
  • 如果频繁在任意位置进行添加、删除操作,建议使用双向链表。此时,两者的平均时间复杂度均为O(n),但平均下来,双向链表的程序指令执行次数比动态数组缩减了近一半。
  • 如果频繁在**查询(随机访问)**操作,建议使用动态数组。此时,动态数组的时间复杂度为O(1),双向链表的时间复杂度为O(n)。

(本讲完,系列博文持续更新中…… )

参考文献:
[1] 《恋上数据结构与算法》,小码哥MJ

[2] 《数据结构与算法》,邓俊辉

如何获取源代码?

关注 “阿汤笔迹” 微信公众号,在后台回复关键词 “数据结构与算法设计与实现” ,即可获取项目源代码。

阿汤笔迹微信公众平台

原文地址:http://www.atangbiji.com/2023/07/22/DoubleLinkedList/
博主最新文章在个人博客 http://www.atangbiji.com/ 发布。