STL--双端队列（deque）和链表（list）

双端队列(deque容器类): #include deque 与vector 类似，支持随机访问和快速插入删除，它在容器中某一位置上的操作所花费的是线性时间。 与vector不同的是:deque 还支持从开始端插入数据：push_front() 。 此外deque 不支持与vector 的capacity() 、reserve() 类似的操作。 deque，是“double-ended queue”的缩写。可以随机存取元素（用索引直接存取）。 数组头部和尾部添加或移除元素都非常快速，但是在中部安插元素比较费时。 本文地址：http://www.cnblogs.com/archimedes/p/cpp-deque-list.html，转载请注明源地址。
mydeq.empty()  判断队列是否为空,为空返回true mydeq.size()          返回容器中实际数据的个数。 mydeq.erase(pos)       删除pos位置的数据，返回下一个数据的位置。 mydeq.insert(pos,cnt,elem)  在pos位置插入cnt个数据elem。 mydeq.begin()     返回的指针指向数组中的第一个数据。 mydeq.end()        实际上是取末尾加一，以便让循环正确运行--它返回的指针指向最靠近数组界限的数据。 operator[]                返回容器中指定位置的一个引用 deque举例：

#include iostream 

#include deque 

using namespace std; 

typedef deque int INTDEQUE;

// 从前向后显示deque 队列的全部元素 

void put_deque(INTDEQUE deque, char *name) 

 INTDEQUE::iterator pdeque;// 仍然使用迭代器输出 

 cout "The contents of " name " : "; 

 for(pdeque = deque.begin(); pdeque != deque.end(); pdeque++) 

 cout *pdeque " ";// 注意有 "*" 号哦，没有"*" 号的话会报错 

 cout endl; 

// 测试deqtor 容器的功能 

int main() 

 //deq1 对象初始为空 

 INTDEQUE deq1; 

 //deq2 对象最初有10 个值为6 的元素 

 INTDEQUE deq2(10,6); 

 // 声明一个名为i 的双向迭代器变量 

 INTDEQUE::iterator i; 

 // 从前向后显示deq1 中的数据 

 put_deque(deq1,"deq1"); 

 // 从前向后显示deq2 中的数据 

 put_deque(deq2,"deq2"); 

 // 从deq1 序列后面添加两个元素 

 deq1.push_back(2); 

 deq1.push_back(4); 

 cout "deq1.push_back(2) and deq1.push_back(4):" endl; 

 put_deque(deq1,"deq1"); 

 // 从deq1 序列前面添加两个元素 

 deq1.push_front(5); 

 deq1.push_front(7); 

 cout "deq1.push_front(5) and deq1.push_front(7):" endl; 

 put_deque(deq1,"deq1"); 

 // 在deq1 序列中间插入数据 

 deq1.insert(deq1.begin()+1,3,9); 

 cout "deq1.insert(deq1.begin()+1,3,9):" endl; 

 put_deque(deq1,"deq1"); 

 // 测试引用类函数 

 cout "deq1.at(4)=" deq1.at(4) endl; 

 cout "deq1[4]=" deq1[4] endl; 

 deq1.at(1)=10; 

 deq1[2]=12; 

 cout "deq1.at(1)=10 and deq1[2]=12 :" endl; 

 put_deque(deq1,"deq1"); 

 // 从deq1 序列的前后各移去一个元素 

 deq1.pop_front(); 

 deq1.pop_back(); 

 cout "deq1.pop_front() and deq1.pop_back():" endl; 

 put_deque(deq1,"deq1"); 

 // 清除deq1 中的第2 个元素 

 deq1.erase(deq1.begin()+1); 

 cout "deq1.erase(deq1.begin()+1):" endl; 

 put_deque(deq1,"deq1"); 

 // 对deq2 赋值并显示 

 deq2.assign(8,1); 

 cout "deq2.assign(8,1):" endl; 

 put_deque(deq2,"deq2"); 

}

#include list ，是一种双线性列表，只能顺序访问（从前向后或者从后向前）。 list 的数据组织形式   与前面两种容器类有一个明显的区别就是：它不支持随机访问。要访问表中某个下标处的项需要从表头或表尾处（接近该下标的一端）开始循环。而且缺少下标运算符： operator[] 。 在任何位置上执行插入或删除动作都非常迅速，内部只需调整一下指针。   list 内部实现: 双向链表 list T, Alloc 支持操作: begin(), end(), size(), clear(), empty() push_back(), pop_back() push_front(), pop_front() insert()  O(1) erase()  O(1) sort()  O(nlogn),不同于 algorithm 中的sort list仍然包含了erase(),begin(),end(),insert(),push_back(),push_front()这些基本函数，下面我们来演示一下list的其他函数功能。 merge()：合并两个排序列表； sort()：列表的排序； list举例：
void PrintIt(list int n) { for (list int ::iterator iter = n.begin(); iter != n.end(); ++iter) cout *iter " ";//用迭代器进行输出循环 int main(void) { list int listn1, listn2; //给listn1,listn2初始化 listn1.push_back(123); listn1.push_back(0); listn1.push_back(34); listn1.push_back(1123); //now listn1:123,0,34,1123 listn2.push_back(100); listn2.push_back(12); //now listn2:12,100 listn1.sort(); listn2.sort(); //给listn1和listn2排序 //now listn1: 0,34,123,1123 listn2: 12,100 PrintIt(listn1); cout endl; PrintIt(listn2); listn1.merge(listn2); //合并两个排序列表后,listn1: 0，12，34，100，123，1123 cout endl; PrintIt(listn1); cin.get(); }
Redis（八）-Redis的list列表的数据结构-快速链表 数组时需要一块连续的内存空间来存储的，而链表值需要零散的内存碎片，数组的插入和删除的时间复杂度是0(n)，查询的某个元素的时间复杂度是O(1)。
LeetCode 138：复制带随机指针的链表 Copy List with Random Pointer 给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深拷贝。 A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.