链表

1、链表结构

链表是一种不连续的线性数据集合，与数组的有序性不同，链表是通过每个节点指向下一个节点的方式来连接的。

链表可通过多种方式实现：

• 用数组的值来指向下一个节点的位置
• 用结构体的字段指向下一个节点的位置
• 用结构题的字段指针指向下一个节点
• 用STL的formard_listlist、list

和数组、vector等不同的是，链表的插入删除都很快，但不支持随机存取，即[下标]访问。

场景：链表一般应用在需要动态插入、删除的场景.

2、STL的链表结构

STL里提供了list容器做为双向链表，单向链表使用forward_list。

2.1 初始化

#include <list>
list<int> li;

也可以用更多的构造函数来初始化：

list<int> li(count); //含count个默认0
list<int> li(count, x); //含count个默认x
list<int> li(list2); //从list2 copy过来
list<int> li(list, it1, it2); //从list2 copy过来一个区间[it1, it2]

2.2 迭代器

list不能用随机访问，也就是说不能用类似数组的[下标]方式访问，必须用iterator来访问遍历。

list<int>::iterator it;
for(it = li.begin(); it != it.end(); it++)
  cout<< *it <<endl;

如果是结构体：

list<Node>::iterator it;
for(it = li.begin(); it != it.end(); it++)
  cout<< it->w <<endl; //或 (*it).w，假设Node有字段w

显然，遍历的时候就可以进行查找。

注意：迭代器只能++和--，不能用it += 3这样。

2.3 查找

也可直接使用std的find函数来查找：

list<Node>::iterator it;
it = std::find(li.begin(), li.end(), k);//查找等于k的元素，找不到就是li.end()

如果是结构体，就需要重载 == 运算符。

2.4 排序

不能用sort函数（因为不支持随机访问），可直接使用list.sort()。

结构体需要重载 < 运算符。

2.5 插入

• push_front()：增加到头部位置
• push_back()：增加到尾部位置
• insert(it, k)：增加到it位置，原来的往后移动
  • 返回值是新插入的首位

li.push_back(1); //1
li.push_front(2); //2 1
list<int>::Iterator it = li.begin(); //it指向2
it++; //it指向1
li.insert(it, 10); //2 10 1，注意此时it还是指向1
it = li.insert(it, 20); //2 10 20 1，注意此时it返回了插入的20
it.insert(it, 30); //2 10 30 20 1

2.6 删除

• pop_front()：删除首位
• pop_back()：删除尾部
• clear()：清空所有
• erase(it)：删除it所在位置，返回下一个位置的迭代器
• remove(k)：删除所有等于k的元素，如果结构体要重载 ==

注意：用迭代器遍历时，erase函数会使得迭代器失效，需要重置it = li.erase(it)。

3、数组实现

3.1 设计思路

以双向链表为例子，用三个数组：

• val[N]存储元素
• L[N]存储每个元素（val下标）的前趋元素（val下标）
• R[N]存储每个元素（val下标）的后趋元素（val下标）

双向链表需要能得到头和尾，因此可用head和tail两个变量来存储头尾，但这样当头尾插入新元素时就需要更新变量。

有一种方法就是在val中固定两个位置用来放头、尾位置（开区间）：

• HEAD：固定下标，令R[HEAD]为链表的第一个元素下标
• TAIL：固定下标，令L[TAIL]为链表的最后一个元素下标
• 例如数据<=10^5时，定义HEAD=10^5+1, TAIL=10^5+2

const int N=1e5+10, HEAD=1e5+1, TAIL=1e5+2;
int val[N], L[N], R[N];
void init() {//初始化，空链表
  R[HEAD] = tail;
  L[tail] = HEAD;
}

3.2 遍历

以正向遍历为例：

for(int i=R[HEAD]; i!=TAIL; i = R[i])
  cout<<val[i]<<" ";

3.3 删除

如果要删除某个位置（val下标k），实际就是将k的前趋指向后趋，后趋指向前趋，也就是将k摘出来。

R[L[k]] = R[k];
L[R[k]] = L[k];

L[k] = R[k] = 0;//用来后续判断是否已被删除

3.4 新增

新增一般有四种场景：

• 头插入：做为新的头，指向原来的头（双向）
• 尾插入：做为新的尾，原来的尾指向它（双向）
• 某元素左侧插入
• 某元素右侧插入

可以统一成一个左侧插入的insert方法：

void insert(int k, int x) {
  val[++last] = x;

  R[L[k]] = last;//和前趋点
  L[last] = L[k];
  
  L[k] = last;//和后趋点
  R[last] = k;
}

四种场景的调用如下：

• 头插入：insert(R[HEAD], x)
• 尾插入：insert(TAIL, x)
• 左侧插入：insert(k, x)
• 右侧插入：insert(R[k], x)