单向链表
[!Tip]
本节源代码见Github链接🔗
概述
单向链表及普通链表，也是提到链表时的默认类型。它包含多个结点，每个结点有一个指向后继元素的next(下一个)指针。表中最后一个节点的next指针值为NULL，表示链表的结束。
单向链表的数据结构如下图所示：
单向链表的类型声明方式如下所示：
【👉🏻>>点击展开查看代码】
/**
* 普通单向链表 数据结点
*
* @className: NormalListNode
* @author: Max Solider
* @date: 2022-10-08 00:02
*/
public class NormalListNode {
/**
* 结点数据
*/
private int data;
/**
* 下一个结点
*/
private NormalListNode next;
public NormalListNode(int data) {
this.data = data;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public NormalListNode getNext() {
return next;
}
public void setNext(NormalListNode next) {
this.next = next;
}
}
优缺点及相关应用场景
单向链表的优缺点及相关应用场景，在链表概述中已经详细介绍过，不再赘述。
基本操作
对单向链表的基本操作包括：
- 遍历链表；
- 在链表中插入一个元素；
- 从链表中删除一个元素。
遍历链表
核心思路：
遍历链表就是从表头指针开始，根据元素结点的next信息，找到下一个元素结点，遍历时输出结点的内容或计数，直到next指针的值为NULL时，遍历结束。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 遍历链表，并返回链表长度
* @param: headNode 链表头结点
* @return: int 链表长度
* @author: Max Solider
* @date: 2022/10/8 00:39
*/
int listLength(NormalListNode headNode) {
NormalListNode currentNode = headNode;
int count = 0;
while (currentNode != null) {
count++;
System.out.println("链表第" + count + "个结点的值是：" + currentNode.getData());
currentNode = currentNode.getNext();
}
return count;
}
时间复杂度：
时间复杂度为O(n)，用于扫描长度为n的链表。
空间复杂度：
空间复杂度为O(1)，用于存储临时变量。
在链表中插入元素
常见操作：
单向链表的插入操作可以分为以下三种情况：
- 在链表头插入；
- 在链表尾插入；
- 在链表中间插入（随机位置）。
在表头前插入一个新结点
核心思路：
在表头插入新结点可以分为以下2步：
- 将新结点的next指针指向原链表的表头结点；
- 更新表头指针，指向新结点。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 表头插入新结点
* @param: 链表头, 新结点
* @return: NormalListNode 新链表头
* @author: Max Solider
* @date: 2022/10/8 10:48
*/
NormalListNode insertHead(NormalListNode headNode, NormalListNode newNode) {
if (newNode == null) {
return headNode;
}
newNode.setNext(headNode);
headNode = newNode;
return headNode;
}
时间复杂度：
时间复杂度O(1)。
空间复杂度：
无需额外空间。
在表尾插入一个新结点
核心思路：
在表尾插入一个新结点可以分为以下2步：
- 遍历找到表尾结点；
- 将表尾结点的next指针指向新结点。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 表尾插入新结点
* @param: 链表头, 新结点
* @return: NormalListNode 链表头
* @author: Max Solider
* @date: 2022/10/8 10:48
*/
NormalListNode insertTail(NormalListNode headNode, NormalListNode newNode) {
// 如果是空链表，或新结点是null，则直接返回
if (headNode == null || newNode == null) {
return headNode;
}
NormalListNode current = headNode;
while (current.getNext() != null) {
current = current.getNext();
}
current.setNext(newNode);
return headNode;
}
时间复杂度：
时间复杂度为O(n)，主要用于遍历链表。
空间复杂度：
空间复杂度为O(1)，用于存储临时变量。
在链表任意位置插入一个新结点
核心思路：
在链表任意位置插入一个新结点，包括以下5步：
- 判断插入位置是否合法；
- 判断是否在链表头插入；
- 找到待插入位置前一个结点；
- 将新结点的next指针，指向待插入位置的原结点；
- 将待插入位置前一个结点的next指针指向新结点。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 任意位置插入新结点
*
* @param headNode 链表表头
* @param newNode 新结点
* @param position 待插入位置
* @return 新链表表头
*/
NormalListNode insert(NormalListNode headNode, NormalListNode newNode, int position) {
int size = listLength(headNode);
// 插入位置合法性校验
if (position < 1 || position > size + 1) {
System.out.println("Position of node to insert is invalid. The valid inputs are 1 to " + (size + 1));
return headNode;
}
// 如果是在表头插入
if (position == 1) {
return insertHead(headNode, newNode);
}
// 表尾或中间位置插入，先找到待插入位置前一个结点
int currentPosition = 1;
NormalListNode previousNode = headNode;
while (currentPosition != position - 1) {
previousNode = previousNode.getNext();
currentPosition++;
}
// 将新结点的next指针指向待插入位置的原结点
newNode.setNext(previousNode.getNext());
// 将待插入位置前一个结点的next指针指向新结点
previousNode.setNext(newNode);
return headNode;
}
时间复杂度：
时间复杂度O(n)，主要用于遍历链表。
空间复杂度：
空间复杂度O(1)，用于存储临时变量。
从链表中删除元素
常见操作：
单向链表的删除操作可以分为以下3种情况：
- 删除链表头；
- 插入链表尾；
- 删除链表中间的结点。
删除表头结点
核心思路：
删除链表头结点，包括以下2步：
- 将表头指针指向第二个元素结点；
- 移除将原表头结点。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 删除表头结点
* @param: headNode
* @return: NormalListNode 新的表头结点
* @author: Max Solider
* @date: 2022/10/8 14:55
*/
NormalListNode deleteHead(NormalListNode headNode) {
if (headNode == null) {
return headNode;
}
NormalListNode newHead = headNode.getNext();
headNode.setNext(null);
headNode = null;
return newHead;
}
时间复杂度：
时间复杂度O(1)，无需遍历。
空间复杂度：
空间复杂度O(1)，需要存储一个临时变量。
删除表尾结点
核心思路：
删除表尾结点，包括以下2步：
- 将倒数第二个结点的next指针指向NULL；
- 删除原表尾结点。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 删除表尾结点
* @param: [headNode]
* @return: NormalListNode
* @author: Max Solider
* @date: 2022/10/8 15:14
*/
NormalListNode deleteTail(NormalListNode headNode) {
if (headNode == null) {
return headNode;
}
// 如果链表只有一个元素结点
if (headNode.getNext() == null) {
headNode = null;
return headNode;
}
NormalListNode previousNode = headNode;
// 遍历找到待删除结点前一个元素结点
while (previousNode.getNext().getNext() != null) {
previousNode = previousNode.getNext();
}
NormalListNode oldTail = previousNode.getNext();
oldTail = null;
previousNode.setNext(null);
return headNode;
}
时间复杂度：
时间复杂度为O(n)，因为需要遍历链表。
空间复杂度：
空间复杂度为O(1)，需要存储临时变量。
删除链表中任意结点
核心思路：
删除链表中间结点，包含以下6步：
- 判断删除位置合法性；
- 判断是否是删除表头结点；
- 遍历找到待删除位置的前一个元素结点；
- 将待删除位置前一个元素结点的next指针指向新结点；
- 将新元素结点的next指针指向原待删除位置的下一个结点；
- 移除原结点。
实现代码：
【👉🏻>>点击展开查看代码】
/**
* 删除任意位置元素结点
*
* @param headNode 链表头结点
* @param position 待删除位置
* @return NormalListNode
* @author: Max Solider
* @date: 2022/10/8 15:34
*/
NormalListNode delete(NormalListNode headNode, int position) {
// 如果是空链表，或者待删除位置不合法
if (headNode == null || position < 1) {
System.out.println("Position of node to delete is invalid. The position must be greater than 0");
return headNode;
}
// 如果是删除第一个元素结点
if (position == 1) {
NormalListNode deleteNode = headNode;
headNode = deleteNode.getNext();
deleteNode = null;
return headNode;
}
// 遍历找到待删除位置的前一个元素
int currentPosition = 1;
NormalListNode previousNode = headNode;
while (currentPosition != position - 1) {
previousNode = previousNode.getNext();
currentPosition++;
// 如果previousNode的下一个结点已经都是null了，还没走到待删除位置，说明待删除位置不合法
if (previousNode.getNext() == null) {
System.out.println("Position of node to delete is invalid. The position must be less than " + currentPosition);
return headNode;
}
}
NormalListNode deleteNode = previousNode.getNext();
// 将待删除位置的前一个元素的next指针指向待删除位置的下一个元素
previousNode.setNext(deleteNode.getNext());
// 移除待删除位置的元素
deleNode.setNext(null);
deleteNode = null;
return headNode;
}
时间复杂度：
需要遍历链表，因此时间复杂度是O(n)。
空间复杂度：
需要存储临时变量，因此空间复杂度是O(1)。