详细分析链表的数据结构的实现过程（Java 实现）
- 2020 年 8 月 31 日
- 筆記
- JAVA, 数据结构, 数据结构(Java 实现), 链表
链表的数据结构的实现过程（Java 实现）
前言
在前面实现的三种线性数据结构：动态数组、栈和队列 虽然对用户而言实现了动态的功能，但在底层上还是依托着静态数组，使用 resize 方法解决固定容量的问题，从根本上来说还不是真正的动态。
而对于链表而言，则是真正的动态数据结构。
因为链表的实现是将一个个节点靠地址的指向将这些节点挂接起来而组成的。
简单来说，每一次在链表上添加新数据就是在一个已有节点的指针域上指定它的下一个节点的地址为存放新数据的节点的地址。这样子，不论是从底层上还是用户的角度上，都不用担心容量的问题，所以链表是真正的动态数据结构。
同样，链表也是一个很重要的数据结构。对于链表而言，它是最简单的动态数据结构，可以帮助我们更深入地理解引用（指针）、更深入地理解递归以及可以用来辅助组成其他的数据结构。
基本概念
链表的基本结构
对链表而言，数据是存储在“节点”（Node）中的，可以使用一个数据域来存储数据，这里我称为 element；然后节点中还有一个用来指向下一个节点位置的节点域，一般称为 next。而对于链表的结尾，一般是以 NULL 作为结尾，所以链表中的最后一个节点的节点域 next 指向的是 NULL。
图示如下:
所以可以先暂时设计链表的基本结构代码如下：
/**
* 链表类
* 支持泛型
*
* @author 踏雪彡寻梅
* @date 2020-02-03 - 21:08
*/
public class LinkedList<E> {
/**
* 链表的节点
* 对于用户而言，不需要知道链表的底层结构是怎样的，只需要知道链表是一种线性数据结构，可以增删改查数据
*/
private class Node {
/**
* 节点存储的数据
*/
public E element;
/**
* 用于指向下一个节点,使节点与节点之间挂接起来组成链表
*/
public Node next;
/**
* 构造函数
* 构造一个存有数据并指向了下一个节点的节点
*
* @param element 存往该节点中的数据
* @param next 该节点的下一个节点
*/
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
/**
* 构造函数
* 构造一个存有数据但没有指向下一个节点的节点
*
* @param element 存往该节点中的数据
*/
public Node(E element) {
this(element, null);
}
/**
* 构造函数
* 构造一个空节点
*/
public Node() {
this(null, null);
}
/**
* 重写 toString 方法以显示节点中存储的数据信息
*
* @return 返回节点中存储的数据信息
*/
@Override
public String toString() {
return element.toString();
}
}
}
从以上设计也可简单的分析链表的优缺点如下：
-
优点：真正的动态结构，不需要处理固定容量的问题。
-
缺点：丧失了随机访问的能力。即不像数组一样可以通过索引快速地获取到数据。
综上，可简单对比数组和链表的使用场景如下：
-
数组最好用于索引有语意的情况，不适合用于索引没有语意的情况。
-
有语意的情况：如一个班级中第二名的分数可这样表示：score[2]。
-
数组也可以没有语意，并不是任何时候索引都是有语意的，不是所有有语意的这样的一个标志就适合做索引，如身份证号：身份证号的保存会存在空间的浪费（有些索引不是身份证号码）。
- 如：身份证号为 41222197801015333 的某个人表示为：person[41222197801015333]
-
最大的优点：支持快速查询。
-
-
相比数组，将一个静态数组改变为一个动态数组，就是在对于不方便使用索引的时候处理有关数据存储的问题，对于这样的存储数据的需求使用链表是更合适的。所以链表不适合用于索引有语意的情况，更适合处理索引没有语意的情况。
- 因为链表最大的优点是动态存储。
另外，对于查看链表中的各个元素，也是需要一一遍历过去的，那么此时就需要一个变量 head 来指向链表头部的位置，以便查看链表信息所用。同时因为有了这个变量 head 来指向链表头的位置，那么往链表头部添加新元素是十分方便的，这和之前实现的数组数据结构在数组尾部添加元素十分方便是同一个道理，数组中有 size 变量指向下一个新元素位置跟踪尾部。
此时链表的结构如下图所示：
此时设计链表基本结构代码如下，其中使用了一个变量 size 来实时记录链表元素的个数以及增加了两个基本方法用于获取链表当前元素个数和判断链表是否为空：
/**
* 链表类
* 支持泛型
*
* @author 踏雪彡寻梅
* @date 2020-02-03 - 21:08
*/
public class LinkedList<E> {
/**
* 链表的节点
* 对于用户而言，不需要知道链表的底层结构是怎样的，只需要知道链表是一种线性数据结构，可以增删改查数据
*/
private class Node {
/**
* 节点存储的数据
*/
public E element;
/**
* 用于指向下一个节点,使节点与节点之间挂接起来组成链表
*/
public Node next;
/**
* 构造函数
* 构造一个存有数据并指向了下一个节点的节点
*
* @param element 存往该节点中的数据
* @param next 该节点的下一个节点
*/
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
/**
* 构造函数
* 构造一个存有数据但没有指向下一个节点的节点
*
* @param element 存往该节点中的数据
*/
public Node(E element) {
this(element, null);
}
/**
* 构造函数
* 构造一个空节点
*/
public Node() {
this(null, null);
}
/**
* 重写 toString 方法以显示节点中存储的数据信息
*
* @return 返回节点中存储的数据信息
*/
@Override
public String toString() {
return element.toString();
}
}
/**
* 链表的头节点
* 存储第一个元素的节点
*/
private Node head;
/**
* 链表当前元素个数
*/
private int size;
/**
* 构造函数
* 构造一个空链表
*/
public LinkedList() {
head = null;
size = 0;
}
/**
* 获取链表中的当前元素个数
*
* @return 返回链表当前元素个数
*/
public int getSize() {
return size;
}
/**
* 判断链表是否为空
*
* @return 链表为空返回 true;否则返回 fasle
*/
public boolean isEmpty() {
return size == 0;
}
}
链表的基本操作的实现
在链表中添加元素
在链表头添加元素
在上文介绍过，在链表头部添加元素是十分方便的，所以先实现这个操作。
对于这个操作，实现的具体步骤如下：
-
创建一个新节点 newNode 存储新元素 newElement，新节点的节点域 next 指向 NULL。
-
将 newNode 的 节点域 next 指向当前链表头 head，使新节点挂接在链表头部。即 newNode.next = head。
-
最后将 head 指向 newNode，使链表头为新增的节点。即 head = newNode。
综上，在链表头添加过程如下图所示：
设计在链表头部添加元素代码如下所示：
/**
* 在链表头添加新的元素 newElement
*
* @param newElement 新元素
*/
public void addFirst(E newElement) {
// 创建一个新节点存储新元素,该节点的 next 指向 NULL
Node newNode = new Node(newElement);
// 使 newNode 的 next 指向链表头
newNode.next = head;
// 将链表头设为链表新添加的新节点
head = newNode;
// 以上三行代码可使用 Node 的另一个构造函数简写为：
// head = new Node(newElement, head);
// 维护 size,链表当前元素个数 + 1
size++;
}
在链表指定位置处添加元素
除了在链表头部添加元素，还可以指定一个位置来进行添加元素。这个操作在链表的操作中不常使用，一般常出现在试题中，这里实现出来用来帮助深入理解链表的思维。
对于这个操作，指定的添加元素位置这里设计为用 index 表示（从 0 开始计数），实现的具体步骤如下：
-
判断指定的添加位置 index 是否为合法值。
-
使用一个节点变量 prev 来找到指定插入位置 index 的前一个节点位置，初始时 prev 指向链表头 head。
-
创建一个新节点 newNode 存储新元素 newElement，新节点的节点域 next 指向 NULL。
-
使用 prev 找到指定位置 index 的前一个位置（index – 1 处，即插入位置的前一个节点）后，将 newNode 的 next 指向 prev 的 next 指向的节点，即将新节点挂接在插入位置的原节点前面。（newNode.next = prev.next）
-
将 prev 的 next 指向新节点 newNode，即将链表前后都挂接了起来。此时新节点处于 index 处，而原来处于 index 的节点和之后的节点都往后挪了一个位置。（prev.next = newNode）
对于以上步骤，关键在于找到要添加的节点的前一个节点。
而找到前一个节点这个操作有一个特殊情况，即指定添加位置 index 为 0 的时候，也就是将元素添加到链表头，而链表头是没有前一个节点的（对于链表头没有前一个节点后续会实现一个虚拟头节点放置到链表头的前一个节点，方便链表的操作）。
所以这个操作需要进行特殊处理：
使用一个判断判断 index 是否为 0，如果为 0 使用前面实现的 addFirst(E newElement) 方法将新节点添加到链表头。
综上，在链表指定位置处添加元素过程如下图所示：
需要注意的是 newNode.next = prev.next 和 prev.next = newNode 的顺序不能相反，否则将会出现错误，具体结果图示如下：
设计在链表指定位置处添加元素代码如下所示：
/**
* 在链表的指定位置 index（从 0 开始计数）处添加新元素 newElement
*
* @param index 指定的添加位置,从 0 开始计数
* @param newElement 新元素
*/
public void add(int index, E newElement) {
// 判断 index 是否合法
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Illegal index.");
}
if (index == 0) {
// 如果 index 为 0,使用 addFirst(E newElement) 方法将新元素添加到链表头。
addFirst(newElement);
} else {
// 否则将新元素添加到 index 处
// 找到 index 的前一个节点
Node prev = head;
for (int i = 0; i < index - 1; i++) {
prev = prev.next;
}
// 创建一个新节点存储新元素,该节点的 next 指向 NULL
Node newNode = new Node(newElement);
// 将新节点添加到 index 处
newNode.next = prev.next;
prev.next = newNode;
// 以上三行代码可使用 Node 的另一个构造函数简写为：
// prev.next = new Node(newElement, prev.next);
// 维护 size,链表当前元素个数 + 1
size++;
}
}
由以上实现可复用其实现一个在链表末尾添加新元素的方法 addLast：
/**
* 在链表末尾添加新的元素 newElement
* @param newElement 新元素
*/
public void addLast(E newElement) {
add(size, newElement);
}
链表的虚拟头节点
在上面实现的在链表指定位置处添加元素中，可以发现有一个特殊情况为指定在头部添加元素时，头部元素没有前一个节点，所以需要做一个特殊处理。为了让这个操作统一为每个节点都可以找到前置节点，需要在链表中设置一个虚拟头节点 dummyHead。这个节点这里设计为不存储数据，只用于指向链表中的第一个元素。
添加虚拟头节点后的链表基本结构图示如下：
此时更改链表的实现代码如下：
/**
* 链表类
* 支持泛型
*
* @author 踏雪彡寻梅
* @date 2020-02-03 - 21:08
*/
public class LinkedList<E> {
/**
* 链表的节点
* 对于用户而言，不需要知道链表的底层结构是怎样的，只需要知道链表是一种线性数据结构，可以增删改查数据
*/
private class Node {
/**
* 节点存储的数据
*/
public E element;
/**
* 用于指向下一个节点,使节点与节点之间挂接起来组成链表
*/
public Node next;
/**
* 构造函数
* 构造一个存有数据并指向了下一个节点的节点
*
* @param element 存往该节点中的数据
* @param next 该节点的下一个节点
*/
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
/**
* 构造函数
* 构造一个存有数据但没有指向下一个节点的节点
*
* @param element 存往该节点中的数据
*/
public Node(E element) {
this(element, null);
}
/**
* 构造函数
* 构造一个空节点
*/
public Node() {
this(null, null);
}
/**
* 重写 toString 方法以显示节点中存储的数据信息
*
* @return 返回节点中存储的数据信息
*/
@Override
public String toString() {
return element.toString();
}
}
/**
* 链表的虚拟头节点
* 不存储数据
* next 指向链表中的第一个元素
*/
private Node dummyHead;
/**
* 链表当前元素个数
*/
private int size;
/**
* 构造函数
* 构造一个空链表
*/
public LinkedList() {
// 创建虚拟头节点,存储 null,初始时 next 指向 null
dummyHead = new Node(null, null);
size = 0;
}
/**
* 获取链表中的当前元素个数
*
* @return 返回链表当前元素个数
*/
public int getSize() {
return size;
}
/**
* 判断链表是否为空
*
* @return 链表为空返回 true;否则返回 fasle
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 在链表的指定位置 index（从 0 开始计数）处添加新元素 newElement
*
* @param index 指定的添加位置,从 0 开始计数
* @param newElement 新元素
*/
public void add(int index, E newElement) {
// 判断 index 是否合法
if (index < 0 || index > size) {
throw new IllegalArgumentException("Add failed.Illegal index.");
}
// 将新元素添加到 index 处
// 找到 index 的前一个节点
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// 创建一个新节点存储新元素,该节点的 next 指向 NULL
Node newNode = new Node(newElement);
// 将新节点添加到 index 处
newNode.next = prev.next;
prev.next = newNode;
// 以上三行代码可使用 Node 的另一个构造函数简写为：
// prev.next = new Node(newElement, prev.next);
// 维护 size,链表当前元素个数 + 1
size++;
}
/**
* 在链表头添加新的元素 newElement
*
* @param newElement 新元素
*/
public void addFirst(E newElement) {
add(0, newElement);
}
/**
* 在链表末尾添加新的元素 newElement
*
* @param newElement 新元素
*/
public void addLast(E newElement) {
add(size, newElement);
}
}
此时，在 add 方法的实现中添加新元素的操作就都统一为同一个步骤了，每一个节点都能找到其前置节点。
需要注意的是，和之前 prev 从链表的第一个元素开始遍历寻找更改为了从虚拟头节点开始遍历寻找，所以遍历的终止条件从 i < index – 1 变为了 i < index。为了方便理解这个过程，可以参考以下图示：
-
原实现：
-
现实现：
在更改了 add 方法之后，addFirst 方法也可精简为复用 add 方法就可实现在链表头部添加元素的功能了。这也是使用了虚拟头节点之后带来的便利。
链表的查询和修改操作
查询操作的实现
对于此操作，这里实现两个类型的方法用于查询链表中的元素：
-
get 方法：获得链表中某个位置的元素（位置从 0 开始计数）。该操作在链表中不常使用，可以用来加强链表的理解。具体实现如下：
/** * 获得链表的第 index 个位置的元素 * * @param index 需要获取的元素的位置,从 0 开始计数 * @return 返回链表中的 index 处的元素 */ public E get(int index) { // 判断 index 的合法性 if (index < 0 || index >= size) { throw new IllegalArgumentException("Get failed.Illegal index."); } // 从链表中第一个元素开始遍历,找到处于 index 的节点 Node currentElement = dummyHead.next; for (int i = 0; i < index; i++) { currentElement = currentElement.next; } // 返回处于 index 的元素 return currentElement.element; }-
由以上实现可衍生出两个方法分别用来获取链表中第一个元素和链表中最后一个元素：
/** * 获得链表的第一个元素 * * @return 返回链表的第一个元素 */ public E getFirst() { return get(0); } /** * 获得链表的最后一个元素 * * @return 返回链表的最后一个元素 */ public E getLast() { // index 从 0 开始计数,size 为当前元素个数,所以最后一个元素的位置对应为 size - 1 return get(size - 1); }
-
-
contains 方法：判断用户给定的一个元素是否存在于链表中，存在返回 true，不存在返回 false。具体实现如下：
/** * 查找链表中是否含有元素 element * * @param element 需要查找的元素 * @return 如果包含 element 返回 true;否则返回 false */ public boolean contains(E element) { // 从链表中第一个元素开始遍历,依次判断是否包含有元素 element Node currentElement = dummyHead.next; while (currentElement != null) { if (currentElement.element.equals(element)) { // 相等说明链表中包含元素 element,返回 true return true; } currentElement = currentElement.next; } // 整个链表遍历完还没有找到则返回 false return false; }
修改操作的实现
对于此操作，实现的目的是修改链表中某个位置（位置从 0 开始计数）的元素为指定的新元素。该操作在链表中也不常使用，可以用来加强链表的理解。具体实现如下：
/**
* 修改链表的第 index 个位置的元素为 newElement
*
* @param index 需要修改的元素的位置,从 0 开始计数
* @param newElement 替换老元素的新元素
*/
public void set(int index, E newElement) {
// 判断 index 的合法性
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Set failed.Illegal index.");
}
// 从链表中第一个元素开始遍历,找到处于 index 的节点
Node currentElement = dummyHead.next;
for (int i = 0; i < index; i++) {
currentElement = currentElement.next;
}
// 修改 index 的元素为 newElement
currentElement.element = newElement;
}
链表的删除操作
对于删除操作，目的为删除链表中某个位置的元素并返回删除的元素。该操作在链表中也不常使用，可以用来加强链表的理解。实现的步骤如下：
-
找到待删除节点 delNode 的前置节点 prev。
-
将 prev 的 next 指向待删除节点 dalNode 的 next。即越过了 delNode，和它后面的节点挂接了起来。(prev.next = delNode.next)
-
将 delNode 的 next 指向 null，至此，delNode 和链表脱离关系，从链表中被删除。(delNode.next = null)
-
返回 delNode 中存储的元素 element，即返回删除的元素。
删除过程图示如下：
代码具体实现如下：
/**
* 从链表中删除 index 位置的节点并返回删除的元素
*
* @param index 要删除节点在链表中的位置,从 0 开始计数
* @return 返回删除的元素
*/
public E remove(int index) {
// 判断 index 的合法性
if (index < 0 || index >= size) {
throw new IllegalArgumentException("Remove failed.Illegal index.");
}
// 从虚拟头节点开始遍历找到待删除节点的前置节点
Node prev = dummyHead;
for (int i = 0; i < index; i++) {
prev = prev.next;
}
// 记录待删除节点
Node delNode = prev.next;
// 进行删除操作
prev.next = delNode.next;
delNode.next = null;
// 维护 size,链表当前元素个数 - 1
size--;
// 返回删除的元素
return delNode.element;
}
由以上实现可衍生出两个方法分别用于删除链表中的第一个元素和最后一个元素：
/**
* 从链表中删除第一个元素所在的节点并返回删除的元素
*
* @return 返回删除的元素
*/
public E removeFirst() {
return remove(0);
}
/**
* 从链表中删除最后一个元素所在的节点并返回删除的元素
*
* @return 返回删除的元素
*/
public E removeLast() {
return remove(size - 1);
}
重写 toString 方法显示链表中元素信息
实现到此，已经可以重写 toString 方法显示链表中元素信息来测试以上实现的基本操作了，以此验证设计的逻辑没有出错。
对于此方法，这里设计为下：
/**
* 重写 toString 方法,以便观察链表中的元素
*
* @return 返回当前链表信息
*/
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append(String.format("LinkedList: size = %d, Elements: dummyHead -> ", size));
// 从链表中第一个元素开始遍历,依次将链表中元素信息添加到结果信息中
Node currentElement = dummyHead.next;
while (currentElement != null) {
result.append(currentElement + " -> ");
currentElement = currentElement.next;
}
// 以上遍历的等价写法：
// for (Node currentElement = dummyHead.next; currentElement != null; currentElement = currentElement.next) {
// result.append(currentElement + " -> ");
// }
result.append("NULL");
return result.toString();
}
接着测试以上实现的基本操作，测试代码如下：
/**
* 测试 LinkedList
*/
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<>();
// 测试 isEmpty 方法
System.out.println("==== 测试 isEmpty 方法 ====");
System.out.println("当前链表是否为空: " + linkedList.isEmpty());
// 测试链表的添加操作
System.out.println("\n==== 测试 addFirst 方法 ====");
for (int i = 0; i < 5; i++) {
linkedList.addFirst(i);
System.out.println(linkedList);
}
System.out.println("\n==== 测试 add 方法 ====");
System.out.println("添加 888 到链表中的第 2 个位置(从 0 开始计数): ");
linkedList.add(2, 888);
System.out.println(linkedList);
System.out.println("\n==== 测试 addLast 方法 ====");
linkedList.addLast(999);
System.out.println(linkedList);
// 测试 contains 方法
System.out.println("\n==== 测试 contains 方法 ====");
System.out.println(linkedList);
boolean flag = linkedList.contains(888);
System.out.println("链表中是否存在 888: " + flag);
flag = linkedList.contains(777);
System.out.println("链表中是否存在 777: " + flag);
// 测试 get 方法
System.out.println("\n==== 测试 get 方法 ====");
System.out.println(linkedList);
Integer element = linkedList.getFirst();
System.out.println("链表中的第一个元素为: " + element);
element = linkedList.getLast();
System.out.println("链表中的最后一个元素为: " + element);
element = linkedList.get(3);
System.out.println("链表中的第 3 个位置(从 0 开始计数)的元素为: " + element);
// 测试 isEmpty 方法
System.out.println("\n==== 测试 isEmpty 方法 ====");
System.out.println("当前链表是否为空: " + linkedList.isEmpty());
// 测试 set 方法
System.out.println("\n==== 测试 set 方法 ====");
System.out.println(linkedList);
linkedList.set(3, 12);
System.out.println("更改链表中的第 3 个位置(从 0 开始计数)的元素为 12 后: ");
System.out.println(linkedList);
// 测试链表的删除操作
System.out.println("\n==== 测试 remove 方法 ====");
Integer delElement = linkedList.remove(3);
System.out.println("删除链表中的第 3 个位置(从 0 开始计数)的元素后: ");
System.out.println(linkedList);
System.out.println("删除的元素为: " + delElement);
System.out.println("\n==== 测试 removeFirst 方法 ====");
delElement = linkedList.removeFirst();
System.out.println("删除链表中的第一个元素后: ");
System.out.println(linkedList);
System.out.println("删除的元素为: " + delElement);
System.out.println("\n==== 测试 removeLast 方法 ====");
delElement = linkedList.removeLast();
System.out.println("删除链表中的最后一个元素后: ");
System.out.println(linkedList);
System.out.println("删除的元素为: " + delElement);
}
测试结果:
==== 测试 isEmpty 方法 ====
当前链表是否为空: true
==== 测试 addFirst 方法 ====
LinkedList: size = 1, Elements: dummyHead -> 0 -> NULL
LinkedList: size = 2, Elements: dummyHead -> 1 -> 0 -> NULL
LinkedList: size = 3, Elements: dummyHead -> 2 -> 1 -> 0 -> NULL
LinkedList: size = 4, Elements: dummyHead -> 3 -> 2 -> 1 -> 0 -> NULL
LinkedList: size = 5, Elements: dummyHead -> 4 -> 3 -> 2 -> 1 -> 0 -> NULL
==== 测试 add 方法 ====
添加 888 到链表中的第 2 个位置(从 0 开始计数):
LinkedList: size = 6, Elements: dummyHead -> 4 -> 3 -> 888 -> 2 -> 1 -> 0 -> NULL
==== 测试 addLast 方法 ====
LinkedList: size = 7, Elements: dummyHead -> 4 -> 3 -> 888 -> 2 -> 1 -> 0 -> 999 -> NULL
==== 测试 contains 方法 ====
LinkedList: size = 7, Elements: dummyHead -> 4 -> 3 -> 888 -> 2 -> 1 -> 0 -> 999 -> NULL
链表中是否存在 888: true
链表中是否存在 777: false
==== 测试 get 方法 ====
LinkedList: size = 7, Elements: dummyHead -> 4 -> 3 -> 888 -> 2 -> 1 -> 0 -> 999 -> NULL
链表中的第一个元素为: 4
链表中的最后一个元素为: 999
链表中的第 3 个位置(从 0 开始计数)的元素为: 2
==== 测试 isEmpty 方法 ====
当前链表是否为空: false
==== 测试 set 方法 ====
LinkedList: size = 7, Elements: dummyHead -> 4 -> 3 -> 888 -> 2 -> 1 -> 0 -> 999 -> NULL
更改链表中的第 3 个位置(从 0 开始计数)的元素为 12 后:
LinkedList: size = 7, Elements: dummyHead -> 4 -> 3 -> 888 -> 12 -> 1 -> 0 -> 999 -> NULL
==== 测试 remove 方法 ====
删除链表中的第 3 个位置(从 0 开始计数)的元素后:
LinkedList: size = 6, Elements: dummyHead -> 4 -> 3 -> 888 -> 1 -> 0 -> 999 -> NULL
删除的元素为: 12
==== 测试 removeFirst 方法 ====
删除链表中的第一个元素后:
LinkedList: size = 5, Elements: dummyHead -> 3 -> 888 -> 1 -> 0 -> 999 -> NULL
删除的元素为: 4
==== 测试 removeLast 方法 ====
删除链表中的最后一个元素后:
LinkedList: size = 4, Elements: dummyHead -> 3 -> 888 -> 1 -> 0 -> NULL
删除的元素为: 999
进程已结束，退出代码 0
从结果可以看出以上实现的基本操作没有出现错误，说明了实现的逻辑是正确的，接下来对以上实现的基本操作做一些简单的时间复杂度分析。
链表的时间复杂度简单分析
-
添加操作
-
addLast 方法：对于该方法，每次都要遍历整个链表进行添加，所以该方法的时间复杂度是 O(n) 级别的。
-
addFirst 方法：对于该方法，每次都是在链表头部做操作，所以该方法的时间复杂度是 O(1) 级别的。
-
add 方法：对于该方法，平均来说，每次添加元素需要遍历 n/2 个元素，所以该方法的时间复杂度是 O(n/2) = O(n) 级别的。
-
综上，添加操作的时间复杂度为 O(n)。
-
-
删除操作
-
removeLast 方法：对于该方法，每次都要遍历整个链表进行删除，所以该方法的时间复杂度是 O(n) 级别的。
-
removeFirst 方法：对于该方法，每次都是在链表头部做操作，所以该方法的时间复杂度是 O(1) 级别的。
-
remove 方法：对于该方法，平均来说，每次删除元素需要遍历 n/2 个元素，所以该方法的时间复杂度是 O(n/2) = O(n) 级别的。
-
综上，删除操作的时间复杂度为 O(n)。
-
-
修改操作
-
set 方法：对于该方法，平均来说，每次修改元素需要遍历 n/2 个元素，所以该方法的时间复杂度是 O(n/2) = O(n) 级别的。
-
所以修改操作的时间复杂度也为 O(n)。
-
-
查找操作
-
getLast 方法：对于该方法，每次都要遍历整个链表进行查找，所以该方法的时间复杂度是 O(n) 级别的。
-
getFirst 方法：对于该方法，每次都是在链表头部做操作，所以该方法的时间复杂度是 O(1) 级别的。
-
get 方法：对于该方法，平均来说，每次查找元素需要遍历 n/2 个元素，所以该方法的时间复杂度是 O(n/2) = O(n) 级别的。
-
contains 方法：对于该方法，平均来说，每次查找判断元素是否存在也是需要遍历 n/2 个元素，所以该方法的时间复杂度也是 O(n/2) = O(n) 级别的。
-
综上，查找操作的时间复杂度为 O(n)。
-
-
所以对于链表而言，增删改查的时间复杂度都是 O(n) 级别的。
-
但是如果不对链表中元素进行修改操作，添加和删除操作也只针对链表头进行操作和查找操作也只查链表头的元素的话，此时整体的时间复杂度就是 O(1) 级别的了，又由于链表整体是动态的，不会浪费大量的内存空间，此时具有一定的优势，显而易见满足这些条件的数据结构为栈，此时就可以使用链表来实现栈发挥链表的优势了。当然，对于链表而言，还有一些改进方式使其在一些应用场景具有优势，比如给链表添加尾指针后使用链表来实现队列。
链表的一些改进方式
使用链表实现栈
对于栈这个数据结构，它只针对一端进行操作，即针对栈顶进行操作，是一个后入先出的数据结构。
上文说到如果链表不使用修改操作，只使用添加、删除、查找链表头的操作是满足栈这个数据结构的特点的。所以可以使用链表头作为栈顶，用链表作为栈的底层实现来实现栈这个数据结构，发挥链表的动态优势。最后，再和之前基于动态数组实现的栈进行一些效率上的对比，查看两者的差距。接下来，开始实现使用链表实现栈。
对于使用链表实现栈，将使用一个 LinkedListStack 类实现之前实现数组栈时定义的栈的接口 Stack 来实现栈的一系列的操作。
回顾栈的接口 Stack 的实现如下：
/**
* 定义栈支持的操作的接口
* 支持泛型
*
* @author 踏雪寻梅
* @date 2020/1/8 - 19:20
*/
public interface Stack<E> {
/**
* 获取栈中元素个数
*
* @return 栈中如果有元素,返回栈中当前元素个数;栈中如果没有元素返回 0
*/
int getSize();
/**
* 判断栈是否为空
*
* @return 栈为空,返回 true;栈不为空,返回 false
*/
boolean isEmpty();
/**
* 入栈
* 将元素 element 压入栈顶
*
* @param element 入栈的元素
*/
void push(E element);
/**
* 出栈
* 将当前栈顶元素出栈并返回
*
* @return 返回当前出栈的栈顶元素
*/
E pop();
/**
* 查看当前栈顶元素
*
* @return 返回当前的栈顶元素
*/
E peek();
}
对于 LinkedListStack 类的实现，只需要复用链表类中的方法就可实现栈的这些基本操作了，具体实现如下：
/**
* 基于 LinkedList 实现的链表栈
* 支持泛型
*
* @author 踏雪彡寻梅
* @date 2020/2/5 - 12:22
*/
public class LinkedListStack<E> implements Stack<E> {
/**
* 基于该链表实现栈
*/
private LinkedList<E> linkedList;
/**
* 构造函数
* 构造一个空的链表栈
*/
public LinkedListStack() {
linkedList = new LinkedList<>();
}
@Override
public int getSize() {
return linkedList.getSize();
}
@Override
public boolean isEmpty() {
return linkedList.isEmpty();
}
@Override
public void push(E element) {
linkedList.addFirst(element);
}
@Override
public E pop() {
return linkedList.removeFirst();
}
@Override
public E peek() {
return linkedList.getFirst();
}
/**
* 重写 toString 方法显示链表栈中的各信息
*
* @return 返回链表栈的信息
*/
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append(String.format("LinkedListStack: size = %d, top [ ", getSize()));
for (int i = 0; i < getSize(); i++) {
E e = linkedList.get(i);
result.append(e);
// 如果不是最后一个元素
if (i != getSize() - 1) {
result.append(", ");
}
}
result.append(" ] bottom");
return result.toString();
}
}
接下来，对以上实现做一些测试，检测是否和预期结果不符，测试代码如下：
/**
* 测试 LinkedListStack
*/
public static void main(String[] args) {
LinkedListStack<Integer> stack = new LinkedListStack<>();
// 判断栈是否为空
System.out.println("==== 测试 isEmpty ====");
System.out.println("当前栈是否为空: " + stack.isEmpty());
System.out.println("\n==== 测试链表栈的入栈,入栈 10 次 ====");
for (int i = 0; i < 10; i++) {
// 入栈
stack.push(i);
// 打印入栈过程
System.out.println(stack);
}
System.out.println("\n==== 测试链表栈的出栈,出栈 1 次 ====");
// 进行一次出栈
stack.pop();
// 查看出栈后的状态
System.out.println(stack);
// 查看当前栈顶元素
System.out.println("\n==== 测试链表栈的查看栈顶元素 ====");
Integer topElement = stack.peek();
System.out.println("当前栈顶元素： " + topElement);
// 判断栈是否为空
System.out.println("\n==== 测试 isEmpty ====");
System.out.println("当前栈是否为空: " + stack.isEmpty());
}
测试结果:
==== 测试 isEmpty ====
当前栈是否为空: true
==== 测试链表栈的入栈,入栈 10 次 ====
LinkedListStack: size = 1, top [ 0 ] bottom
LinkedListStack: size = 2, top [ 1, 0 ] bottom
LinkedListStack: size = 3, top [ 2, 1, 0 ] bottom
LinkedListStack: size = 4, top [ 3, 2, 1, 0 ] bottom
LinkedListStack: size = 5, top [ 4, 3, 2, 1, 0 ] bottom
LinkedListStack: size = 6, top [ 5, 4, 3, 2, 1, 0 ] bottom
LinkedListStack: size = 7, top [ 6, 5, 4, 3, 2, 1, 0 ] bottom
LinkedListStack: size = 8, top [ 7, 6, 5, 4, 3, 2, 1, 0 ] bottom
LinkedListStack: size = 9, top [ 8, 7, 6, 5, 4, 3, 2, 1, 0 ] bottom
LinkedListStack: size = 10, top [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ] bottom
==== 测试链表栈的出栈,出栈 1 次 ====
LinkedListStack: size = 9, top [ 8, 7, 6, 5, 4, 3, 2, 1, 0 ] bottom
==== 测试链表栈的查看栈顶元素 ====
当前栈顶元素： 8
==== 测试 isEmpty ====
当前栈是否为空: false
进程已结束，退出代码 0
从结果可以看出，实现的结果和预期是相符的，实现了栈的各个基本操作。整体的时间复杂度前面也分析过了，都是对链表头部进行操作，时间复杂度是 O(1) 级别的，并且拥有了链表的整体动态性。接下来和之前实现的数组栈进行一些效率上的对比：
测试代码:
import java.util.Random;
/**
* 对比数组栈和链表栈的效率差距
*
* @author 踏雪彡寻梅
* @date 2020/2/5 - 12:52
*/
public class Main {
/**
* 测试使用 stack 运行 opCount 个 push 和 pop 操作所需要的时间,单位: 秒
*
* @param stack 测试使用的栈
* @param opCount 测试的数量级
* @return 返回测试的运行时间,单位: 秒
*/
private static double testStack(Stack<Integer> stack, int opCount) {
long startTime = System.nanoTime();
Random random = new Random();
for (int i = 0; i < opCount; i++) {
stack.push(random.nextInt(Integer.MAX_VALUE));
}
for (int i = 0; i < opCount; i++) {
stack.pop();
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 10000;
ArrayStack<Integer> arrayStack = new ArrayStack<>();
double time1 = testStack(arrayStack, opCount);
System.out.println("ArrayStack, time: " + time1 + " s");
LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
double time2 = testStack(linkedListStack, opCount);
System.out.println("LinkedListStack, time: " + time2 + " s");
}
}
测试结果-1（opCount 为 1 万时）
测试结果-2（opCount 为 10 万时）
测试结果-3（opCount 为 100 万时）
测试结果-4（opCount 为 1000 万时）
从这几个测试结果可以看出在我这台机器上当数据量较小时，链表栈耗时比数组栈短，随着数据量增大，数组栈耗时比链表栈短。
但归根结底，这两个栈的入栈和出栈操作的时间复杂度是同一级别 O(1) 的。
这种有时快有时慢的情况主要跟内部实现相关：
-
对于数组栈来说可能时不时需要重新分配数组空间进行扩容或者减容，这一操作会消耗一些时间。
-
对于链表栈来说则是有很多 new 新节点 Node 的操作，这些 new Node 的操作也会消耗一些时间。
所以这两种栈之间的时间对比会出现这种常数倍的差异，属于正常的情况，它们之间没有复杂度上的巨大的差异，总体上的时间复杂度还是同一级别的，具体的时间差异最多也就是几倍的差异，不会产生巨大的差异。
当然，相比数组栈需要时不时重新分配数组空间达到动态伸缩容量的目的，链表栈的动态性将会显得更有优势一些，不需要我们像数组栈一样手动地进行伸缩容量处理。
使用链表实现队列
对于队列这个数据结构，它是针对两端进行操作，即针对队首和队尾进行操作，是一个先入先出的数据结构。
而在之前的链表实现中，只有针对链表头的操作是 O(1) 级别的，那么如果用来实现队列这种数据结构的话，就会有一端的操作是 O(n) 级别的，为了解决这个问题，可以给链表添加一个尾指针 tail 用于追踪链表尾部，达到对链表首尾两端的操作都是 O(1) 级别进而实现队列的目的。
当给链表添加尾指针 tail 后，可以发现在尾部删除元素是需要从头遍历找到前置节点的进行删除操作的，这个过程是 O(n) 的，不满足我们的需求；而如果在尾部添加元素的话，就和在链表头添加元素一个道理，是十分方便的，只需要 O(1) 的复杂度。再看回链表头，由之前的实现可以发现在头部删除元素非常方便，只需要 O(1) 的复杂度。
所以可以设计为在链表头进行删除元素的操作，在链表尾进行添加元素的操作。即将链表头作为队首，链表尾作为队尾。
由于在队列中只需要对两端进行操作，所以这里实现队列时就不复用前面实现的链表类了。在之前实现的链表类中，设计了虚拟头节点便于统一操作链表中的所有数据。而在现在的队列实现中只需要在头部删除元素在尾部添加元素，所以不需要使用虚拟头节点。只需要两个变量 head、tail 分别指向链表中的第一个元素和链表中的最后一个非 NULL 元素即可。
需要注意的是这样设计后当队列为空时，head 和 tail 都指向 NULL。
改进后的链表队列基本结构如下图所示：
和之前实现栈一样，这里也是实现一个 LinkedListQueue 类实现之前实现数组队列时定义的队列的接口 Queue 来实现队列的一系列的操作。
回顾队列的接口 Queue 的实现如下：
/**
* 定义队列支持的操作的接口
* 支持泛型
*
* @author 踏雪寻梅
* @date 2020/1/9 - 16:52
*/
public interface Queue<E> {
/**
* 获取队列中元素个数
*
* @return 队列中如果有元素,返回队列中当前元素个数;队列中如果没有元素返回 0
*/
int getSize();
/**
* 判断队列是否为空
*
* @return 队列为空,返回 true;队列不为空,返回 false
*/
boolean isEmpty();
/**
* 入队
* 将元素 element 添加到队尾
*
* @param element 入队的元素
*/
void enqueue(E element);
/**
* 出队
* 将队首的元素出队并返回
*
* @return 返回当前出队的队首的元素
*/
E dequeue();
/**
* 查看当前队首元素
*
* @return 返回当前的队首元素
*/
E getFront();
}
对于 LinkedListQueue 类的实现，具体实现如下：
/**
* 链表队列
* 支持泛型
*
* @author 踏雪彡寻梅
* @date 2020/2/5 - 14:45
*/
public class LinkedListQueue<E> implements Queue<E> {
/**
* 链表的节点
* 对于用户而言，不需要知道链表的底层结构是怎样的，只需要知道链表是一种线性数据结构，可以增删改查数据
*/
private class Node {
/**
* 节点存储的数据
*/
public E element;
/**
* 用于指向下一个节点,使节点与节点之间挂接起来组成链表
*/
public Node next;
/**
* 构造函数
* 构造一个存有数据并指向了下一个节点的节点
*
* @param element 存往该节点中的数据
* @param next 该节点的下一个节点
*/
public Node(E element, Node next) {
this.element = element;
this.next = next;
}
/**
* 构造函数
* 构造一个存有数据但没有指向下一个节点的节点
*
* @param element 存往该节点中的数据
*/
public Node(E element) {
this(element, null);
}
/**
* 构造函数
* 构造一个空节点
*/
public Node() {
this(null, null);
}
/**
* 重写 toString 方法以显示节点中存储的数据信息
*
* @return 返回节点中存储的数据信息
*/
@Override
public String toString() {
return element.toString();
}
}
/**
* 用于指向链表队列的第一个节点
*/
private Node head;
/**
* 用于指向链表队列的最后一个非 NULL 节点
*/
private Node tail;
/**
* 链表队列当前元素个数
*/
private int size;
/**
* 构造函数
* 构造一个空的链表队列
*/
public LinkedListQueue() {
// 链表队列为空时, head 和 tail 都指向 null
head = null;
tail = null;
size = 0;
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void enqueue(E element) {
if (tail == null) {
// 空队时入队
tail = new Node(element);
head = tail;
} else {
// 非空队时入队
tail.next = new Node(element);
tail = tail.next;
}
// 维护 size,队列当前元素个数 + 1
size++;
}
@Override
public E dequeue() {
// 出队时判断队列是否为空
if (isEmpty()) {
throw new IllegalArgumentException("Dequeue failed. Cannot dequeue from an empty queue.");
}
// 记录要出队的节点
Node dequeueNode = head;
// 将队头节点出队
head = head.next;
dequeueNode.next = null;
// 如果出队后队列为空,维护 tail 指向 null,空队时 head 和 tail 都指向 null
if (head == null) {
tail = null;
}
// 维护 size,队列当前元素个数 - 1
size--;
// 返回出队元素
return dequeueNode.element;
}
@Override
public E getFront() {
// 获取队头元素时判断队列是否为空
if (isEmpty()) {
throw new IllegalArgumentException("GetFront failed. Queue is empty.");
}
// 返回队头元素
return head.element;
}
/**
* 重写 toString 方法显示链表队列的详细信息
*
* @return 返回链表队列的详细详细
*/
@Override
public String toString() {
StringBuilder result = new StringBuilder();
result.append(String.format("LinkedListQueue: size: %d, front [ ", getSize()));
// 从链表中第一个元素开始遍历,依次将链表中元素信息添加到结果信息中
Node currentElement = head;
while (currentElement != null) {
result.append(currentElement + "->");
currentElement = currentElement.next;
}
result.append("NULL ] tail");
return result.toString();
}
}
在实现中需要注意的是在入队时如果是空队列需要维护 head 指向 tail，否则 head 会指向 null。以及在出队时需要判断出队后队列是否为空，如果为空需要维护 tail 指向 null。以及需要注意队列为空时 head 和 tail 都指向 null。
接下来，对以上实现做一些测试，检测是否和预期结果不符，测试代码如下：
/**
* 测试 LinkedListQueue
*/
public static void main(String[] args) {
LinkedListQueue<Integer> queue = new LinkedListQueue<>();
// 判断队列是否为空
System.out.println("==== 测试 isEmpty ====");
System.out.println("当前队列是否为空: " + queue.isEmpty());
System.out.println("\n==== 测试入队和出队, 10 次 入队, 每 3 次入队就出队 1 次====");
for (int i = 0; i < 10; i++) {
// 入队
queue.enqueue(i);
// 显示入队过程
System.out.println(queue);
// 每入队 3 个元素就出队一次
if (i % 3 == 2) {
// 出队
queue.dequeue();
// 显示出队过程
System.out.println("\n" + queue + "\n");
}
}
// 判断队列是否为空
System.out.println("\n==== 测试 isEmpty ====");
System.out.println("当前队列是否为空: " + queue.isEmpty());
// 获取队首元素
System.out.println("\n==== 测试 getFront ====");
System.out.println(queue);
Integer front = queue.getFront();
System.out.println("当前队列队首元素为: " + front);
}
测试结果:
==== 测试 isEmpty ====
当前队列是否为空: true
==== 测试入队和出队, 10 次 入队, 每 3 次入队就出队 1 次====
LinkedListQueue: size: 1, front [ 0->NULL ] tail
LinkedListQueue: size: 2, front [ 0->1->NULL ] tail
LinkedListQueue: size: 3, front [ 0->1->2->NULL ] tail
LinkedListQueue: size: 2, front [ 1->2->NULL ] tail
LinkedListQueue: size: 3, front [ 1->2->3->NULL ] tail
LinkedListQueue: size: 4, front [ 1->2->3->4->NULL ] tail
LinkedListQueue: size: 5, front [ 1->2->3->4->5->NULL ] tail
LinkedListQueue: size: 4, front [ 2->3->4->5->NULL ] tail
LinkedListQueue: size: 5, front [ 2->3->4->5->6->NULL ] tail
LinkedListQueue: size: 6, front [ 2->3->4->5->6->7->NULL ] tail
LinkedListQueue: size: 7, front [ 2->3->4->5->6->7->8->NULL ] tail
LinkedListQueue: size: 6, front [ 3->4->5->6->7->8->NULL ] tail
LinkedListQueue: size: 7, front [ 3->4->5->6->7->8->9->NULL ] tail
==== 测试 isEmpty ====
当前队列是否为空: false
==== 测试 getFront ====
LinkedListQueue: size: 7, front [ 3->4->5->6->7->8->9->NULL ] tail
当前队列队首元素为: 3
进程已结束，退出代码 0
从结果可以看出，实现的结果和预期是相符的，实现了队列的各个基本操作。整体的时间复杂度前面也简单分析过了，针对链表头部和尾部进行操作，时间复杂度都是 O(1) 级别的，并且拥有了链表的整体动态性。接下来和之前实现的数组队列和循环队列进行一些效率上的对比：
测试代码:
import java.util.Random;
/**
* 测试 ArrayQueue、LoopQueue 和 LinkedListQueue 的效率差距
*
* @author 踏雪寻梅
* @date 2020/1/8 - 16:49
*/
public class Main2 {
public static void main(String[] args) {
// 测试数据量
int opCount = 10000;
// 测试数组队列所需要的时间
ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
double arrayQueueTime = testQueue(arrayQueue, opCount);
System.out.println("arrayQueueTime: " + arrayQueueTime + " s.");
// 测试循环队列所需要的时间
LoopQueue<Integer> loopQueue = new LoopQueue<>();
double loopQueueTime = testQueue(loopQueue, opCount);
System.out.println("loopQueueTime: " + loopQueueTime + " s.");
// 测试链表队列所需要的时间
LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
double linkedListQueueTime = testQueue(linkedListQueue, opCount);
System.out.println("linkedListQueueTime: " + linkedListQueueTime + " s.");
}
/**
* 测试使用队列 queue 运行 opCount 个 enqueue 和 dequeue 操作所需要的时间,单位: 秒
* @param queue 测试的队列
* @param opCount 测试的数据量
* @return 返回整个测试过程所需要的时间,单位: 秒
*/
private static double testQueue(Queue<Integer> queue, int opCount) {
long startTime = System.nanoTime();
// 用于生成随机数入队
Random random = new Random();
// opCount 次 enqueue
for (int i = 0; i < opCount; i++) {
// 入队
queue.enqueue(random.nextInt(Integer.MAX_VALUE));
}
// opCount 次 dequeue
for (int i = 0; i < opCount; i++) {
// 出队
queue.dequeue();
}
long endTime = System.nanoTime();
// 将纳秒单位的时间转换为秒单位
return (endTime - startTime) / 1000000000.0;
}
}
测试结果-1（opCount 为 1 万时）
测试结果-2（opCount 为 10 万时）
测试结果-3（opCount 为 100 万时）
从以上几种结果可以看出，在我这台机器上数组队列耗时比基于数组的循环队列和链表队列要大的多，基于数组的循环队列耗时和链表队列相差不大，是常数倍的差异。
对于数组队列而言它的入队操作是 O(1) 级别的、出队操作是 O(n) 级别的，所以在以上测试中整体时间复杂度是 O(n2) 级别的（进行了 n 次入队和出队）。
而基于数组的循环队列和链表队列的入队操作和出队操作都是 O(1) 级别的，所以在以上测试中整体而言时间复杂度是 O(n) 级别的（都进行了 n 次入队和出队）。但这两者有时候也会出现一个快一点一个慢一点的情况，也是和前面的链表栈和数组栈的情况是一样的，这里不再阐述。
总而言之基于数组实现的循环队列和链表队列这两者是同一级别的复杂度的，相比数组队列的时间复杂度快了很多，时间上的差异是巨大的。
最后，链表队列在动态性上相比基于数组实现的循环队列会更好一些，不需要手动进行伸缩容量的实现。
实现到此处，链表的常见基本操作也都实现完成了，对于链表而言，也还存在着一些改进方案，比如给节点增加一个前置指针域用于指向当前节点的前置节点，使链表变成双链表等等。这里就不再实现了，具体过程还是大同小异的。
小结
-
链表是一种真正的动态的数据结构，不需要像数组一样手动地处理动态伸缩容量。
-
链表在针对头部和尾部做特殊处理后，可以实现栈和队列这两种数据结构，极大地发挥了链表的动态特性。
如有写的不足的，请见谅，请大家多多指教。
