列表

List 是 C++ 内置的序列容器，支持非连续内存分配。我们说到 list 时，指的是双向链表。还有另一种叫作 forward list 的列表，指的是单向链表。 

下面来澄清一下。 
vector 数据结构支持连续内存分配，也就是说，每个元素在内存中都紧跟在前一个元素之后。
而链表 数据结构中的元素包含数据部分（实际值）和一个指针，指针中存储着列表中下一个元素的内存地址。

C++ 中有两种链表：

• 双向链表 ，list
• 单向链表 ，forward list

双向链表 和单向链表的主要区别是，单向链表只能向前遍历，也就是说，每个元素都有自己的值和下一个元素的内存地址。而双向链表 中的元素会保存定位列表中下一个元素和前一个元素所需的信息。

我们可以通过在文件中引入 list（双向链表）和 forward list（单向链表）来使用它们：

#include <list>
#include <forward_list>

或者，我们也可以只引入 bits/stdc++.h 头文件。

Forward List

首先，我们来介绍 forward list。它有很多方法，下面介绍其中最实用的几个。
声明 forward list 的方式和声明 vector 及 deque 完全一样。

forward_list<int> flist = {1, 2, 3};

我们可以使用 push_front() 方法添加元素，也可以使用 pop_front() 从头部移除元素。

flist.push_front(5);
for (int &x : flist) // 我们用每次迭代都会递增的指针输出元素
	cout << x << " ";
cout << endl;

flist.pop_front();
for (int &x : flist)
	cout << x << " ";

Output:
5 1 2 3
1 2 3

Forward List 方法

List

接下来是 list。list 数据结构也有很多方法，下面会介绍其中最实用的几个。 
首先，你将学习如何在 .cpp 文件顶部引入相关内容后声明 list 。 

list<int> list1 = {1, 2, 3};

我们可以使用 push_front() 或 push_back() 方法向列表中添加元素。
同样，我们可以分别使用 pop_front() 和 pop_back() 方法移除第一个和最后一个元素。

list1.push_back(4);
list1.push_front(0);
for (int &x : list1)
	cout << x << " ";
cout << endl;

list1.pop_front();
list1.pop_back();
for (int &x : list1)
	cout << x << " ";

Output:
0 1 2 3 4
1 2 3

List 方法