一、List簡(jiǎn)介

鏈表是一種物理存儲(chǔ)單元上非連續(xù)、非順序的存儲(chǔ)結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過(guò)鏈表中的指針鏈接次序?qū)崿F(xiàn)的。

鏈表由一系列結(jié)點(diǎn)（鏈表中每一個(gè)元素稱為結(jié)點(diǎn)）組成，結(jié)點(diǎn)可以在運(yùn)行時(shí)動(dòng)態(tài)生成。每個(gè)結(jié)點(diǎn)包括兩個(gè)部分：一個(gè)是存儲(chǔ)數(shù)據(jù)元素的數(shù)據(jù)域，另一個(gè)是存儲(chǔ)下一個(gè)結(jié)點(diǎn)地址的指針域。

相較于vector的連續(xù)線性空間，list的好處是每次插入或者刪除一個(gè)元素，就是配置或者釋放一個(gè)元素的空間。因此，list對(duì)于空間的運(yùn)用有絕對(duì)的精準(zhǔn)，一點(diǎn)也不浪費(fèi)。而且，對(duì)于任何位置的元素插入或元素的移除，list永遠(yuǎn)是常數(shù)時(shí)間。

List和vector是兩個(gè)最常被使用的容器。

list容器是一個(gè)雙向鏈表容器，可高效地進(jìn)行插入刪除元素。

list不可以隨機(jī)存取元素，所以不支持at.(pos)函數(shù)與[]操作符。

#include <list>

二、list對(duì)象的默認(rèn)構(gòu)造

list采用采用模板類實(shí)現(xiàn),對(duì)象的默認(rèn)構(gòu)造形式：list<T> LIST; 如：

list<int> lstInt;      //定義一個(gè)存放int的list容器。
list<float> lstFloat;   //定義一個(gè)存放float的list容器。
list<string> lstString;   //定義一個(gè)存放string的list容器。              
//尖括號(hào)內(nèi)還可以設(shè)置指針類型或自定義類型。

三、list頭尾的添加移除操作

list.push_back(elem); //在容器尾部加入一個(gè)元素

list.pop_back(); //刪除容器中最后一個(gè)元素

list.push_front(elem); //在容器開(kāi)頭插入一個(gè)元素

list.pop_front(); //從容器開(kāi)頭移除第一個(gè)元素

list<int> lstInt;
lstInt.push_back(1);
lstInt.push_back(3);
lstInt.push_back(5);
lstInt.push_back(7);
lstInt.push_back(9);
lstInt.pop_front();
lstInt.pop_front();
lstInt.push_front(11);
lstInt.push_front(13);
lstInt.pop_back();
lstInt.pop_back();
// lstInt    {13,11,5}

四、list的數(shù)據(jù)存取

list.front(); //返回第一個(gè)元素。

list.back(); //返回最后一個(gè)元素。

list<int> lstInt;
lstInt.push_back(1);
lstInt.push_back(5);
lstInt.push_back(9);

int iFront = lstInt.front();//1
int iBack = lstInt.back();//9

五、list與迭代器

list.begin(); //返回容器中第一個(gè)元素的迭代器。

list.end(); //返回容器中最后一個(gè)元素之后的迭代器。

list.rbegin(); //返回容器中倒數(shù)第一個(gè)元素的迭代器。

list.rend(); //返回容器中倒數(shù)最后一個(gè)元素的后面的迭代器。

for (list<int>::iterator it=lstInt.begin(); it!=lstInt.end(); ++it){
cout << *it<<cout << " ";
}

六、list對(duì)象的帶參數(shù)構(gòu)造

list(beg,end); //構(gòu)造函數(shù)將[beg, end)區(qū)間中的元素拷貝給本身。注意該區(qū)間是左閉右開(kāi)的區(qū)間。

list(n,elem); //構(gòu)造函數(shù)將n個(gè)elem拷貝給本身。

list(const list &lst); //拷貝構(gòu)造函數(shù)。

list<int> mlist1;
list<int> mlist2(10, 10); //有參構(gòu)造
list<int> mlist3(mlist2);//拷貝構(gòu)造
list<int> mlist4(mlist2.begin(), mlist2.end());

for (list<int>::iterator it = mlist4.begin(); it != mlist4.end(); it++) {
cout << *it << " ";
}
cout << endl;
/*
結(jié)果：
10 10 10 10 10 10 10 10 10 10
*/

七、list的賦值

list.assign(beg,end); //將[beg, end)區(qū)間中的數(shù)據(jù)拷貝賦值給本身。注意該區(qū)間是左閉右開(kāi)的區(qū)間。

list.assign(n,elem); //將n個(gè)elem拷貝賦值給本身。

list& operator=(const list &lst); //重載等號(hào)操作符

list.swap(lst); // 將lst與本身的元素互換。

list<int> lstIntA,lstIntB,lstIntC,lstIntD;
lstIntA.push_back(1);
lstIntA.push_back(5);
lstIntA.push_back(9);

lstIntB.assign(lstIntA.begin(),lstIntA.end());//1 5 9
lstIntC.assign(5,8);//8 8 8 8 8
lstIntD = lstIntA;//1 5 9
lstIntC.swap(lstIntD);//互換

八、list的大小

list.size(); //返回容器中元素的個(gè)數(shù)

list.empty(); //判斷容器是否為空

list.resize(num); //重新指定容器的長(zhǎng)度為num，若容器變長(zhǎng)，則以默認(rèn)值填充新位置。如果容器變短，則末尾超出容器長(zhǎng)度的元素被刪除。

list.resize(num, elem); //重新指定容器的長(zhǎng)度為num，若容器變長(zhǎng)，則以elem值填充新位置。如果容器變短，則末尾超出容器長(zhǎng)度的元素被刪除。

list<int> lstIntA;
lstIntA.push_back(11);
lstIntA.push_back(33);
lstIntA.push_back(55);

if (!lstIntA.empty())
{
int iSize = lstIntA.size();//3
lstIntA.resize(5);//11 33 55 0 0
lstIntA.resize(7,1);//11 33 55 0 0 1 1
lstIntA.resize(2);//11 33
}

九、list的插入

list.insert(pos,elem); //在pos位置插入一個(gè)elem元素的拷貝，返回新數(shù)據(jù)的位置。

list.insert(pos,n,elem); //在pos位置插入n個(gè)elem數(shù)據(jù)，無(wú)返回值。

list.insert(pos,beg,end); //在pos位置插入[beg,end)區(qū)間的數(shù)據(jù)，無(wú)返回值。

list<int> lstA;
list<int> lstB;

lstA.push_back(1);
lstA.push_back(5);
lstA.push_back(9);

lstB.push_back(2);
lstB.push_back(6);

lstA.insert(lstA.begin(), 11);//{11, 1, 5, 9}
lstA.insert(++lstA.begin(),2,33);//{11,33,33,1,5,9}
lstA.insert(lstA.begin() , lstB.begin() , lstB.end() );//{2,6,11,33,33,1,5,9}

十、list的刪除

list.clear(); //移除容器的所有數(shù)據(jù)

list.erase(beg,end); //刪除[beg,end)區(qū)間的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。

list.erase(pos); //刪除pos位置的數(shù)據(jù)，返回下一個(gè)數(shù)據(jù)的位置。

lst.remove(elem); //刪除容器中所有與elem值匹配的元素。

//刪除區(qū)間內(nèi)的元素
//lstInt是用list<int>聲明的容器，現(xiàn)已包含按順序的1,3,5,6,9元素。
list<int>::iterator itBegin=lstInt.begin();
++ itBegin;
list<int>::iterator itEnd=lstInt.begin();
++ itEnd;
++ itEnd;
++ itEnd;
lstInt.erase(itBegin,itEnd);
//此時(shí)容器lstInt包含按順序的1,6,9三個(gè)元素。

//假設(shè) lstInt 包含1,3,2,3,3,3,4,3,5,3，刪除容器中等于3的元素的方法一
for(list<int>::iterator it=lstInt.being(); it!=lstInt.end(); )    //小括號(hào)里不需寫  ++it
{
   if(*it == 3){
        it  =  lstInt.erase(it);       //以迭代器為參數(shù)，刪除元素3，并把數(shù)據(jù)刪除后的下一個(gè)元素位置返回給迭代器。
         //此時(shí)，不執(zhí)行  ++it；  
   }
   else{
       ++it;
   }
}

//刪除容器中等于3的元素的方法二
lstInt.remove(3);

//刪除lstInt的所有元素
lstInt.clear();//容器為空

十一、list的反序排列

lst.reverse(); //反轉(zhuǎn)鏈表

list<int> lstA;

lstA.push_back(1);
lstA.push_back(3);
lstA.push_back(5);
lstA.push_back(7);
lstA.push_back(9);

lstA.reverse();//9 7 5 3 1