上QQ阅读APP看书，第一时间看更新
2.9 list双向链表容器
list容器实现了双向链表的数据结构，数据元素是通过链表指针串连成逻辑意义上的线性表，这样，对链表的任一位置的元素进行插入、删除和查找都是极快速的。图2-7是list采用的双向循环链表的结构示意图。
图2-7 list采用的双向循环链表的结构示意图
list的每个节点有三个域：前驱元素指针域、数据域和后继元素指针域。前驱元素指针域保存了前驱元素的首地址；数据域则是本节点的数据；后继元素指针域则保存了后继元素的首地址。list的头节点的前驱元素指针域保存的是链表中尾元素的首地址，而list的尾节点的后继元素指针域则保存了头节点的首地址，这样，就构成了一个双向循环链。
由于list对象的节点并不要求在一段连续的内存中，所以，对于迭代器，只能通过“++”或“- -”的操作将迭代器移动到后继/前驱节点元素处。而不能对迭代器进行+n或-n的操作，这点，是与vector等不同的地方。
使用list需要声明头文件包含“#include <list>”, list文件在C:\Program Files\Microsoft Visual Studio\VC98\Include文件夹中。
2.9.1 创建list对象
（1）创建空链表，如：
list<int> l;
（2）创建具有n个元素的链表，如：
list<int> l（10）; //创建具有10个元素的链表
2.9.2 元素插入和遍历
有三种方法往链表里插入新元素：
（1）采用push_back()方法往尾部插入新元素，链表自动扩张。
（2）采用push_front()方法往首部插入新元素，链表自动扩张。
（3）采用insert()方法往迭代器位置处插入新元素，链表自动扩张。注意，迭代器只能进行“++”或“- -”操作，不能进行+n或-n的操作，因为元素的位置并不是物理相连的。
采用前向迭代器iterator对链表进行遍历。
下面的程序详细说明了如何对list进行元素插入和遍历。
#include <list>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义元素为整型的list对象，当前没有元素
list<int> l;
//在链表尾部插入新元素，链表自动扩张
l.push_back(2);
l.push_back(1);
l.push_back(5);
//在链表头部插入新元素，链表自动扩张
l.push_front(8);
//在任意位置插入新元素，链表自动扩张
list<int>::iterator it;
it=l.begin();
it++; //注意，链表的迭代器只能进行++或--操作，而不能进行+n操作
l.insert(it,20);
//使用前向迭代器遍历链表
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
8 20 2 1 5
2.9.3 反向遍历
采用反向迭代器reverse_iterator对链表进行反向遍历。
#include <list>
#include <iostream>
4using namespace std;
int main(int argc, char * argv[])
{
//定义元素为整型的list对象，当前没有元素
list<int> l;
//在链表尾部插入新元素，链表自动扩张
l.push_back(2);
l.push_back(1);
l.push_back(5);
//反向遍历链表
list<int>::reverse_iterator rit;
for(rit=l.rbegin(); rit! =l.rend(); rit++)
{
cout<<*rit<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
5 1 2
2.9.4 元素删除
（1）可以使用remove()方法删除链表中一个元素，值相同的元素都会被删除。
#include <list>
#include <iostream>
using namespace std;
int main0028int argc, char * argv[])
{
//定义元素为整型的list对象，当前没有元素
list<int> l;
//在链表尾部插入新元素，链表自动扩张
l.push_back(2);
l.push_back(1);
l.push_back(5);
l.push_back(1);
//遍历链表
list<int>::iterator it;
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
//删除值等于1的所有元素
l.remove(1);
//遍历链表
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果
2 1 5 1
2 5
（2）使用pop_front()方法删除链表首元素，使用pop_back()方法删除链表尾元素。
#include <list>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义元素为整型的list对象，当前没有元素
list<int> l;
//在链表尾部插入新元素，链表自动扩张
l.push_back(2);
l.push_back(8);
l.push_back(1);
l.push_back(5);
l.push_back(1);
//遍历链表
list<int>::iterator it;
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
//删除首元素
l.pop_front();
//删除尾元素
l.pop_back();
//遍历链表
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
2 8 1 5 1
8 1 5
（3）使用erase()方法删除迭代器位置上的元素。
#include <list>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义元素为整型的list对象，当前没有元素
list<int> l;
//在链表尾部插入新元素，链表自动扩张
l.push_back(2);
l.push_back(8);
l.push_back(1);
l.push_back(5);
l.push_back(1);
//遍历链表
list<int>::iterator it;
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
//删除第2个元素（从0开始计数）
it=l.begin();
it++;
it++;
l.erase(it);
//遍历链表
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
2 8 1 5 1
2 8 5 1
（4）使用clear()方法清空链表。
#include <list>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义元素为整型的list对象，当前没有元素
list<int> l;
//在链表尾部插入新元素，链表自动扩张
l.push_back(2);
l.push_back(8);
l.push_back(1);
l.push_back(5);
l.push_back(1);
//遍历链表
list<int>::iterator it, it2;
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
//清空链表
l.clear();
//打印链表元素个数
cout<<l.size()<<endl;
return 0;
}
运行结果：
2 8 1 5 1
0
2.9.5 元素查找
采用find()查找算法可以在链表中查找元素，如果找到该元素，返回的是该元素的迭代器位置；如果没有找到，则返回end()迭代器位置。
find()算法需要声明头文件包含语句“#include <algorithm>”。
#include <list>
#include <iostream>
#include <algorithm>
using namespace std;
int main(int argc, char * argv[])
{
//定义元素为整型的list对象，当前没有元素
list<int> l;
//在链表尾部插入新元素，链表自动扩张
l.push_back(2);
l.push_back(8);
l.push_back(1);
l.push_back(5);
l.push_back(1);
//遍历链表
list<int>::iterator it, it2;
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
//采用find()查找算法在链表中查找
it=find(l.begin(), l.end(),5);
if(it! =l.end())//找到
{
cout<<"find it"<<endl;
}
else
{
cout<<"not find it"<<endl;
}
it=find(l.begin(), l.end(),10);
if(it! =l.end())//找到
{
cout<<"find it"<<endl;
}
else
{
cout<<"not find it"<<endl;
}
return 0;
}
运行结果：
2 8 1 5 1
find it
not find it
2.9.6 元素排序
采用sort()方法可以对链表元素进行升序排列。
#include <list>
#include <iostream>
using namespace std;
int main(int argc, char * argv[])
{
//定义元素为整型的list对象，当前没有元素
list<int> l;
//在链表尾部插入新元素，链表自动扩张
l.push_back(2);
l.push_back(8);
l.push_back(1);
l.push_back(5);
l.push_back(1);
//遍历链表
list<int>::iterator it, it2;
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
//使用sort()方法对链表排序，是升序排列
l.sort();
//遍历链表
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
2 8 1 5 1
1 1 2 5 8
2.9.7 剔除连续重复元素
采用unique()方法可以剔除连续重复元素，只保留一个。
#include <list>
#include <iostream>
using namespa4ce std;
int main(int argc, char * argv[])
{
//定义元素为整型的list对象，当前没有元素
list<int> l;
//在链表尾部插入新元素，链表自动扩张
l.push_back(2);
l.push_back(8);
l.push_back(1);
l.push_back(1);
l.push_back(1);
l.push_back(5);
l.push_back(1);
//遍历链表
list<int>::iterator it, it2;
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
//剔除连续重复元素（只保留一个）
l.unique();
//遍历链表
for(it=l.begin(); it! =l.end(); it++)
{
cout<<*it<<" ";
}
//回车换行
cout<<endl;
return 0;
}
运行结果：
2 8 1 1 1 5 1
2 8 1 5 1