List

链表也是个常用的数据结构，它是一种物理存储单元上非连续非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针实现的。

链表由一系列结点组成，每个结点包含两个部分：数据以及指向下一结点的指针。

而标准数据库STL中的List是双向链表，既可以指向下一个结点也可以指向上一个结点，这样使得正向遍历和反向遍历都很方便。也可以快速的进行插入和删除操作。图片来自

一、List的声明/定义

list<数据类型> 链表名称，例：list<int> list1;

二、List的遍历/访问

迭代器法

list<数据类型>::iterator 迭代器名称，例:list<int>::iterator iter1;

常用函数

iter1=list1.begin();      //返回指向容器中第一个元素的迭代器
iter1=list1.end();        //返回容器中最后一个元素的迭代器
iter1=list1.rbegin();     //返回指向容器中最后一个元素的反向迭代器
iter1=list1.rend();       //返回容器中第一个元素的反向迭代器

注：begin()和rbegin()是返回指向元素的迭代器，而end()和rend()是返回元素的迭代器，也就是说list1.end()和list1.rend()返回指向最后一个元素的下一个元素的迭代器，具体用法如下：

list<int> a;
a.push_front(8); 
a.push_front(6);
a.push_front(3);  
list<int>::iterator l1=a.begin();
for(l1=a.begin();l1!=a.end();l1++){
    cout<<*l1<<" ";
}
/*
结果(因为在插入元素时，用的是头插法)：
3 6 8 
*/

三、List类常见的类方法

例：list<int> list1;

1 添加元素

int x1=8;
list1.push_front(x1);       //在头部添加
list1.push_back(x1);        //在尾部添加
list1.insert(pos,elem);     //在pos(迭代器)位置插elem元素的拷贝，返回新数据的位置。
list1.insert(pos,n,elem);   //在pos(迭代器)位置插入n个elem数据，无返回值。
list1.insert(pos,beg,end);  //在pos(迭代器)位置插入[beg,end)区间的数据，无返回值。

2 删除元素

list1.pop_front();       //删除头部元素
list1.pop_back();        //删除尾部元素
list1.clear();           //删除所有元素
list1.erase(begin,end);  //删除[begin,end)区间（迭代器）的数据，返回下一个数据的位置。
list1.erase(pos);        //删除pos(迭代器)位置的数据，返回下一个数据的位置。
list1.remove(elem);      //删除容器中所有与elem匹配的元素。

3 List容量

list1.size();            //返回元素个数
list1.max_size();        //返回对象最大允许容量
list1.empty();           //得到容器是否为空，为空返回true(1)，否则返回false(0)
list1.resize(num);       //重新指定容器的长度为num，若容器变长，则以默认值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。
list1.resize(num, elem); //重新指定容器的长度为num，若容器变长，则以elem值填充新位置。如果容器变短，则末尾超出容器长度的元素被删除。

4 其他

list1.unique();     //去重
list1.merge();      //合并两个有序链表
list1.sort();       //单链表排序
list1.reversr();    //单链表的逆置