C++STL之list双向链表容器方式.docx
第
C++STL之list双向链表容器方式
目录1.list技术原理2.应用基础2.1元素的遍历访问2.2元素的插入2.3元素的反向遍历和删除2.4list的排序与归并总结不同于采用线性表顺序存储结构的vector和deque容器，list双向链表中任一位置的元素查找、插入和删除，都具有高效的常数阶算法时间复杂度O(1)。
1.list技术原理
为了支持前向和反向访问list容器的元素，list采用双向循环的链表结构组织数据元素，链表的每个节点包括指向前驱的指针、实际数据和指向后继的指针等数据域。
list的前向链，由头节点第1个节点第2个节点第n个节点头节点构成循环。
list的反向链，则由第n个节点第n-1个节点头节点第n个节点构成循环。n为list的节点个数，整个链表的存储位置由头指针指出，它指向头节点。
2.应用基础
list对象的创建，初始化赋值方法与vector相同，list的交换与deque相同，这里直接跳过。
2.1元素的遍历访问
由于链表中的数据需要一个个元素进行遍历，因此，list元素的遍历只使用迭代器的方式进行。
上代码：
#includeQCoreApplication
#includeiostream
#includelist
usingnamespacestd;
structStudent{
char*name;
intage;
char*city;
char*tel;
intmain(intargc,char*argv[])
QCoreApplicationa(argc,argv);
Students[]={
{符符,18,上海市,156624},
{介介,20,北京市,152534},
{贝贝,25,深圳市,453545},
//将数据插入链表
listStudent
l.push_back(s[0]);
l.push_back(s[1]);
l.push_back(s[2]);
//遍历打印链表元素
listStudent::iteratori,iend;
iend=l.end();
cout姓名年龄城市电话endl;
cout----------------------------endl;
for(i=l.begin();i!=iend;i++)
cout(*i).name;
cout(*i).age;
cout(*i).city;
cout(*i).telendl;
cout----------------------------endl;
returna.exec();
运行结果：
2.2元素的插入
由于list链表元素的插入不需要对其他元素进行移位拷贝，除了push_back函数在尾部添加元素外，list还提供了在链首插入元素的push_front函数和在任意迭代器位置的插入insert()函数。
#includeQCoreApplication
#includeiostream
#includelist
usingnamespacestd;
intmain(intargc,char*argv[])
QCoreApplicationa(argc,argv);
listint
l.push_back(6);
l.push_back(8);
l.push_back(9);
listint::iteratori,iend;
i=l.begin();
i++;
l.insert(i,7);//在6的后面插入7
l.push_front(5);//在链首插入5
iend=l.end();
for(i=l.begin();i!=iend;i++)
cout*i;
returna.exec();
输出结果：
2.3元素的反向遍历和删除
由于list容器的迭代器具有操作，因此也定义了反向迭代器。用反向迭代器来进行链表的遍历。
#includeQCoreApplication
#includeiostream
#includelist
usingnamespacestd;
intmain(intargc,char*argv[])