list容器链表

一、链表特性

（1） 链表是由一系列的结点组成，结点包含两个域，一个数据域，一个指针域。 （2） 链表内存是非连续的，因此添加或删除元素，时间复杂度都是常数项，不需要移动元素，比数组添加删除效率高。 （3） 链表只有在需要的时候，才分配内存。 （4） 链表，只要拿到第一个结点，相当于拿到整个链表。 （5） 链表需要额外的空间保存结点的关系：前驱、后继关系。

二、链表和数组区别：

（1） 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。 （2） 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据元素。（数组中插入、删除数据项时，需要移动其他数据项）

三、list容器（链表）各种操作

（1）操作函数释义：

sort 支持可随机访问的容器

（2）重点操作实例

#include<iostream> #include<list> using namespace std; void printlist(list<int>& v) { for (list<int>::iterator it = v.begin(); it != v.end(); ++it) { cout << *it << " "; }cout << endl; } //初始化 void test01() { list<int>mlist1; list<int>mlist2(10, 10);//有参构造用十个10去初始化 list<int>mlist3(mlist2);//拷贝构造 list<int>mlist4(mlist2.begin(), mlist2.end()); printlist(mlist4); } //list容器插入、删除 void test02() { list<int>mlist; mlist.push_back(100); mlist.push_front(200); mlist.push_front(200); mlist.push_front(200); //插入 mlist.insert(mlist.begin(), 300); mlist.insert(mlist.begin(), 200); mlist.insert(mlist.end(), 400); list<int>::iterator it = mlist.begin(); //it+2 //这样表示是错误，只能说给it两次++； it++; it++; mlist.insert(it, 500); printlist(mlist); //删除 mlist.remove(200);//删除数据中的所有200； printlist(mlist); mlist.pop_back();//删尾 mlist.pop_front();//删头 mlist.erase(mlist.begin(), mlist.end());//从开始到结尾删除相当于 ：mlist.clear(); printlist(mlist); } //赋值初始化 void test03() { list<int>mlist; mlist.assign(10, 10);//用十个10初始化 printlist(mlist); list<int>mlist2; mlist2 = mlist;//对mlist来初始化 printlist(mlist2);//10 10 10 10 10 10 10 10 10 10 list<int>mlist3; mlist3.assign(5, 8); //8 8 8 8 8 mlist.swap(mlist3);//将mlist3的数据和mlist 的数据互相交换 printlist(mlist);//8 8 8 8 8 printlist(mlist3);//10 10 10 10 10 10 10 10 10 10 } //翻转 void test04() { list<int>mlist; for (int i = 0; i < 10; ++i) { mlist.push_back(i); } printlist(mlist);//0 1 2 3 4 5 6 7 8 9 mlist.reverse();//实现链表的翻转 printlist(mlist);//9 8 7 6 5 4 3 2 1 0 } //排序 bool mycompare(int v1, int v2); void test05() { list<int>mlist; mlist.push_back(1); mlist.push_back(7); mlist.push_back(5); mlist.push_back(3); printlist(mlist);//1 7 5 3 mlist.sort();//默认从小到大 printlist(mlist);//1 3 5 7 mlist.sort(mycompare);//要想实现从大到小，那么加入规则即可 printlist(mlist);//7 5 3 1 } bool mycompare(int v1, int v2) { return v1 > v2; } int main(void) { //test01(); //test02(); //test03(); //test04(); test05(); return 0; }

链表的功能还是十分强大，如果完全掌握了，不管是实现一些函数或者是我们在做面试题的时候都会让我们事半功倍，让代码看起来更简洁，逻辑表达更清晰。