list基础知识

list

1.list 的定义和结构

list 是双向链表，是C++的容器模板，其接收两个参数，即 list(a,b) 其中 a 表示指定容器中存储的数据类型，b 表示用于分配器内存的分配器类型，默认为 list <int>;
list 的特点：

双向性：由于是双向链表，每个节点都包含前一个节点和后一个节点的指针，故此可以在 O(1) 内实现对某个元素的插入、删除，但对于访问读取来讲就需要 O(n) 的时间；

动态大小：类似于 vector ，其大小也会随着需求扩展或收缩，无需提前定义容器的大小；

不连续存储：list 的存储与数组不同，是离散的，节点之间的联系为双向的指针；

#include <iostream>
#include <list>
using namespace std;int main()
{list <int> mylist;mylist.push_back(1);mylist.push_back(2);mylist.push_back(3);mylist.push_front(0);	//可以双向访问故此可以使用push_front()；for(auto num : mylist)cout << num << ' ';return 0;
}

- list 为双向链表，插入删除的时间复杂度为 O(1) ,而访问和查找的操作的时间复杂度则为 O(n) 其中n为链表长度；
  
  如若需要大量进行访问查找的操作，则更加推荐使用 vector 或者 deque（双端队列，由vector实现）

2.list 的常用函数

1）push_back( ) 和 push_front( ) 用来向 list 的尾端或者首端插入一个元素；

2）pop_back() 和 pop_front() 用来去除 list 的尾端或者首端一个元素，在使用前要先判断 list 是否为空；

3）size() 返回 list 此时存有的元素个数；

4）empty( ) 用来检查 list 是否为空；

5）clear( ) 用来清空 list 的所有元素；

#include <iostream>
#include <list>
using namespace std;int main()
{list <int> mylist;mylist.push_back(1);mylist.push_back(2);mylist.push_back(3);mylist.push_front(0);for(auto num : mylist)cout << num << ' ';cout << '\n' << "第一个元素是：" << mylist.front(); return 0;
}

6）front( ) 和 back( ) 用来返回 list 里面第一个元素或最后一个元素的的引用；

#include <iostream>
#include <list>
using namespace std;int main()
{list <int> mylist;mylist.push_back(1);mylist.push_back(2);mylist.push_back(3);mylist.push_front(0);mylist.front() ++;for(auto num : mylist)cout << num << ' ';cout << '\n' << "第一个元素是：" << mylist.front(); return 0;
}

7）begin() 和 end() 指向链表起始元素或者最后一个元素下一个位置的迭代器；

8）insert( ) 和 erase( ) 表示在指定位置之前插入或者移除一个或多个元素（需要逐个确认，故此为 O(n) 的时间复杂度）；

#include <iostream>
#include <list>
using namespace std;int main()
{list <int> mylist;mylist.push_back(1);mylist.push_back(2);mylist.push_back(3);mylist.insert(++ mylist.begin(),0);	 //insert()是将第二个参数插入在在第一个参数指向位置的左侧mylist.erase(++ ++ mylist.begin(),-- mylist.end());//if(mylist.empty())	cout << "yes" << '\n';for(auto num : mylist)cout << num << ' ';return 0;
}