⁰

list 链表

list底层是双向循环链表，因此不支持随机访问，但对于插入和删除能做到 O(1)的复杂度，且插入和删除不会使迭代器失效。

基本语法
list<typename> name;
需要加上头文件 list

例如：

//表示创建一个int类型的链表，名字叫做l
list<int> l;

list 的常用函数

构造和赋值

创建一个空的 list

list<int> L1;
创建一个空的整数类型的链表，名字叫做 L1

创建一个大小为 n，值都为 0 的 list

list<int> L1(10, 0);
创建一个大小为 10，值为 0 的整数类型的链表，名字叫做 L1

创建一个和 L1 一样的 list

list<int> L2(L1);
创建一个跟 L1 一样的整数类型的链表 L2

push_back()

L1.push_back(num)
从链表 L1 的末尾插入一个值 num

push_front()

L1.push_front(num)
从链表 L1 的头部插入一个值 num

大小、容量

返回 List 中元素的个数

L1.size()
返回链表 L1 中的元素个数

:: details size 示例代码

#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1(10,1);
    cout << "L1链表中共有 " << L1.size() << " 个元素" << endl;
    return 0;
}

运行结果：
```c
L1链表中共有 10 个元素

返回容器所能容纳的最大元素数目

L1.max_size()
返回 L1 所能容纳的最大元素数目

是系统或者库所实施的限制,但是容器不一定保证能达到该大小，有可能在还未达到该大小的时候，就已经无法继续分配任何的空间了。

判断链表是否为空

L1.empty()
判断 L1 链表是否为空，如果为空则返回 True，否则返回 False

遍历

:: details 遍历示例代码

#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
    L1.push_back(50);
    //list<int>::iterator可以用auto代替
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    return 0;
}

运行结果：

10 20 30 40 50

插入

在指定位置插入一个元素

L1.insert(L1.begin()+num,value);
在链表的开头位置插入值为 value 的元素 :: details 在指定位置插入一个元素示例代码

#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
    L1.push_back(50);
    cout << "插入元素之前：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    cout << endl;
    L1.insert(L1.begin(),100);
    cout << "插入元素之后：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    return 0;
}

运行结果：

插入元素之前：
10 20 30 40 50
插入元素之后：
100 10 20 30 40 50

:: tip 分析表示在链表的开头插入一个元素 100 ::

在指定位置插入多个元素 L1.insert(L1.begin(), n, value);
在链表的开头位置插入值为 num 的 n 个元素

:: details 在指定位置插入多个元素示例代码

#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
    L1.push_back(50);
    cout << "插入元素之前：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    cout << endl;
    L1.insert(L1.begin(),3,100);
    cout << "插入元素之后：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    return 0;
}

运行结果：

插入元素之前：
10 20 30 40 50
插入元素之后：
100 100 100 10 20 30 40 50

:: tip 分析表示在链表的开头插入 3 个都是 100 的值

删除

在头部删除元素 L1.pop_front();
删除 L1 链表的头部元素

:: details 在头部删除元素示例代码

#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
    L1.push_back(50);
        cout << "删除元素之前：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    cout << endl;
    L1.pop_front();
    cout << "删除元素之后：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    return 0;
}

运行结果：

删除元素之前：
10 20 30 40 50
删除元素之后：
20 30 40 50

:: tip 分析将链表的头部元素 10 删除了

在尾部删除元素 L1.pop_back();
删除 L1 链表的尾部元素

:: details 在尾部删除元素示例代码

#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
    L1.push_back(10);
    L1.push_back(20);
    L1.push_back(30);
    L1.push_back(40);
    L1.push_back(50);
        cout << "删除元素之前：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    cout << endl;
    L1.pop_back() ;
    cout << "删除元素之后：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    return 0;
}

运行结果：

删除元素之前：
10 20 30 40 50
删除元素之后：
10 20 30 40

:: tip 分析将链表的尾部元素 50 删除了

删除任意位置上的一个元素 L8.erase(++L8.begin());

排序

通过 list 的 sort 成员函数来排序。默认从低到高

L1.sort();
对链表 L1 进行排序

:: details 升序示例代码

#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
    L1.push_back(10);
    L1.push_back(30);
    L1.push_back(20);
    L1.push_back(70);
    L1.push_back(50);
    cout << "排序之前：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    cout << endl;
    L1.sort();
    cout << "排序之后：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    return 0;
}

运行结果：

排序之前：
10 30 20 70 50
排序之后：
10 20 30 50 70

:: tip 分析链表里面的元素默认升序排序 ::

通过 list 的 sort 成员函数来排序。默认从低到高

L1.sort(greater<int>());
对链表 L1 进行降序排序

:: details 降序示例代码

#include<bits/stdc++.h>
#include<list>
using namespace std;
int main()
{
    list<int> L1;
    L1.push_back(10);
    L1.push_back(30);
    L1.push_back(20);
    L1.push_back(70);
    L1.push_back(50);
    cout << "排序之前：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    cout << endl;
    L1.sort(greater<int>());
    cout << "排序之后：" << endl;
    for(list<int>::iterator it = L1.begin(); it!=L1.end() ; it++){
        cout << *it << &apos; &apos; ;
    }
    return 0;
}

运行结果：

排序之前：
10 30 20 70 50
排序之后：
70 50 30 20 10

:: tip 分析链表里面的元素默认降序排序 ::

vector

stack

On This Page

list 的常用函数