线性表 是一种常用的数据结构，其中的每一个元素（结点）都有唯一的前驱和唯一的后续。当然，第一个元素只有后续，最后一个元素只有前驱。
线性表一般分为“顺序表”和“链表”。顺序表可以简单理解成前面学过的数组。它是一种逻辑上和物理上都是有序的、连续存储的静态结构。链表是一种物理上不连续存储的动态结构，数据之间的逻辑顺序是通过链表中的指针链接关系实现的。
顺序存储结构的优缺点分析
优点：
A、 无需为表示结点间的逻辑关系而增加额外的存储空间;
B、 可方便地随机存取表中的任一元素。
缺点:
A、 插入或删除平均需要移动一半的结点；
B、 顺序表要求占用连续的存储空间。
问题：存储一个班的同学，人数不确定如何存储？
解决方法1:定义尽可能长的数组来存储！
解决方法2:利用链表来存储!
一、什么是链表（list）
list 是一个线性双向链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。
特点：
- list随机检索的性能非常的不好，因为它不像vector那样直接找到元素的地址，而是要从头一个一个的顺序查找。
- 但是它可以迅速地在任何节点进行插入和删除操作，因为list的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响。
- list支持双向迭代器，没有下标，必须使用迭代器遍历list。（由于不支持随机迭代器， 不能写迭代器+x,迭代器-x,不能用sort函数，但list拥有sort成员函数 ）。
二、list的常用函数
STL中的算法sort可以用来对 vector 和 deque 排序，它需要随机访问迭代器的支持。 因为list不支持随机访问迭代器，所以不能用算法sort对list容器排序。因此，list 容器引入了 sort成员函数以完成排序。
例子：list的使用
#include<iostream>
#include<list>
using namespace std;
void print(list<int> l){
list<int>::iterator it;
//注意：双向迭代器不支持+x (-x)的写法
for(it=l.begin();it!=l.end();it++){
cout<<*it<<" ";
}
cout<<endl;
}
int main(){
list<int> l1;
list<int> l2;
int a[10]={20,10,40,30,60,50};
list<int> l(a,a+5);
l.insert(l.begin(),16);
print(l);
l.remove(30);
print(l);
list<int>::iterator it=l.begin();
it++;it++;
l.insert(it,3,66);
print(l);
l.sort();
print(l);
return 0;
}