入门级-数据结构-链表

# 链表

|例题|
|----|
|[维护序列](http://39.99.183.126:8888/p/CCFPB06D04)|

---

#### 1、链表结构

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

![](https://cdn.itbegin.com//pics/admin/2020/9/8d6915553d06458b9c379b892fa0046f.jpg)

---

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

* 用数组的值来指向下一个节点的位置
* 用结构体的字段指向下一个节点的位置
* 用结构体的字段指针指向下一个节点
* 用STL的forward_list、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)。

---

## 例题
[abc278a A-Shift](http://39.99.183.126:8888/p/abc278a)

---

```c++
#include<iostream>
#include<cstdio>
#include<list>
using namespace std;
list<int>ml;
int main(void)
{
    int n, t, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++)
    {
        cin >> t;
        ml.push_back(t);
    }
    for(int i = 0; i < k; i++)
    {
        ml.push_back(0);
        ml.erase(ml.begin());
    }
    for(auto c:ml) cout << c << " ";
    return 0;
}
```

---

#### 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)

---
|练习题|
|----|
|[操作车厢](http://39.99.183.126:8888/p/CCFPB06E02)|