list双向链表容器

List容器是一种实现了双向链表的数据结构，它的每个节点都含有前驱元素指针域、数据域、后继元素指针域。不同于数组这样的线性表，由于list元素的前驱和后继都是靠指针来链接，因此在链表的任意位置进行元素的插入、删除和查找操作速度是较快的。由于list对象的结点并不要求在一段连续的内存中，所以对于迭代器，只能通过“++”或者“--”的操作，不能对其进行+N或者-N的操作。List含有丰富的操作，使用前需引入<list>头文件。

（一）创建list对象：

（1）创建没有任何元素的list对象：list<int > l;  

（2）创建具有n个元素的list对象：list<int > l(10);  //创建具有10个整形元素的list对象l 。

（二）插入元素：

（1）使用push_back()方法从尾部插入元素，链表自动扩张；

（2）使用push_front()方法从头部插入元素，链表自动扩张；

（3）使用insert()方法向迭代器位置插入新元素，链表自动扩张。

[cpp] view plain copy

#include<iostream>    

#include<list>    

#include<algorithm>    

using namespace std;    

int main()    

{    

    int i;  

    list<int> l;  

    list<int>::iterator pos;  

    //使用push_back()方法从尾部插入元素  

    l.push_back(1);  

    l.push_back(2);  

    l.push_back(3);  

    l.push_back(4);  

    for(pos=l.begin();pos!=l.end();pos++)  

        cout<<*pos<<" ";  

    cout<<endl;  

    //使用push_front()方法从头部插入元素  

    l.push_front(0);  

    for(pos=l.begin();pos!=l.end();pos++)  

        cout<<*pos<<" ";  

    cout<<endl;  

    //使用insert()方法向迭代器位置插入新元素  

    pos=l.begin();  

    pos++;  

    l.insert(pos,9);  

    for(pos=l.begin();pos!=l.end();pos++)  

        cout<<*pos<<" ";  

    cout<<endl;  

    return 0;    

}   

输出结果：  

1 2 3 4  

0 1 2 3 4  

0 9 1 2 3 4  

（三）遍历元素：

（1）前向遍历：以前向迭代器的方式遍历；

（2）反向遍历：使用反向迭代器进行遍历。

[cpp] view plain copy

#include<iostream>    

#include<list>    

#include<algorithm>    

using namespace std;    

int main()    

{    

    int i;  

    list<int> l;  

    list<int>::iterator pos;  

    list<int>::reverse_iterator pos1;  

    l.push_back(1);  

    l.push_back(2);  

    l.push_back(3);  

    l.push_back(4);  

    //前向遍历  

    for(pos=l.begin();pos!=l.end();pos++)  

        cout<<*pos<<" ";  

    cout<<endl;  

    //反向遍历  

    for(pos1=l.rbegin();pos1!=l.rend();pos1++)  

        cout<<*pos1<<" ";  

    cout<<endl;  

    return 0;    

}   

输出结果：  

1 2 3 4  

4 3 2 1  

（四）删除元素：

（1）remove(元素值)，删除链表中的元素，值相同的元素都会被删除；

（2）pop_front()删除链表首元素；

（3）pop_back()删除链表尾元素；

（4）erase()删除迭代器位置的元素；

（5）clear()清空链表容器。

[cpp] view plain copy

#include<iostream>    

#include<list>    

#include<algorithm>    

using namespace std;    

int main()    

{    

    int i;  

    list<int> l;  

    list<int>::iterator pos;  

    l.push_back(1);  

    l.push_back(3);  

    l.push_back(2);  

    l.push_back(4);  

    l.push_back(-1);  

    l.push_back(0);  

    l.push_back(1);  

    for(pos=l.begin();pos!=l.end();pos++)  

        cout<<*pos<<" ";  

    cout<<endl;  

    //remove(元素值),值相同的元素都会被删除  

    l.remove(1);  

    for(pos=l.begin();pos!=l.end();pos++)  

        cout<<*pos<<" ";  

    cout<<endl;  

    //pop_front() 删除链表首元素  

    l.pop_front();  

    for(pos=l.begin();pos!=l.end();pos++)  

        cout<<*pos<<" ";  

    cout<<endl;  

    //pop_back() 删除链表尾元素  

    l.pop_back();  

    for(pos=l.begin();pos!=l.end();pos++)  

        cout<<*pos<<" ";  

    cout<<endl;  

    //erase() 删除迭代器位置的元素  

    pos=l.begin();  

    pos++;  

    l.erase(pos);  

    for(pos=l.begin();pos!=l.end();pos++)  

        cout<<*pos<<" ";  

    cout<<endl;  

    //clear()清空链表容器  

    l.clear();  

    cout<<"size="<<l.size()<<endl;  

    return 0;    

}   

输出结果：  

1 3 2 4 -1 0 1  

3 2 4 -1 0  

2 4 -1 0  

2 4 -1  

2 -1  

size=0  

（五）查找元素：需要添加#include<algorithm>

find(迭代器1，迭代器2，元素)，函数返回一个迭代器值，若该值被找到则返回该值所在的迭代器值，若没有找到则返回end()迭代器的位置。

（六）list排序：使用list的成员函数sort()实现升序排序

[cpp] view plain copy

#include<iostream>    

#include<list>    

using namespace std;    

int main()    

{    

    int i;  

    list<int> l;  

    list<int>::iterator pos;  

    l.push_back(1);  

    l.push_back(3);  

    l.push_back(2);  

    l.push_back(4);  

    l.push_back(-1);  

    l.push_back(0);  

    l.push_back(1);  

    l.sort();  

    for(pos=l.begin();pos!=l.end();pos++)  

        cout<<*pos<<" ";  

    cout<<endl;  

    return 0;    

}   

输出结果：  

-1 0 1 1 2 3 4