2.2链表(linked list)
链表是动态的数据结构，是一种逻辑上相邻但物理结构上不一定相邻的线性表。
2.2.1单链表
1.单链表的定义
单链表由一系列节点组成，每个节点包含数据和指向下一个节点的指针。形如下图所示：
其中：
(1)头指针 head：指向链表第一个节点的指针。无论单链表有多长，只要抓住头指针就可以遍历整个链表。
(2)中间节点：通过指针域连接形成链式结构。每个节点都能找到他自己的后继节点，却无法找到前驱节点，因此成为单向链表。
(3)尾节点：即链表中的最后一个节点。一般用tail指针来指向尾节点，尾节点指针域为 NULL，表示链表结束。
(4)判断链表是否为空：head等于NULL时为空链表。
节点的定义如下：
struct ListNode
{
int data; // 数据域
ListNode *next; // 指针域
ListNode(int x) : data(x), next(nullptr) {}//构造函数
};有了节点以后，我们就可以把这些节点都“串联”起来组成一个链表。我们可以这么做：
#include <bits/stdc++.h>
using namespace std;
struct ListNode
{
int data; // 数据域
ListNode *next; // 指针域
ListNode(int x) : data(x), next(nullptr) {}//构造函数
};
int main()
{
ListNode *head;
ListNode *n0 = new ListNode(1);//创建一个新节点，并用构造函数对其初始化
ListNode *n1 = new ListNode(2);
ListNode *n2 = new ListNode(3);
head = n0;//千万不能写成head->next = n0; 因为head未初始化，属于野指针
n0->next = n1;
n1->next = n2;
cout << "第1个节点为：" << head->data << endl;
cout << "第2个节点为：" << head->next->data << endl;
cout << "第3个节点为：" << head->next->next->data << endl;
return 0;
}一开始很多读者对形如：n0->next = n1;的代码不是很理解，赋值符号左侧是节点的指针域，可以看作是一个指针变量，而赋值符号右侧则是另一个节点的地址。
上面串联节点的做法透着似乎不太“聪明”的样子，下面我们把一些常用的功能封装成函数，并通过代码来探讨链表的优势在哪里。
2.单链表的常用操作
(1)创建链表。第一种方法是单独处理头节点：
ListNode *LinkedList_create(int n)
{
int data;
ListNode *head, *tail;
if (n <= 0)
return nullptr; // 处理n=0的情况
//单独处理头节点
cin >> data;
head = new ListNode(data);
tail = head;//始终指向链表中最后一个节点
//处理其余节点
for (int i = 1; i < n; i++)
{
cin >> data;
tail->next = new ListNode(data);
tail = tail->next;
}
return head;
}第二种方法是通过借助虚拟节点来简化上述操作，这样看起来更优雅一些：
ListNode *LinkedList_create(int n)
{
if (n <= 0)
return nullptr; // 处理n=0的情况
ListNode *dummy = new ListNode(0); // 虚拟头节点
ListNode *tail = dummy;
for (int i = 0; i < n; i++)
{
int data;
cin >> data;
tail->next = new ListNode(data);
tail = tail->next;
}
ListNode *head = dummy->next; //实际头节点
delete dummy; //删除虚拟头节点
return head;
}(2)打印输出链表
从给定的头节点开始，依次打印每个节点的数据，直到最后一个节点，这个过程成为遍历输出链表，也叫打印输出链表。如果不需要输出，仅是枚举链表中的每个节点也可以使用这段代码：
void LinkedList_print(ListNode *head)
{
if (head == nullptr)
{
cout << "空链表" << endl;
return;
}
ListNode *current = head;
while (current->next != nullptr)
{
cout << current->data << " -> ";
current = current->next;
}
cout << current->data << endl;
}在做链表练习的时候一定要注意检查空指针，否则程序容易崩溃。另外作为练习，也可以使用递归来输出链表。下面代码不建议在竞赛或真正生产环境中使用：
void LinkedList_print_recursive(ListNode *node)
{
if (node == nullptr)
{
cout << endl;
return;
}
cout << node->data;
if (node->next)
cout << " -> ";
LinkedList_print_recursive(node->next);
}(3)按值查找操作
在链表中查找值域的值为target的节点，并返该节点的指针。
ListNode *LinkedList_find(ListNode *head, int target)
{
ListNode *current = head;
while (current)
{
if (current->data == target)
return current;
current = current->next;
}
return nullptr;
}读者可以试着写一下下面四个类似的函数：
ListNode* LinkedList_find_pre(ListNode* head, int target) 功能：返回target节点之前的节点的指针
ListNode* LinkedList_find_next(ListNode* head, int target) 功能：返回target节点之后的节点的指针
ListNode* LinkedList_find_at(ListNode* head, int k) 功能：返回第k个节点的指针
ListNode* LinkedList_find_end(ListNode* head) 功能：返回最后一个节点的指针
(4) 在指定位置（后）插入操作
bool LinkedList_insert_after(ListNode *node, int val)
{
if (node == nullptr)
return false;
ListNode *p = new ListNode(val);
p->next = node->next;
node->next = p;
return true;
}读者自行增加：在特定位置之前的插入操作、在指定值之后（前）的插入操作、指定次序之后（前）的插入操作、在链表头之前的插入操作、在链表尾之后的插入操作等。
(5) 删除指定值的节点
ListNode *LinkedList_delete_value(ListNode *head, int val)
{
if (head == nullptr)
return nullptr;
//如果第一个节点就是要删除的节点
if (head->data == val)
{
ListNode *newHead = head->next;
delete head;
return newHead;
}
//查找要删除节点的前一个节点
ListNode *current = head->next;
while (current->next != nullptr && current->next->data != val)
current = current->next;
if (current->next->data == val)
{
ListNode *nodeToDelete = current->next;
current->next = nodeToDelete->next;
delete nodeToDelete;
}
return head;
}从while()循环出来后，current不可能既是最后一个节点，又是值为val的节点。所以有两种可能： 第一种，current是最后一个节点，这说明链表中不存在值是val的节点；第二种，current的下一个节点的值是val。
读者自行增加：删除指定位置的节点、删除头节点、删除尾节点等操作的函数。另外链表的常用操作还包括：反转链表、链表排序以及链表去重等操作。
2.2.2双向链表
双向链表是链表的扩展形式，每个节点包含两个指针：一个指向前一个节点（prev），一个指向后一个节点（next），以满足单向链表只能向后不能向前的不足。
双向链表节点的定义如下：
struct DoublyListNode
{
int data; // 数据域
DoublyListNode *prev; // 指向前驱节点
DoublyListNode *next; // 指向后继节点
DoublyListNode(int x) : data(x), prev(nullptr), next(nullptr) {}
};1.双向链表的插入操作
2.双向链表的删除操作
2.2.3循环链表
在单链表中，由于每个节点都指向后继节点，所以只能先后操作，不能向前操作（因此叫做单向链表）。如果把尾节点next域的值(NULL)改成head，单链表就变成了循环链表。双向链表除了要修改尾节点的next域以外，还要修改头节点的pre域，使其指向尾指针。
无论单向链表、双向链表还是循环链表，判空条件都是看head是否等于NULL。
2.2.4静态链表