C++ STL- list 的使用以及练习

这篇具有很好参考价值的文章主要介绍了C++ STL- list 的使用以及练习。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

C++ STL- list 的使用以及练习,C++,数据结构,c++,开发语言,c语言,visual studio code,数据结构,list,visualstudio

目录

0.引言

1. list 介绍 

2. list 使用

2.1 构造函数

2.2 list iterator 的使用 

3 list capacity 

4. list element access 

5. list modifiers 

6. list 迭代器失效 

7. list 与vector 对vector

8. OJ 题讲解 

删除链表的倒数第 N  个节点:


0.引言

本篇博客我们将介绍 STL 中 list 的使用,由于list STL 接口函数与之前vector string 类似,我们在这里将不再详细赘述了,通过 OJ 题来练习 list 的实际使用。

1. list 介绍 

(1). list是可以在常数范围内在任意位置进行插入和删除的序列式容器,该容器可以前后双向迭代。

(2). list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节点中,在节点中通过指针指向 其前一个元素和后一个元素。

(3). list与forward_list非常相似:最主要的不同在于forward_list是单链表,只能朝前迭代,已让其更简单高效。

(4). 与其他的序列式容器相比(array,vector,deque),list通常在任意位置进行插入、移除元素的执行效率更好。

(5). 与其他序列式容器相比,list和forward_list最大的缺陷是不支持任意位置的随机访问,比如:要访问list 的第6个元素,必须从已知的位置(比如头部或者尾部)迭代到该位置,在这段位置上迭代需要线性的时间 开销;list还需要一些额外的空间,以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)。

2. list 使用

2.1 构造函数

构造函数:constructor 说明
list (size_type n, const value_type& val = value_type()) 构造的list中包含n个值为val的元素
list() 构造空的list
list (const list& x) 拷贝构造函数
list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list

2.2 list iterator 的使用 

函数声明 说明
begin() + end() 返回第一个元素的迭代器+返回最后一个元素下一个位置的迭代器
rbegin() + rend() 返回第一个元素的reverse_iterator,即end位置,返回最后一个元素下一个位置的 reverse_iterator,即begin位置

 这里可以将将迭代器理解成一个指针,该指针指向list中的某个节点。

(1).  begin与end为正向迭代器,对迭代器执行++操作,迭代器向后移动

(2).  rbegin(end)与rend(begin)为反向迭代器,对迭代器执行++操作,迭代器向前移动

3 list capacity 

函数声明 说明
empty 检测list是否为空,是返回true,否则返回false
size 返回list中有效节点的个数

4. list element access 

函数声明 说明
front 返回list的第一个节点中值的引用
back 返回list的最后一个节点中值的引用

5. list modifiers 

函数声明 说明
push_front 在list首元素前插入值为val的元素
pop_front 删除list中第一个元素
push_back 在list尾部插入值为val的元素
pop_back 删除list中最后一个元素
insert 在list position 位置中插入值为val的元素
erase 删除list position位置的元素
swap 交换两个list中的元素
clear 清空list中的有效元素

6. list 迭代器失效 

迭代器失效即迭代器所指向的节点的无效,即该节 点被删除了。因为list的底层结构为带头结点的双向循环链表,因此在list中进行插入时是不会导致list的迭代 器失效的,只有在删除时才会失效,并且失效的只是指向被删除节点的迭代器,其他迭代器不会受到影响。

int Array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
list<int> l(Array, Array + sizeof(Array) / sizeof(int));

auto it = l.begin();
while (it != l.end())
{
	// erase()接口被执行后,it所指向的节点已被删除,导致it迭代器无效,在下一次使用时,必须重新赋值
	l.erase(it);
	++it;
}

 C++ STL- list 的使用以及练习,C++,数据结构,c++,开发语言,c语言,visual studio code,数据结构,list,visualstudio

正确写法: 

int Array[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
list<int> l(Array, Array + sizeof(Array) / sizeof(int));

auto It = l.begin();
while (It != l.end())
{
	// erase()接口被执行后,对It重新赋值
	l.erase(It++); // It = l.erase(It) -- 后置++先使用后自增
}

7. list 与vector 对vector

vector list
底层结构 动态顺序表,一段连续空间 带头结点的双向循环链表
随机访问 支持随机访问,访问某个元素效率O(1) 不支持随机访问,访问某个元素 效率O(N)
插入和删除 任意位置插入和删除效率低,需要搬移元素,时间复杂 度为O(N),插入时有可能需要增容,增容:开辟新空 间,拷贝元素,释放旧空间,导致效率更低 任意位置插入和删除效率高,不 需要搬移元素,时间复杂度为 O(1)
空间利用率 底层为连续空间,不容易造成内存碎片,空间利用率 高,缓存利用率高 底层节点动态开辟,小节点容易 造成内存碎片,空间利用率低, 缓存利用率低
迭代器 原生态指针 对原生态指针(节点指针)进行封装
迭代器失效 在插入元素时,要给所有的迭代器重新赋值,因为插入 元素有可能会导致重新扩容,致使原来迭代器失效,删 除时,当前迭代器需要重新赋值否则会失效 插入元素不会导致迭代器失效, 删除元素时,只会导致当前迭代 器失效,其他迭代器不受影响
使用场景 需要高效存储,支持随机访问,不关心插入删除效率 大量插入和删除操作,不关心随 机访问

8. OJ 题讲解 

删除链表的倒数第 N  个节点:

给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。 

C++ STL- list 的使用以及练习,C++,数据结构,c++,开发语言,c语言,visual studio code,数据结构,list,visualstudio

 我们以示例为例来做分析,为完成题目要求,我们只需要将 3 指向 5 即可。C++ STL- list 的使用以及练习,C++,数据结构,c++,开发语言,c语言,visual studio code,数据结构,list,visualstudio

那么我们如何确定倒数第 n 个 节点的位置呢? 我i们只需要定义两个快慢指针,让快指针先走 n 步,然后再让快慢指针同时走,当快指针走到最后的一个节点时,那么慢指针指向的位置即为倒数第 n-1 个位置,刚好方便删除操作,最后为了方便返回头节点,我们可以提前开辟一个哨兵位,哨兵位指向头节点即可。

 C++ STL- list 的使用以及练习,C++,数据结构,c++,开发语言,c语言,visual studio code,数据结构,list,visualstudioC++ STL- list 的使用以及练习,C++,数据结构,c++,开发语言,c语言,visual studio code,数据结构,list,visualstudio

接着我们来看代码: 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) 
    {
         ListNode* sentinel = new ListNode(0);  
         sentinel->next = head;
         ListNode* slow = sentinel;
         ListNode* fast = sentinel;
         while(n--)
            fast = fast->next;

         while(fast->next)
         {
            fast = fast->next;
            slow = slow->next;
         }
         slow->next = slow->next->next;

         return sentinel->next;  
    }
};

C++ STL- list 的使用以及练习,C++,数据结构,c++,开发语言,c语言,visual studio code,数据结构,list,visualstudio

复杂度分析: 

快慢指针实则只遍历一次,时间复杂度 O(n), 只申请了有几个变量,空间复杂度 O(1) 。文章来源地址https://www.toymoban.com/news/detail-843607.html

到了这里,关于C++ STL- list 的使用以及练习的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • [JAVA数据结构] 认识 Iterable、Collection、List 的常见方法签名以及含义

            (一)Iterable                 1. 介绍                 2. 常见方法         (二)Collection                 1. 介绍                  2. 常见方法         (三) List                  1. 介绍                 2. 常见方法

    2024年02月02日
    浏览(8)
  • 【每日算法 && 数据结构(C++)】—— 01 | 平方值去重统计(解题思路STL法,双指针法、流程图、代码片段)

    “Success is not final, failure is not fatal: It is the courage to continue that counts.” - Winston Churchill (成功并非终点,失败并非致命:真正重要的是继续前行的勇气 - 温斯顿·丘吉尔) 给你一个整数数组,数组中的数可以是正数、负数、零,请实现一个函数,返回这个数组中所有数的平方

    2024年02月12日
    浏览(15)
  • 【C++进阶(五)】STL大法--list模拟实现以及list和vector的对比

    💓博主CSDN主页:杭电码农-NEO💓   ⏩专栏分类:C++从入门到精通⏪   🚚代码仓库:NEO的学习日记🚚   🌹关注我🫵带你学习C++   🔝🔝 本篇文章立足于上一篇文章: list深度剖析(上) 请先阅读完上一篇文章后再阅读这篇文章! 本章重点: 本章着重讲解list的模拟实现 list模拟实

    2024年02月09日
    浏览(12)
  • 【C++】STL——list介绍及使用

    🚀 作者简介:一名在后端领域学习,并渴望能够学有所成的追梦人。 🚁 个人主页:不 良 🔥 系列专栏:🛸C++  🛹Linux 📕 学习格言:博观而约取,厚积而薄发 🌹 欢迎进来的小伙伴,如果小伙伴们在学习的过程中,发现有需要纠正的地方,烦请指正,希望能够与诸君一同

    2024年02月12日
    浏览(32)
  • C++ [STL之list的使用]

    本文已收录至《C++语言》专栏! 作者:ARMCSKGT vector是一片连续的空间,在数据访问上性能较好,但是任意位置插入删除性能较低,头插头删性能亦是如此;此时在这种需要频繁插入的场景下,显然链表是一种更好的选择,STL中实现了带头双选循环链表,本次我们来介绍该如何

    2024年02月07日
    浏览(9)
  • C++ STL学习之【list的使用】

    ✨个人主页: 北 海 🎉所属专栏: C++修行之路 🎊每篇一句: 图片来源 A year from now you may wish you had started today. 明年今日,你会希望此时此刻的自己已经开始行动了。 STL 中的 vector 存在头部及中部操作效率低的缺陷,需要另一种容器来弥补其短板,此时 list 就应运而生,

    2023年04月16日
    浏览(7)
  • C++数据结构之查找——静态查找表(顺序查找、折半查找、分块查找 带有gif以及图示)

    目录 一、查找的相关概念介绍 1.查找表(Search Table) 概念 对查找表的操作 查找表的分类 2.(Key) 概念 3.查找(Searching) 概念 4.衡量查找算法的标准 1.时间复杂度 2.空间复杂度 3.平均查找长度(ASL) 二、静态查找表 1.顺序查找 算法思路 算法举例 算法性能分析 不等概率

    2024年02月03日
    浏览(12)
  • stl_list类(使用+实现)(C++)

    list是一个可以在常熟范围内任意位置进行插入和删除的序列式容器。 底层是带头双向循环链表 (链接中有对带头双向循环链表的逻辑分析)。 (constructor)构造函数声明 接口说明 list() 无参构造 list(size_type n, const T val = T() 构造并初始化n个val list(const list x) 拷贝构造 list(InputI

    2024年02月14日
    浏览(12)
  • STL 之 list接口的简单使用【C++】

    ![在这里插入图片描述](https://img-blog.csdnimg.cn/717807397d8d499d840aae2e3127f467.png 将文档翻译提炼得到以下结论 list是可以在常数范围内在任意位置进行插入和删除的序列式容器,并且该容器可以前后双向迭代。 list的底层是双向链表结构,双向链表中每个元素存储在互不相关的独立节

    2024年02月13日
    浏览(18)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包