C++STL之list雙向連結清單容器

list容器實作了雙向連結清單的資料結構，資料元素是通過連結清單指針串成邏輯意義上的線性表，選擇對連結清單的任一位置的元素進行插入，删除和查找都是非常高效的。

list的每個節點有三個域：前驅元素指針域，資料域，後繼元素指針域，前驅元素的指針域儲存了前驅元素的首位址；資料域則是本節點的資料，後繼元素指針域則儲存了後繼元素的首位址。

list的頭節點的前驅元素指針域儲存的是連結清單中尾元素的首位址，而list的尾節點的後繼元素指針域則儲存了頭節點的首位址，這樣就構成一個雙向循環連結清單。

由于list對象的節點并不要求一段連續的記憶體空間，是以，對于疊代器，隻能通過”++”或”–”的操作将疊代器移動到後繼/前驅節點元素處。而不能對疊代器進行+n或者-n操作。

*建立list對象

建立空連結清單

list<int> L;
           

建立具有n個元素的連結清單

list<int> L();
           

*元素的插入和周遊

采用push_back方法往尾部插入元素，連結清單自動擴張。

采用push_front方法往首部插入元素，連結清單自動擴張。

采用insert方法往疊代器插入元素，聯系自動擴張。

疊代器隻能進行”++”或“–”操作，不能進行+n或-n操作。

#include<iostream>
#include<list>
using namespace std;

int main()
{
    list<int> L;
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();

    list<int>::iterator it;
    it = L.begin();
    it ++;
    L.insert(it, );
    for(it = L.begin(); it != L.end(); it ++)
        cout<<*it<<" ";
    cout<<endl;

    list<int>::reverse_iterator rit;
    for(rit = L.rbegin(); rit != L.rend(); rit ++)
        cout<<*rit<<" ";
    cout<<endl;

    return ;
}
           

*元素删除

使用remove()方法删除連結清單中一個元素，值相同的元素都會被删除。

使用pop_front()方法删除連結清單首元素。

使用pop_back()方法删除連結清單尾元素。

#include<iostream>
#include<list>
using namespace std;

int main()
{
    list<int> L;
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();

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

    //删除所有等于1的元素 
    L.remove();
    for(it = L.begin(); it != L.end(); it ++)
        cout<<*it<<" ";
    cout<<endl;

    L.pop_front();
    L.pop_back();
    for(it = L.begin(); it != L.end(); it ++)
        cout<<*it<<" ";
    cout<<endl;

    return ;
}
           

使用erase()方法删除疊代器位置上的元素

使用clear()方法清空連結清單

#include<iostream>
#include<list>
using namespace std;

int main()
{
    list<int> L;
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();

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

    //删除第2個元素（從0開始計數）
    it = L.begin();
    it ++;
    it ++;

    L.erase(it);
    for(it = L.begin(); it != L.end(); it ++)
        cout<<*it<<" ";
    cout<<endl;

    L.clear();
    cout<<L.size()<<endl;
    return ;
}
           

*元素查找

采用find()查找可以在連結清單中查找元素，如果找到該元素，則傳回該元素的疊代器位置，反之，則傳回end()疊代器位置。

find()算法需要聲明頭檔案`#include

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;

int main()
{
    list<int> L;
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();

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

    it = find(L.begin(), L.end(), );
    if(it != L.end())
        cout<<"Find it"<<endl;
    else
        cout<<"Not find it"<<endl;

    it = find(L.begin(), L.end(), );
    if(it != L.end())
        cout<<"Find it"<<endl;
    else
        cout<<"Not find it"<<endl;
    return ;
}
           

*元素排序

使用sort()方法對連結清單進行排序，升序排列

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;

int main()
{
    list<int> L;
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();

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

    L.sort();

    for(it = L.begin(); it != L.end(); it ++)
        cout<<*it<<" ";
    cout<<endl;
    return ;
}
           

*剔除連續重複元素

采用unique()方法可以剔除連續重複元素，隻保留一個

#include<iostream>
#include<list>
#include<algorithm>
using namespace std;

int main()
{
    list<int> L;
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();
    L.push_back();

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

    L.unique();

    for(it = L.begin(); it != L.end(); it ++)
        cout<<*it<<" ";
    cout<<endl;
    return ;
}