【C++】STL 容器 - list 双向链表容器 ① ( 容器特点 | 容器操作时间复杂度 | 构造函数 )

韩曙亮

发布于 2023-12-26 10:06:19

2920

发布于 2023-12-26 10:06:19

文章被收录于专栏：韩曙亮的移动开发专栏韩曙亮的移动开发专栏

文章目录

一、 list 双向链表容器简介
- 1、容器特点
- 2、容器操作时间复杂度
- 3、遍历访问
- 5、头文件
二、 list 双向链表容器构造函数
- 1、默认无参构造函数
- 2、创建包含 n 个相同元素的 list 双向链表
- 3、使用初始化列表构造 list 双向链表
- 4、使用另外一个 list 容器构造 list 双向链表容器

一、 list 双向链表容器简介

1、容器特点

list 双向链表容器可以在任意位置高效的进行插入 / 删除元素 ;

list 双向链表容器的元素的指针 : 容器中的元素 , 包含 2 个指针 , 一个指向该元素的前驱 , 一个指向该元素的后继 ;

2、容器操作时间复杂度

list 双向链表容器操作时间复杂度 :

头部和尾部插入或删除元素的时间复杂度是 O(1) ;
表中间插入或删除元素 , 最坏情况可能需要移动 n 个元素 , 时间复杂度是 O(n) ;

3、遍历访问

迭代器 : list 双向链表容器提供了迭代器功能 , 可以使用迭代器遍历容器中的元素 ;

list 双向链表容器不能随机存储访问 , 也就是不能根据下标获取元素 , 不能使用 at() 函数和 [] 操作符访问容器中的元素 ;

5、头文件

使用 list 双向链表容器 , 需要导入 <list> 头文件 ;

#include <list>

二、 list 双向链表容器构造函数

list 双向链表容器常用操作 , 基本与 vector 相同 , 这里进行简单介绍 ;

1、默认无参构造函数

list 双向链表容器默认的无参构造函数 , 构造格式如下 :

list<T> lstT

在尖括号中的 T 泛型类型是 list 双向链表容器中存储的元素类型 ;

lstT 是双向链表容器的变量名 ;

该默认无参构造函数会创建空的 list 双向链表 ;

代码示例 :

#include "iostream"
using namespace std;
#include "list"

int main() {

	// 默认无参构造函数 会创建空的 list 双向链表

	// list 双向链表容器, 存储 int 类型元素
	list<int> lstInt;

	// list 双向链表容器, 存储 float 类型元素
	list<float> lstFloat;

	// list 双向链表容器, 存储 string 类型元素
	list<string> lstString;

	// 控制台暂停 , 按任意键继续向后执行
	system("pause");

	return 0;
};

执行结果 :

2、创建包含 n 个相同元素的 list 双向链表

创建包含 n 个相同元素的 list 双向链表 , 构造函数会将 n 个相同的元素拷贝到容器中 ;

函数原型如下 :

list(size_type n, const value_type& value = value_type(), const allocator_type& alloc = allocator_type());

该构造函数会创建一个包含 n 个元素的新列表 , 每个元素的值都初始化为 value ;

如果没有提供 value , 则元素初始化为默认值 , 使用提供的 alloc 来分配内存 ;

如 : 如果是 int 类型的元素 , 则初始化为 0 ;

代码示例 :

	// list 双向链表容器, 存储 3 个 int 类型元素 666
	list<int> lstInt(3, 666);

完整代码示例 :

#include "iostream"
using namespace std;
#include "list"

// 打印 list 容器内容
void printL(list<int>& lst) {
	// 获取迭代器起始位置
	list<int>::iterator it = lst.begin();

	cout << "list 容器内容 : ";

	// 循环判定, 如果没有迭代到最后一个元素的后一个位置, 那么一直循环
	while (it != lst.end())
	{
		// 获取元素值
		cout << *it << " ";
		// 迭代器指向下一个元素
		it++;
	}
	// 回车换行
	cout << endl;
}

int main() {

	// list 双向链表容器, 存储 3 个 int 类型元素 666
	list<int> lstInt(3, 666);

	// 打印 list 容器内容
	printL(lstInt);

	// 控制台暂停 , 按任意键继续向后执行
	system("pause");

	return 0;
};

执行结果 :

list 容器内容 : 666 666 666
请按任意键继续. . .

3、使用初始化列表构造 list 双向链表

使用初始化列表构造 list 双向链表函数原型如下 :

list(std::initializer_list<value_type> init, const allocator_type& alloc = allocator_type());

该构造函数会创建一个列表 , 其元素是从 init 初始化器列表复制的 ;

代码示例 :

	// list 双向链表容器 使用初始化列表构造
	list<int> lstInt{1, 2, 3, 4, 5};

完整代码示例 :

#include "iostream"
using namespace std;
#include "list"

// 打印 list 容器内容
void printL(list<int>& lst) {
	// 获取迭代器起始位置
	list<int>::iterator it = lst.begin();

	cout << "list 容器内容 : ";

	// 循环判定, 如果没有迭代到最后一个元素的后一个位置, 那么一直循环
	while (it != lst.end())
	{
		// 获取元素值
		cout << *it << " ";
		// 迭代器指向下一个元素
		it++;
	}
	// 回车换行
	cout << endl;
}

int main() {

	// list 双向链表容器 使用初始化列表构造
	list<int> lstInt{1, 2, 3, 4, 5};

	// 打印 list 容器内容
	printL(lstInt);

	// 控制台暂停 , 按任意键继续向后执行
	system("pause");

	return 0;
};

执行结果 :

list 容器内容 : 1 2 3 4 5
请按任意键继续. . .

4、使用另外一个 list 容器构造 list 双向链表容器

使用另外一个 list 容器构造 list 双向链表容器 , 有 3 种方式 :

参数为另一个 list 容器引用 : 构造函数会创建一个新的列表 , 它是另一个列表 other 的副本 ;

	list(const list& other);

	// list 双向链表容器 使用初始化列表构造
	list<int> lstInt{1, 2, 3, 4, 5};

	// 是 lstInt 的副本
	list<int> lstInt2 (lstInt);

参数为另一个 list 容器指定区间范围的迭代器 : 该构造函数会创建一个新的列表 , 其元素是从范围 [first, last) 复制的 , 注意是前闭后开区间 ; 这个范围可以是任何类型的输入迭代器 , 包括但不限于指针和 std::vector、std::deque 等容器的迭代器 ;

	list(InputIt first, InputIt last);

	// list 双向链表容器 使用初始化列表构造
	list<int> lstInt{1, 2, 3, 4, 5};

	// 注意是前闭后开区间
	list<int> lstInt3( ++lstInt.begin(), lstInt.end());

代码示例 :

#include "iostream"
using namespace std;
#include "list"

// 打印 list 容器内容
void printL(list<int>& lst) {
	// 获取迭代器起始位置
	list<int>::iterator it = lst.begin();

	cout << "list 容器内容 : ";

	// 循环判定, 如果没有迭代到最后一个元素的后一个位置, 那么一直循环
	while (it != lst.end())
	{
		// 获取元素值
		cout << *it << " ";
		// 迭代器指向下一个元素
		it++;
	}
	// 回车换行
	cout << endl;
}

int main() {

	// list 双向链表容器 使用初始化列表构造
	list<int> lstInt{1, 2, 3, 4, 5};

	// 是 lstInt 的副本
	list<int> lstInt2 (lstInt);

	// 注意是前闭后开区间
	list<int> lstInt3( ++lstInt.begin(), lstInt.end());

	// 打印 list 容器内容
	printL(lstInt);
	printL(lstInt2);
	printL(lstInt3);

	// 控制台暂停 , 按任意键继续向后执行
	system("pause");

	return 0;
};

执行结果 :

list 容器内容 : 1 2 3 4 5
list 容器内容 : 1 2 3 4 5
list 容器内容 : 2 3 4 5
请按任意键继续. . .

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2023-12-25，如有侵权请联系 cloudcommunity@tencent.com 删除

c++

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度