线性表——★（双向）链表

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

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

1、双向链表（DoubleLinkedList）

与单向链表相比，双向链表具有以下特点：

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

2、双向链表的设计

（1）类的结构设计

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

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

• 链表存放元素的数量。

  private int size; 

  size = 元素（Element）数目 = 节点（Node）数目。

• 第一个节点的引用。

  private Node<E> first; 

  first指向链表的第一个（头）节点。

• 最后一个节点的引用。

  private Node<E> last;

  last指向链表的最后一个（尾）节点。

• 内部静态节点（Node）类。

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

  • 上一个节点的引用

    Node<E> prev;

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

  • 该节点内部的泛型元素

    E element;

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

  • 下一个节点的引用

    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文件：

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文件：

/*
 * 元素的数量
 * @param
 * @return 
 * */
public int size() {
	return size;	//直接返程size成员变量即可
}

（3）实现isEmpty()接口

DoubleLinkedList.java文件：

/*
 * 是否为空
 * @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文件：

/*
 * 获取索引为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的元素，只需：

a.首先从链表中获取索引为index的节点对象；

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

DoubleLinkedList.java文件：

/*
 * 获取index位置对应的元素
 * @param: index
 * @return 
 * */
public E get(int index) {
	return node(index).element;
}

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

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

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

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

DoubleLinkedList.java文件：

/*
 * 设置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文件：

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文件：

/*
 * 是否包含某元素
 * @param: element
 * @return 
 * */
public boolean contains(E element) {
	return indexOf(element) != ELEMENT_NOT_FOUND;
}

（8）实现clear()接口

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

DoubleLinkedList.java文件：

/*
 * 清除所有元素
 * @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)接口

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

①找到被删除节点；

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

③让前一节点的next直接指向后一节点，让后一节点的prev直接指向前一节点；

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

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

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

• 删除一般节点：

  

• 删除头节点（index=0）：

  

• 删除尾节点（index=size）：

  

• 当size=1时：

  

  当删除双向链表中唯一存在的元素时，直接让first和last都指向空（null）即可。

DoubleLinkedList.java文件：

/*
 * 删除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处添加新元素只需：

①创建一个新节点；

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

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

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

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

• 添加一般节点：

  

• 添加头节点（index=0）：

  

• 添加尾节点（index=size）：

  

• 当size=0时：

  

DoubleLinkedList.java文件：

/*
 * 在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文件：

/*
 * 添加元素到尾部
 * @param: element
 * @return 
 * */
public void add(E element) {
	add(size,element);
}

（12）打印链表中的所有元素

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

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

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

DoubleLinkedList.java文件：

/*
 * 打印链表中的所有元素：重载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、接口测试

双向链表同样要注意边界测试，如：当index为0、size - 1、size时的情况。

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

Main.java文件：

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`平均为：$\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`平均为：$\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/ 发布。