list双向链表
STL中的list是一个双向循环链表,如下图所示:
使用list时必须先包含头文件
#include <list>
其中的list类型定义于namespace std中，是个class template:
namespace std {
template< typename T,
typename Allocator = allocator<T> >
class list;
}第一个参数是任何数据类型,第二个参数可有可无。
list对象自带两个指针,一个指向第一个元素,另一个指向最后一个元素。因此list在如下几个主要方面与array、 vector 或deque不同:
1.list不支持随机访问,如果你要访问第5个元素，就得顺着链表逐一遍历前 4个元素。所以，在list中随机访问任意元素是很缓慢的。然而访问第一个和最后一个元素的速度很快。
2.任何位置(不只两端)插入和删除都非常快，在常量时间内完成,因为无须移动其他元素。只需要进行一些指针操作。
list提供的比较好用的函数:
1.list提供front,push_front,pop_front和back,push_back,pop_back等函数
2.由于不支持随机访问,list即不支持下标操作也不支持at函数。
3.list提供不少特殊成员函数,专门用于移动和删除元素,和同名的STL通用算法相比,这些函数执行起来更快速,优先使用list自己提供的算法。
定义及初始化
下表列出定义list对象的常用初始化方法。
#include <iostream>
#include <list>
using namespace std;
//输出链表元素的值
void Show(const list<int>& l)
{
for (auto x : l)
cout << x << " ";
cout << endl;
}
int main()
{
list<int> l1; //空链表
list<int> l2(2); //包含两个默认元素值的链表
list<int> l3(3, 4); //包含3个4的链表
list<int> l4{ 1,2,3,4 };//包含1,2,3,4的链表
list<int> l5(l4); //把l4的值赋值给l5
cout << "l1:"; Show(l1);//输出l1的元素
cout << "l2:"; Show(l2);//输出l2的元素
cout << "l3:"; Show(l3);//输出l3的元素
cout << "l4:"; Show(l4);//输出l4的元素
cout << "l5:"; Show(l5);//输出l5的元素
return 0;
}
list常用迭代器
list支持双向迭代器(不支持随机迭代器),所以STL中需要随机迭代器的算法不能用于list,例如sort。不过list自带sort算法。
list常用的迭代器如下:
例如,利用迭代器访问list对象。
#include <iostream>
#include <list>
using namespace std;
int main()
{
list<int>l{ 1, 2, 3, 4, 5 };
//从头到尾输出链表元素
cout << "从头到尾输出:";
for (list<int>::const_iterator it = l.cbegin(); it != l.cend(); ++it)
cout << *it << " ";
cout << endl;
//把所有元素值+10
for (auto it = l.begin(); it != l.end(); ++it)
*it += 10;
//从尾到头输出链表元素
cout << "从尾到头输出:";
for (auto it = l.crbegin(); it != l.crend(); ++it)
cout << *it << " ";
cout << endl;
//auto it = l.begin() + 1;//错误,不是随机迭代器不能+1或-1,但可以++,--
cout << "从尾到头输出(少一个):";
for (auto it = --l.end(); it != l.begin(); --it)//这段代码不好,仅仅为了演示--
cout << *it << " ";
cout << endl;
return 0;
}
请注意:
1.list迭代器不是随机迭代器,不能 + - 数字。例如上面。可以++,--。
2.list迭代器不能比较大小。可以==和!=。
list常用运算符
list类既支持常用的=,==,!=,< , >等运算符,也可以通过调用其成员函数来执行相应的操作。
下面列举了其常用的操作。
#include <iostream>
#include <list>
using namespace std;
//输出链表的所有数据
void Show(const list<int>& l)
{
for (auto x : l)
cout << x << " ";
cout << endl;
}
int main()
{
list<int> l1{ 1,2,3,4,5,6 };//创建包含1,2,3,4,5,6的链表
list<int>l2;//创建空链表
l2 = l1;//把l1的所有元素赋值给l2
cout << "l1:"; Show(l1);//输出l1所有元素值
cout << "l2:"; Show(l2);//输出l2所有元素值
if (l1 == l2)
cout << "l1 == l2" << endl;
l1.front() = 100;//把l1的第一元素改为100,等同下一行的代码
//int& x = l1.front(); x = 100;//把l1的第一元素改为100
cout << "l1:"; Show(l1);//输出l1所有元素值
cout << "l2:"; Show(l2);//输出l1所有元素值
if (l1 != l2)
cout << "l1 != l2" << endl;
if (l1 > l2)
cout << "l1 > l2" << endl;
else
cout << "l1 <= l2" << endl;
return 0;
}
list常用成员函数
下面列举list对象常用的成员函数.
push_front(头部插入),push_back(尾部插入)
#include <iostream>
#include <list>
using namespace std;
//输出链表的所有数据
void Show(const list<int>& l)
{
for (auto x : l)
cout << x << " ";
cout << endl;
}
int main()
{
list<int> l1;//定义一个空的链表
//头插1,2,3
l1.push_front(1);
l1.push_front(2);
l1.push_front(3);
//尾插10,20,30
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
cout << "l1:"; Show(l1);//输出l1的数据
return 0;
}
pop_front(头部删除),pop_back(尾部删除)
#include <iostream>
#include <list>
using namespace std;
//输出链表的所有数据
void Show(const list<int>& l)
{
for (auto x : l)
cout << x << " ";
cout << endl;
}
int main()
{
list<int> l1;//定义一个空的链表
//头插1,2,3
l1.push_front(1);
l1.push_front(2);
l1.push_front(3);
//尾插10,20,30
l1.push_back(10);
l1.push_back(20);
l1.push_back(30);
cout << "l1:";
Show(l1);//输出l1的数据
cout << "删除第一个元素:";
l1.pop_front();//删除第一个元素
Show(l1);
cout << "删除最后一个元素:";
l1.pop_back();//删除最后一个元素
Show(l1);
return 0;
}
insert成员函数
插入一个或多个元素。list插入元素时,不需要移动后面的数据,只需要修改几个指针,所以时间复杂度为常数。
#include <iostream>
#include <list>
using namespace std;
//输出链表的所有数据
void Show(const list<int>& l)
{
for (auto x : l)
cout << x << " ";
cout << endl;
}
int main()
{
list <int> l1{ 1, 2, 3 };//创建一个包含1,2,3的链表
list <int> l2{ 4, 5, 6 };//创建一个包含4,5,6的链表
list <int>::iterator Iter; //迭代器
cout << "l1:"; Show(l1);
cout << "l2:"; Show(l2);
Iter = l1.begin();
l1.insert(Iter, 100);//在开始位置插入数字100
cout << "l1:"; Show(l1);
Iter = l1.begin();
Iter++;
l1.insert(Iter, 2, 200);//在Iter位置插入2个100
cout << "l1:"; Show(l1);
//在l1的begin后面插入l2的所有元素,不包含l2的最后一个
l1.insert(++l1.begin(), l2.begin(), --l2.end());//最后一个迭代器不包含
cout << "l1:"; Show(l1);
l2.insert(l2.begin(), { 10,20,30 });//插入多个元素
cout << "l2:"; Show(l2);
return 0;
}
list特有成员函数
下面列举list特有的函数(相比vector)
merge特有成员函数
把两个链表的元素进行合并。注意合并的前提是原来两个链表必须按照合并的方法有序。默认升序合并。
#include <iostream>
#include <list>
using namespace std;
//输出链表的所有数据
void Show(const list<int>& l)
{
for (auto x : l)
cout << x << " ";
cout << endl;
}
int main()
{
list <int> l1{ 3, 4, 6 };
list <int> l2{ 2, 5, 7 };
cout << "l1:"; Show(l1);
cout << "l2:"; Show(l2);
l2.merge(l1); //把l1合并到l2中,默认升序合并,前提l1和l2必须升序有序
cout << "合并l1后" << endl;
cout << "l1:"; Show(l1);
cout << "l2:"; Show(l2);
cout << endl;
list <int> l3{ 20, 15, 12,11 };
list <int> l4{ 22, 15, 10 };
cout << "l3:"; Show(l3);
cout << "l4:"; Show(l4);
l4.merge(l3, greater<int>());//按降序合并,前提l3,l4必须降序有序
cout << "合并l3后" << endl;
cout << "l3:"; Show(l3);
cout << "l4:"; Show(l4);
return 0;
}
合并的前提是原有的两个链表是"有序的"(按照排序的规则),如果不符合前提条件结果是未定义的。如下代码:
int main()
{
list <int> l5{3, 4, 6};//升序
list <int> l6{2, 20, 7};//非升序
l5.merge(l6); //把l6合并到l5中,程序错误
return 0;
}
reverse特有成员函数
将所有的元素反序。
#include <iostream>
#include <list>
using namespace std;
//输出链表的所有数据
void Show(const list<int>& l)
{
for (auto x : l)
cout << x << " ";
cout << endl;
}
int main()
{
list <int> l1{ 1,2,3,4,5,6,7,8,9,10 };
cout << "l1:"; Show(l1);
l1.reverse();
cout << "反序后" << endl;
cout << "l1:"; Show(l1);
return 0;
}
splice特有成员函数
链表连结,把一个链表的元素连结到另一个链表中。它和merge的区别是:merge要求数据必须有序,而splice对数据没有要求。
#include <iostream>
#include <list>
using namespace std;
//输出链表的所有数据
void Show(const list<int>& l)
{
for (auto x : l)
cout << x << " ";
cout << endl;
}
int main()
{
list<int> l1{ 10, 11 };
list<int> l2{ 20, 21, 22 };
list<int> l3{ 30, 31 };
list<int> l4{ 40, 41, 42, 43 };
list<int>::iterator where_iter;
list<int>::iterator first_iter;
list<int>::iterator last_iter;
cout << "初始值:" << endl;
cout << "l1:"; Show(l1);
cout << "l2:"; Show(l2);
cout << "l3:"; Show(l3);
cout << "l4:"; Show(l4);
//连结整个链表
where_iter = l2.begin();
++where_iter; //在数据11位置处处理,这个迭代器在后面可以一直使用
l2.splice(where_iter, l1);
cout << "把l1连结到l2后" << endl;
cout << "l1 = "; Show(l1);
cout << "l2 = "; Show(l2);
//连结一个元素
first_iter = l3.begin();
l2.splice(where_iter, l3, first_iter);
cout << "把l3的第一个元素连结到l2后" << endl;
cout << "l3:"; Show(l3);
cout << "l2:"; Show(l2);
//连结一个区间
first_iter = l4.begin();
last_iter = l4.end();
++first_iter; //第二个
--last_iter; //倒数第二个
l2.splice(where_iter, l4, first_iter, last_iter);
cout << "把l4的区间数据连结到l2后:" << endl;
cout << "l4 = "; Show(l4);
cout << "l2 = "; Show(l2);
return 0;
}
在上面的代码中where_iter这个迭代器在代码中可以多次使用,是因为在插入或者删除(没有删除它本身)操作中list的迭代器不会失效(在vector中插入和删除操作都可能会让迭代器失效)。
unique特有成员函数
删除相邻且重复的值,只保留一个。
#include <iostream>
#include <list>
using namespace std;
//输出链表的所有数据
void Show(const list<int>& l)
{
for (auto x : l)
cout << x << " ";
cout << endl;
}
int main()
{
list <int> l1{ 1,1,2,2,4,4,3,3,3,3,0 };
list <int> l2{ -1,1,1,3,3,3,5,5,-1 };
cout << "l1:"; Show(l1);
cout << "l2:"; Show(l2);
cout << "删除过相邻且相同的数字后" << endl;
l1.unique();
l2.unique();
cout << "l1:"; Show(l1);
cout << "l2:"; Show(l2);
return 0;
}
注意:相同的值如果不相邻是不删除的。