[TOC] # 簡介 鏈表是一種物理存儲單元上非連續、非順序的存儲結構，數據元素的邏輯順序是通過鏈表中的指針鏈接次序實現的。鏈表由一系列結點（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個是存儲數據元素的數據域，另一個是存儲下一個結點地址的指針域。 相較于vector的連續線性空間，list就顯得負責許多，它的好處是每次插入或者刪除一個元素，就是配置或者釋放一個元素的空間。因此，list對于空間的運用有絕對的精準，一點也不浪費。而且，對于任何位置的元素插入或元素的移除，list永遠是常數時間。 List和vector是兩個最常被使用的容器。 List容器是一個雙向鏈表。  * 采用動態存儲分配，不會造成內存浪費和溢出 * 鏈表執行插入和刪除操作十分方便，修改指針即可，不需要移動大量元素 * 鏈表靈活，但是空間和時間額外耗費較大 由于list是一個循環雙向鏈表，迭代器必須能夠具備前移、后移的能力，所以list容器提供的是Bidirectional Iterators. List有一個重要的性質，插入操作和刪除操作都不會造成原有list迭代器的失效。 這在vector是不成立的，因為vector的插入操作可能造成記憶體重新配置，導致原有的迭代器全部失效，甚至List元素的刪除，也只有被刪除的那個元素的迭代器失效，其他迭代器不受任何影響。 # 常用api ## 構造函數 ~~~ list<T> lstT;//list采用采用模板類實現,對象的默認構造形式： list(beg,end);//構造函數將[beg, end)區間中的元素拷貝給本身。 list(n,elem);//構造函數將n個elem拷貝給本身。 list(const list &lst);//拷貝構造函數。 ~~~ ~~~ list<int> mylist1(10, 6); list<int> mylist2(++mylist1.begin(), --mylist1.end()); ~~~ ## 元素插入和刪除 ~~~ push_back(elem);//在容器尾部加入一個元素 pop_back();//刪除容器中最后一個元素 push_front(elem);//在容器開頭插入一個元素 pop_front();//從容器開頭移除第一個元素 insert(pos,elem);//在pos位置插elem元素的拷貝，返回新數據的位置。 insert(pos,n,elem);//在pos位置插入n個elem數據，無返回值。 insert(pos,beg,end);//在pos位置插入[beg,end)區間的數據，無返回值。 clear();//移除容器的所有數據 erase(beg,end);//刪除[beg,end)區間的數據，返回下一個數據的位置。 erase(pos);//刪除pos位置的數據，返回下一個數據的位置。 remove(elem);//刪除容器中所有與elem值匹配的元素。 ~~~ ~~~ list<int> mylist; for (int i = 0; i < 10; i++) { mylist.push_back(i); } //2015和2017vs :_Myhead==>_Myhead(),_Mysize==>_Mysize() list<int>::_Nodeptr node = mylist._Myhead->_Next;//頭節點的下一個節點 for (int i = 0; i < mylist._Mysize * 2; i++) { cout << "Node:" << node->_Myval << endl;//獲取節點數據 node = node->_Next; if (node == mylist._Myhead) { node = node->_Next; } } ~~~ ## 大小操作 ~~~ size();//返回容器中元素的個數 empty();//判斷容器是否為空 resize(num);//重新指定容器的長度為num， 若容器變長，則以默認值填充新位置。 如果容器變短，則末尾超出容器長度的元素被刪除。 resize(num, elem);//重新指定容器的長度為num， 若容器變長，則以elem值填充新位置。 如果容器變短，則末尾超出容器長度的元素被刪除。 ~~~ ## 賦值 ~~~ assign(beg, end);//將[beg, end)區間中的數據拷貝賦值給本身。 assign(n, elem);//將n個elem拷貝賦值給本身。 list&operator=(const list &lst);//重載等號操作符 swap(lst);//將lst與本身的元素互換。 ~~~ ## 數據的存取 ~~~ front();//返回第一個元素。 back();//返回最后一個元素。 ~~~ ## 反轉排序 ~~~ reverse();//反轉鏈表，比如lst包含1,3,5元素，運行此方法后，lst就包含5,3,1元素。 sort(); //list排序 ~~~