C++基础：STL之双向链表list

这篇文章介绍一下STL中list的基本使用方法。

双向链表list

相较于数组，链表也是一种非常常见的数据结构，链表的特点主要如下所示：

• 物理存储上非连续，数组为顺序存储，需要大段空间，而链表则体现为随机存储，可见缝插针地使用空间

• 一般分为双向链表或者单向链表

• 链表的元素一般称为节点，节点由存放数据的部分和存放链接信息的指针数据组成

• 单向链表一般保存next指针关联后续节点，双向链表还需要previous指针指向前面的节点

• 关于对于数组和链表的说明内容可参看：https://blog.csdn.net/liumiaocn/article/details/108088361

头文件和命名空间

#include using namespace std;

常用的成员函数 函数名 用途 功能说明 时间复杂度 size() 查询遍历 获取元素个数 O(1) begin() 查询遍历 获取指向第一个元素的迭代器 O(1) end() 查询遍历 获取末尾的迭代器 O(1) insert(position,x) 插入 在position位置插入数据x O(1)/O(n) erase(position) 删除 删除position位置上的元素 O(1)/O(n) push_back(x) 插入 在末尾插入数据x O(1) pop_back() 删除 删除最后一个元素 O(1) clear() 删除 删除所有元素 O(n) push_front(x) 插入 在表头插入数据x O(1) pop_front 删除 删除表头元素 O(1)

注：因为对于末尾的元素的插入和删除不涉及元素的连锁移动，所以复杂度为O(1)，另外成员函数中似乎未涉及更新，这是因为vecotr可以像数组一样直接使用下标方式访问和修改，其复杂度当然也是O(1)。

list vs vector

常用函数比较如下所示，简单来说，基本一致，list由于其链表的特性，在插入和删除的时候只需要断链和重链即可，所以复杂度也是常数级别的O(1)。另外由于其双向的特性，所以还存在一个在表头进行插入和删除的函数，此函数由于vector是变长数组的实现，所以是没有这种函数的。

list函数名 vector函数名 用途 功能说明 时间复杂度 size() size() 查询遍历 获取元素个数 O(1) begin() begin() 查询遍历 获取指向第一个元素的迭代器 O(1) end() end() 查询遍历 获取末尾的迭代器 O(1) insert(position,x) insert(position,x) 插入 在position位置插入数据x O(1)/O(n) erase(position) erase(position) 删除 删除position位置上的元素 O(1)/O(n) push_back(x) push_back(x) 插入 在末尾插入数据x O(1) pop_back pop_back() 删除 删除最后一个元素 O(1) clear() clear() 删除 删除所有元素 O(n) push_front(x) - 插入 在表头插入数据x O(1) pop_front - 删除 删除表头元素 O(1) 代码使用示例

#include#includeusing namespace std;

void print_list_data(listl) {
    list::iterator it = l.begin();

    while (it != l.end()) cout << *it++;

    cout << endl;
}

int main() {
    listl;

    cout << "Size of list l : " << l.size() << endl;
    l.push_back('L');
    l.push_back('i');
    l.push_back('u');
    l.push_back('C');
    l.push_back('N');
    cout << "Size of list l : " << l.size() << endl;
    for (list::iterator it = l.begin(); it != l.end(); it++) cout << *it;
    cout <