目录
【PS】学校里也学到了，之前在信竞中也已经学过，此博客只当作个人的知识整理和备份。如果有错误的地方，请帮忙指出，谢谢！
本文引文基本出自Starting Out with C++ From Control Structures Through Objects 8th Global Edition
1. 链表（Linked List）
1.1 什么是链表？
A linked list is a series of connected nodes, where each node is a data structure. A linked list can grow or shrink in size as the program runs.
链表是一系列连接的节点，其中每个节点都是一个数据结构。和数组的功能相似，都是存储一系列同种数据类型的数据结构。
如下图，链表的每一个元素都是由一个自身的数据内容和（至少）一个指针构成的。这个指针至关重要，它承载着下一个（或上一个）元素的地址信息。这就好比自己家里有一个同学家的地址一样，只要依据这个地址，就可以找到同学家（下一个元素）的位置。这样子，一个“链”表就形成了。
当然，总得有个头啊。因此在这个链表得第一个人而言，要有一个指针专门指向第一个元素。对于新加进链表得最后一个元素而言，它是最后一个，没有下一个元素得地址，因此一般先指向自己（自己的指针指向自己）或者是一个空指针。
当然，很明显的可以看到，如果我要找到链表中的某一个元素，必须从头开始找，就跟藏宝图一样，找到一个新的宝藏和藏宝图，继续按新的藏宝图寻找下一个…
但是对于链表来说，每一个元素在物理内存中可以动态分配位置的，而不像数组一样，在物理内存中是以相邻的地址去分配的。
1.2 链表和数组（Array）、向量（Vector）的区别
虽然链表的结构会相比于数组复杂，但是链表最大的优势在于，它是可以在程序运行时大小可以随意变化，即用户想增加链表中的元素个数和减少元素个数都是可以的。而数组虽然大小可以由用户决定，一旦在程序中定义后则不可再更改大小。因此，通常说数组是“静态”（Static）的，而链表是“动态”的（Dynamic）。
称链表为动态的还有一个原因，是他比较好“维护”，也就是说，用户在链表中的某一处添加一个元素非常的容易。这也是它和向量的最大区别。虽然说链表可能没有比向量优越（指在STL中的代码），但是在动态的修改中依然占有较大的优势。如果向量中间要加入一个新元素，则这个位置后面的元素都要相应的往后位移。但是链表只需要将“链”（前一个元素的指针）链在自己身上即可添加新元素，维护起来非常的方便。相同的删除这个元素只需要把这个“链”（前一个元素的指针）从自身上卸下来，链到后面的元素即可直接将当前这个元素“删除”。
当然，数组相比于向量，向量也可以动态修改大小。数组是存储在栈中，而向量是存储在堆中，存储的位置不一致。但是数组的执行效率相比于向量会高不少。
1.3 使用链表
1.3.1 链表结构
相对简单的，我们直接可以用struct定义一个链表的结构（当然也可以使用class，使用struct是因为其结构相对比较简单，只有成员变量）：
struct ListNode
{
double value; //链表中的数据元素（可以不同数据类型）
ListNode *next; //一个同类型的指针，用于指向下一个结构体的
};
这个看起来有点套娃，这个实际上是一种自引用数据结构（self-referential data structure），这可以让每个节点都去生成跟自己相同类型的数据结构。
当然，正如刚刚所说，总得有个头啊，因此再定义一个头指针：
ListNode *head; //当然最好初始化成空指针
1.3.2 封装一个自己的链表类
我们可以将这一整个封装成一个非常简单的类（单向链表），里面包含数据元素，相应的头指针，相应的成员函数：访问器，删、改、插入、添加等操作（像是自己写了一个库文件一样）：
class NumberList
{
private:
struct Node //定义链表结构体
{
double value; //要存储的数据
struct ListNode *next; //下一个链表元素的指针
};
Node *head; //头指针
int length; //链表长度
public:
NumberList() { head = nullptr; length = 0; } //构造函数，将头指针置为空指针，链表长度初始化为0
~NumberList(); //解构函数
void appendNode(double); //在链表末尾添加一个节点
void insertNode(double); //在链表中间添加一个节点
void deleteNode(double); //删除一个节点
void displayList() const; //访问器，展示链表
};
1.3.3 在尾部添加节点（Append）
对于在链表尾部添加一个节点，原理不难理解，例如下图12.6要放到7.9后面。先设置一个nodePtr，指针从head给出，一个个向下索引至末尾节点（即所引到空指针），这时候nodePtr便指向7.9了，这时候只需要将7.9的指针指向12.6，即可完成添加节点
代码实现：
void NumberList::appendNode(double num)
{
Node *newNode; //新建一个指针->当前新要添加进来的节点
Node *nodePtr; //新建一个指针->用于搜寻末尾节点
newNode = new Node; //申请空间，将一个结构体实例化
newNode->value = num; //新节点的值是传入进来的值
newNode->next = nullptr;
//新节点由于是当前链表尾部的节点，没有它指向的下一个点了，因此它自己的这个指针置为空指针
if (!head) //如果当前此链表还没有节点，将新加入节点置为头节点
head = newNode;
else //如果已经有节点了，就要去寻找还未更新时的最后一个节点
{
nodePtr = head; //先获得头节点的地址
while (nodePtr->next) //根据地址一个接一个的往下找，直到遇到空指针（说明到末尾了）
nodePtr = nodePtr->next;
nodePtr->next = newNode; //把最后一个节点的指针指向现在新加入的节点
}
length++; //更新链表长度
}
1.3.4 在中间插入一个元素
插入的方法很容易理解，例如10.5要插入到7.9和12.6中间，只需要将7.9的指针指向10.5，然后将10.5的指针指向12.6即可完成插入。
这是链表的优势所在，代码实现可以这么写：
void NumberList::insertNode(double pos, double num)
{
Node *newNode; //新建一个指针->需要插入的节点
Node *nodePtr; //新建一个指针->用于遍历链表
Node *previousNode = nullptr; //新建一个指针->用于存储上一个节点
newNode = new Node; //申请空间，将结构体实例化
newNode->value = num; //将值写入新节点中
if (!head) //如果没有节点，则默认这个为第一个节点，并说明
{
cout<<"No node in the list, considering as the first node"<<endl;
head = newNode;
head->next = nullptr;
}
else
{
if (pos == 0) //如果直接在头部插入新节点
{
newNode->next = head; //将新节点的指针指向原来的头
head = newNode; //更新头指针为此新节点
}
else
{
nodePtr = head; //先给予头部指针
while (nodePtr->next && cnt < pos) //寻找到输入位置的节点
{
previousNode = nodePtr; //持续更新前一个节点
nodePtr = nodePtr->next; //持续寻找下一个节点
cnt++; //计数，链表的第几个
}
if (cnt < pos) //如果没到设定位置，即说明链表长度太短，默认将节点设为链表的末尾
{
cout<<"Warning: Insert "<<pos<<": Number would be inserted to the end of the list."<<endl;
newNode->next = nullptr;
nodePtr->next = newNode;
}
else //如果找到了，直接将节点插入previousNode和NodePtr之间
{
previousNode->next = newNode;
newNode->next = nodePtr;
}
}
length++; //更新链表长度
}
1.3.5 在中间删除一个元素
删除一个元素的方法也很简单，只需要将前一个节点的指针指向当前指针指向的节点，即可删除当前的节点。例如要将7.9从中间删除，只需要把2.5的指针指向12.6即可，这样7.9的地址就被丢失了，因此索引不到它，像是被“删除”了。
代码实现：
void NumberList::deleteNode(int pos) //给定链表中的位置进行删除
{
int cnt = 0; //计数，数链表的第几个节点
Node *nodePtr; //设置新指针->用于遍历
Node *previousNode = nullptr; //设置新指针->用于实时更新遍历指针的前一个
if (!head) //如果链表还是空的，不能进行删除操作
{
cout<<"The list is empty!"<<endl;
return;
}
else
{
if (pos == 0) //如果想将链表头部删除
{
nodePtr = head->next;
delete head;
head = nodePtr;
}
else
{
while(nodePtr != nullptr && cnt < pos) //向下索引到相应位置
{
previousNode = nodePtr;
nodePtr = nodePtr->next;
cnt++;
}
if(cnt < pos) //如果索引到的小于输入的位置，则说明链表过短，默认删除链表最后一个节点
{
cout<<"Warning: Delete "<<pos<<": "<<"The end of the list would be deleted."<<endl;
previousNode->next = nullptr;
delete nodePtr;
}
else
{
previousNode->next = nodePtr->next;
}
}
}
length--; //更新链表长度
}
1.3.6 展示链表
之前的文章提到，类需要Accessor去访问链表里的值，因此，展示链表的成员函数是必须的。当然，这里只是把每个节点的值和链表的长度展示出来。
代码实现：
void NumberList::displayList() const
{
Node *nodePtr;
nodePtr = head; //从头部开始索引
while (nodePtr)
{
cout<<nodePtr->value<<endl; //每个节点都将值输出
nodePtr = nodePtr->next; //继续索引下一个节点
}
cout<<"Total number in the list: "<<length<<endl; //将链表长度展示
}
1.3.7 测试
将此类进行测试，测试代码：
int main()
{
NumberList list; //实例化一个链表类
list.appendNode(5.6); //末尾添加节点
list.appendNode(7.2);
list.insertNode(0,3.3); //头部插入节点
list.insertNode(0,5.6);
list.insertNode(2,9.9);
list.insertNode(6,12.38); //测试默认在尾部添加节点
list.displayList();
cout<<endl;
list.deleteNode(0); //删除头部节点
list.deleteNode(2); //删除中间节点
list.deleteNode(8); //测试默认在尾部删除节点
list.displayList();
}
结果：
Warning: Insert 6: Number would be inserted to the end of the list.
5.6
3.3
9.9
5.6
7.2
12.38
Total number in the list: 6
Warning: Delete 8: The end of the list would be deleted.
3.3
5.6
7.2
Total number in the list: 3
链表这种类可以写成模板（Template），供以后嵌套和使用
1.4 链表的类型
链表有很多种类型，依据不同的功能而设计。
1.4.1 单向链表（singly linked lists）
刚刚上面定义的即是单向链表，即每个节点只含有下一个节点地址的信息。当然，单项链表可以反过来，即最后的一个节点一个个向前一个指。
1.4.2 双向链表（doubly linked list）
双向链表，顾名思义，是一个节点同时包含前一个节点和后一个节点的地址信息。这样索引的时候既可以往前索引，也可以往后索引。
1.4.3 循环链表（circularly linked list）
循环链表是节点之间形成闭环，每个节点指向下一个，形成一个闭环。
1.5 STL List库
对于链表而言，C++标准库中有现成的成熟库，可以直接调用。list是一种双向链表。
库声明：
#include <list>
转自C++ list用法。对应成员函数：
实例化一个链表：
list<int> myList; //生成一个int的链表
相关成员函数
assign() //给list赋值
back() //返回最后一个元素
begin() //返回指向第一个元素的迭代器
clear() //删除所有元素
empty() //如果list是空的则返回true，否则返回false
end() //返回末尾的迭代器
erase(x)/erase(x,y) //删除第
front() //返回第一个元素
get_allocator() //返回list的配置器
insert() //插入一个元素到list中
max_size() //返回list能容纳的最大元素数量
merge() //合并两个list
pop_back() //删除最后一个元素
pop_front() //删除第一个元素
push_back() //在list的末尾添加一个元素
push_front() //在list的头部添加一个元素
remove() //从list删除元素
remove_if() //按指定条件删除元素
resize() //改变list的大小
reverse() //把list的元素倒转
size() //返回list中的元素个数
sort() //给list排序
swap() //交换两个list
unique() //删除list中的重复元素