数据结构之链表（一）：单链表
一、单链表
链表是一种线性结构，通过前后节点指针连接起每个节点，从结构来看就像是用一个链把所有的节点都串起来了，因此被称为链表。
它和数组最大的不同就是不能随机访问，数组的内存空间是顺序的，通过计算位置偏差就能定位到元素。而链表的节点的地址是不连续的，它无法直接通过地址定位随机访问。但是数组在以下场景就没有链表方便了：
- 开辟新空间：数组元素到达上限后，如需添加新元素，需要重新开辟一块更大的空间，然后把当前数组的数据拷贝过去再继续添加元素。
- 删除元素：删除数组元素后，需要把被删除元素后面的元素都集体前移。
- 移动元素：移动元素和删除类似，移动节点会导致部分节点数据迁移。
但是对于链表而言，都不存在以上问题。它不管是新增、删除甚至移动节点，都能在O(1)的时间完成。因此，在某些情况下，它更适合数组来使用。
二、单链表的操作
2.1 链表结构
链表都是由一个个节点组成的，从面向对象的特性上来说，链表和节点是两个不同的东西。每个节点至少都包含了一个数据字段和一个next节点指针，next指针指向的是下一个节点地址，而链表只需要保存一个首节点指针就行了。通过链表的首节点指针和每个节点的next指针，就可以循环遍历到节点的每一个元素了。
2.2 添加节点操作
添加节点的操作可通过下图演示：
可以分为两步来描述：
- 设置新节点（B节点）的
next指针为下一个节点（C节点）地址。 - 把插入节点（A）节点的
next指针指向新节点（B节点）。
这样就完成了一个节点的插入。
2.3 删除节点操作
删除节点的操作图示：
操作描述：
- 找到删除节点的前置节点（A节点）。
- 设置前置节点的next指针为删除节点的next指针指向。
- 删除节点。
2.4 移动节点操作
移动节点的操作可以分解为删除和添加节点两步：
- 把移动节点从链表中删除。
- 把这个删除的节点重新插入到链表的指定位置。
三、代码描述（C++）
3.1 节点和链表定义
节点定义：
template<typename T>
class list_node {
public:
friend class singly_linklist<T>;
list_node() : next(nullptr) {}
list_node(const T &data) : next(nullptr), data(data) {}
private:
T data;
list_node<T> *next;
};节点的定义很简单，包含了一个T类型的数据域和next指针，其中比较特殊的是对singly_linklist类的友元定义，singly_linklist是后面要定义的链表类，通过设置友元可以方便链表类直接操作节点中的私有数据域，因为需要在链表中对节点进行新增、删除和移动等操作。
链表的定义如下：
template<typename T>
class singly_linklist {
public:
singly_linklist() : len(0), head(nullptr), tail(nullptr) {}
private:
size_t len;
list_node<T> *head;
list_node<T> *tail;
};链表中包含了两个指针head和tail，head指针是上面说的链表首元素的地址，而tail指针则是链表尾元素指针，tail指针在单链表中实际上没有很大的用途，但是在后续的双向链表和双向循环链表中都会用到，单链表中可以用作冗余字段使用。
除了首位指针以外，还有一个表示链表长度的字段，这个字段也是作为冗余使用，实际项目中如果需要获取链表长度就可以在0(1)时间返回，避免了便利链表。链表长度的设置方法也很简单：每添加一个节点，长度加一；每删除一个节点，长度减一。
3.2 添加节点
插入链表节点的逻辑很简单，代码在网上一搜也是一大把，但很少有准确并简单的实现方式。
本文中的链表（包括后续的双向链表和循环链表）都参考了linux内核中的实现方式，力求简单、高效并且准确。
链表节点的插入有头插法和尾插法，头插法的意思是把节点插到链表头部，而尾插法的意思是把节点插到链表尾部。两者逻辑不同，但是共同点就是都要插入节点到链表中，只是插入的位置不同。因此对添加节点而言，有必要把插入节点逻辑抽离出来作为私有函数供其他插入函数调用。
定义一个私有的添加节点函数（c语言中通过static关键字完成，c++通过private关键字完成），传入参数包含三个：
- 待插入的节点
new_node，因为是私有函数提供给类中的其他函数使用的，因此外部函数调用前要确保值不为空。 - 待插入节点的前置节点
prev，值可能为空（插入节点到链表首部的时候）。 - 待插入节点的后置节点
next，值可能为空（插入节点到链表尾部的时候）。
添加节点除了设置前后节点指针以外，还有一个难处理的地方就是首尾指针的赋值。
什么时机才应该重新赋值首尾指针？？？
更新首尾指针的地址的场景：
- 空链表插入新节点。
- 非空链表插入节点到链表首部或者尾部。
- 删除首、尾节点（删除的场景在下面讨论）。
可以整理出来的一个规律是：
- 如果新插入节点的前置节点是空（此时插入节点到链表头），设置头指针为新插入的节点。
- 如果新插入节点的后置节点为空（此时插入节点到链表尾），设置尾指针为新插入的节点。
代码如下：
/*
* 添加节点操作，新添加的节点需确保不是空值
* @new_node 新节点
* @prev 前驱节点，节点可能为空（插入到首部的时候）
* @next 后继节点，节点可能为空（插入到尾部的时候）
*/
template <typename T>
void singly_linklist::add_node(list_node<T> *new_node, list_node<T> *prev, list_node<T> *next) {
len++;
new_node->next = next;
if (prev) { // 如果前置节点不为空，修改前置节点的next指针
prev->next = new_node;
} else { // 前置节点为空，说明放在了链表头部，设置头节点的指针
head = new_node;
}
if (next == nullptr) { // 后置节点为空，说明放在链表的尾部，设置尾节点的指针
tail = new_node;
}
}实现了add_node函数后，再实现头插和尾插函数就简单了：
/*
* 插入元素到末尾
* @data 待插入数据
*/
template <typename T>
const singly_linklist<T> &singly_linklist::push_back(list_node<T> *node) {
if (node == nullptr)
return *this;
// 添加节点到末尾，前置节点是尾节点，后置节点是空
add_node(node, tail, nullptr);
return *this;
}
/*
* 插入数据到开头
* @node 待插入的数据节点
*/
template <typename T>
const singly_linklist &singly_linklist::push_front(list_node<T> *node) {
if (node == nullptr)
return *this;
// 添加节点到开头，前置节点是空，后置节点是头节点
add_node(node, nullptr, head);
return *this;
}一个要注意的地方是两个函数的返回值都是const singly_linklist &，在函数结束后都返回*this，这么做的目的就是为了支持链式表达式。
3.3 删除节点
删除节点和添加节点一样，难处理的地方就是首尾指针的赋值（也就是上面添加节点时说到的需要处理但是还没有处理的的第3点）。
删除节点时处理首尾指针的规律和插入节点一致：
- 如果删除节点的前置节点是空（删除的是头节点），设置头节点指针为删除节点的后置节点。
- 如果删除节点的后置节点是空（删除的是尾节点），设置尾节点指针为删除节点的前置节点。
代码如下：
/*
* 删除节点，待删除的节点请确保不是空值
* @del_node 待删除节点
* @prev 前驱节点
* @next 后继节点
*/
template <typename T>
void singly_linklist::remove_node(list_node<T> *del_node, list_node<T> *prev, list_node<T> *next) {
len--;
del_node->next = nullptr;
if (prev) { // 如果存在前置节点，更新前置节点的next指针
prev->next = next;
} else { // 不存在前置节点，删除的是头节点，更新头节点的指针
head = next;
}
if (next == nullptr) { // 不存在后置节点，删除的是尾节点，更新尾节点指针
tail = prev;
}
}对比remove_node和add_node的函数实现可以看到，函数开头都没有对新增节点或删除节点做合法校验。
不校验的意义在于两个都是内部函数，提供给内部其他函数使用的，其他函数在外层调用的时候已经判断参数合法性了，函数内已经确保不会为空。
在实现remove_node之后，需要再实现的一个功能是找到前置节点，因为删除节点要先找到前置节点才能调用。查找前置节点函数find_prev的操作为：
/*
* 查找某个节点的前一个节点
* @node 当前节点
* @return 如果存在上一个节点，返回上一个节点的地址，否则返回nullptr
*/
template <typename T>
list_node<T> *singly_linklist::find_prev(list_node<T> *node) {
list_node<T> *p = head;
if (node == nullptr)
return nullptr;
// 遍历链表查找前置节点
while (p != nullptr) {
if (p->next == node) {
return p;
}
p = p->next;
}
return p;
}有了find_prev之后，对外的remove函数就可以实现了：
/*
* 删除节点
* @node 待删除节点
*/
template <typename T>
const singly_linklist &singly_linklist::remove(list_node<T> *node) {
list_node<T> *prev;
if (node == nullptr)
return;
// 找到前置节点
prev = find_prev(node);
// 删除节点
remove_node(node, prev, node->next);
delete node;
}基于remove函数实现pop_front和pop_bak：
// 弹出首元素
template <typename T>
const singly_linklist &singly_linklist::pop_front() {
remove(head);
}
// 弹出尾元素
template <typename T>
const singly_linklist &singly_linklist::pop_back() {
remove(tail);
}四、单元测试
测试头插法：
TEST(singly_linklist, push_front) {
int i;
singly_linklist<int> list;
const list_node<int> *p;
vector<int> v{1, 2, 3};
list.push_front(3).push_front(2).push_front(1);
EXPECT_EQ(3, list.get_len());
p = list.get_head();
for (i = 0; i < v.size(); i++) {
EXPECT_EQ(p->get_data(), v[i]);
p = p->get_next();
}
EXPECT_EQ(p, nullptr);
}测试尾插法：
TEST(singly_linklist, push_back) {
int i;
singly_linklist<int> list;
const list_node<int> *p;
vector<int> v{1, 2, 3};
list.push_back(1).push_back(2).push_back(3);
EXPECT_EQ(3, list.get_len());
p = list.get_head();
for (i = 0; i < v.size(); i++) {
EXPECT_EQ(p->get_data(), v[i]);
p = p->get_next();
}
EXPECT_EQ(p, nullptr);
}测试获取前置节点：
TEST(singly_linklist, get_prev) {
int i;
singly_linklist<int> list;
const list_node<int> *p;
list_node<int> *node1, *node2, *node3;
// 插入3个节点
node1 = new list_node<int>(1);
node2 = new list_node<int>(2);
node3 = new list_node<int>(3);
list.push_back(node1).push_back(node2).push_back(node3);
EXPECT_EQ(3, list.get_len());
p = list.find_prev(node1);
EXPECT_EQ(p, nullptr);
p = list.find_prev(node2);
EXPECT_EQ(p, node1);
p = list.find_prev(node3);
EXPECT_EQ(p, node2);
}测试删除节点：
TEST(singly_linklist, remove) {
int i;
singly_linklist<int> list;
const list_node<int> *p;
list_node<int> *node1, *node2, *node3;
node1 = new list_node<int>(1);
node2 = new list_node<int>(2);
node3 = new list_node<int>(3);
list.push_front(node1);
list.push_back(node2);
list.push_back(node3);
// 删除中间节点
list.remove(node2);
EXPECT_EQ(node1, list.get_head());
EXPECT_EQ(node3, list.get_tail());
EXPECT_EQ(node1->get_next(), node3);
// 删除头节点
list.remove(node1);
EXPECT_EQ(node3, list.get_head());
EXPECT_EQ(node3, list.get_tail());
EXPECT_EQ(node3->get_next(), nullptr);
// 删除尾节点
list.remove(node3);
EXPECT_EQ( list.get_head(), nullptr);
EXPECT_EQ( list.get_tail(), nullptr);
}测试结果：
