首页 > 代码库 > 4.lists(双向链表)
4.lists(双向链表)
一.概述
是一个线性链表结构，它的数据由若干个节点构成，每一个节点都包括一个信息块（即实际存储的数据）、一个前驱指针和一个后驱指针。它无需分配指定的内存大小且可以任意伸缩，这是因为它存储在非连续的内存空间中，并且由指针将有序的元素链接起来。由于其结构的原因，list 随机检索的性能非常的不好，因为它不像vector 那样直接找到元素的地址，而是要从头一个一个的顺序查找，这样目标元素越靠后，它的检索时间就越长。检索时间与目标元素的位置成正比。
虽然随机检索的速度不够快，但是它可以迅速地在任何节点进行插入和删除操作。因为list 的每个节点保存着它在链表中的位置，插入或删除一个元素仅对最多三个元素有所影响，不像vector 会对操作点之后的所有元素的存储地址都有所影响，这一点是vector 不可比拟的。
二.特点
(1) 不使用连续的内存空间这样可以随意地进行动态操作；
(2) 可以在内部任何位置快速地插入或删除，当然也可以在两端进行push和pop 。
(3) 不能进行内部的随机访问，即不支持[ ] 操作符和vector.at() ；
Lists将元素按顺序储存在链表中，与向量(vectors)相比，它允许快速的插入和删除，但是随机访问却比较慢.。
C++标准规定：每种的容器都必须提供自己的迭代器，容器提供的一些函数以获得迭代器并以之遍历所有元素，而迭代器就是容器提供的一种遍历的方式，其本质上是一个指针。
三.常用API
| assign() | 给list赋值 |
| back() | 返回最后一个元素 |
| begin() | 返回指向第一个元素的迭代器 |
| clear() | 删除所有元素 |
| empty() | 如果list是空的则返回true |
| end() | 返回末尾的迭代器 |
| erase() | 删除一个元素 |
| front() | 返回第一个元素 |
| get_allocator() | 返回list的配置器 |
| insert() | 插入一个元素到list中 |
| max_size() | 返回list能容纳的最大元素数量 |
| merge() | 合并两个list |
| pop_back() | 删除最后一个元素 |
| pop_front() | 删除第一个元素 |
| push_back() | 在list的末尾添加一个元素 |
| push_front() | 在list的头部添加一个元素 |
| rbegin() | 返回指向第一个元素的逆向迭代器 |
| remove() | 从list删除元素 |
| remove_if() | 按指定条件删除元素 |
| rend() | 指向list末尾的逆向迭代器 |
| resize() | 改变list的大小 |
| reverse() | 把list的元素倒转 |
| size() | 返回list中的元素个数 |
| sort() | 给list排序 |
| splice() | 合并两个list |
| swap() | 交换两个list |
| unique() | 删除list中重复的元素 |
四.示例Demo
1) 使用迭代器遍历当前list元素
#include <iostream>#include <stdlib.h>#include <list>using namespace std;#pragma warning(disable:4996)/*const int arraysize = 10;int ai[arraysize] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };int *begin = ai;int *end = ai + arraysize; // end指向的是9后面的空间for (int *pi = begin; pi != end; ++pi){ cout << *pi << "";}*/// 使用迭代器遍历当前链表1void printlist(list<int> &l){ for (list<int>::iterator p = l.begin(); p != l.end(); ++p) { cout << "current item is: " << *p << endl; }}// 使用迭代器遍历当前链表2void printlist2(list<int> &l){ list<int>::iterator current = l.begin(); // 返回第一个元素的迭代器，头指针，迭代器本质上就是一个指针 while (current != l.end()) // l.end() 代表末尾迭代器 尾指针 { cout <<"current item is: " <<*current << endl; current++; }}int main() { list<int> l; for (int i = 0; i < 5; i++) { l.push_back(i + 1); } cout << "current list size is: " << l.size() << endl; printlist(l); printf("----------------------------------------\n"); list<int> s; for (int i = 0; i < 10; i++) { s.push_front(0); } list<int>::iterator s_iterator = s.begin(); // 从链表中取出链表的开头，赋值给迭代器，初始位置为0 s_iterator++; s_iterator++; s_iterator++; // 当前迭代器运行到3号位置(从0开始) s.insert(s_iterator, 5); // 在3号位置插入 printlist2(s); system("pause"); return 0;}
运行结果：
current list size is: 5
current item is: 1
current item is: 2
current item is: 3
current item is: 4
current item is: 5
----------------------------------------
current item is: 0
current item is: 0
current item is: 0
current item is: 5
current item is: 0
current item is: 0
current item is: 0
current item is: 0
current item is: 0
current item is: 0
current item is: 0
2) 链表元素为结构体或结构体指针
#include <iostream>#include <stdlib.h>#include <list>using namespace std;#pragma warning(disable:4996)struct Teacher { char name[20]; int age;};// 使用迭代器遍历当前链表void printlist(list<Teacher*> &l){ for (list<Teacher*>::iterator p = l.begin(); p != l.end(); ++p) { Teacher *teacher = *p; cout << "Teacher, name is: " << teacher->name << ", age is: " << teacher->age << endl; }}// 使用迭代器遍历当前链表void printlist2(list<Teacher> &l){ list<Teacher>::iterator current = l.begin(); // 返回第一个元素的迭代器，头指针，迭代器本质上就是一个指针 while (current != l.end()) // l.end() 代表末尾迭代器 尾指针 { Teacher teacher = *current; cout << "Teacher, name is: " << teacher.name << ", age is: " << teacher.age << endl; current++; }}int main() { Teacher t1, t2, t3; strcpy(t1.name,"jack"); t1.age = 11; strcpy(t2.name,"mike"); t2.age = 22; strcpy(t3.name,"tom"); t3.age = 33; list<Teacher> l; l.push_back(t1); l.push_back(t2); l.push_back(t3); printlist2(l); printf("------------------指针元素-------------------\n"); list<Teacher *> m; m.push_back(&t1); m.push_back(&t2); m.push_back(&t3); printlist(m); system("pause"); return 0;}
运行结果：
Teacher, name is: jack, age is: 11
Teacher, name is: mike, age is: 22
Teacher, name is: tom, age is: 33
------------------指针元素-------------------
Teacher, name is: jack, age is: 11
Teacher, name is: mike, age is: 22
Teacher, name is: tom, age is: 33
4.lists(双向链表)