链表容器(list container in STL)

C++程序设计第十四章标准模板库(STL) 链表容器(list container in STL)

list的底层由双向链表（doubly linked list）实现而成，他的内存空间可以是不连续的，通过指针来进行数据的访问，这个特点使得它的随机存取变得非常没有效率，因此它没有提供 [] 操作符的重载。但是由于链表的特点，它可以很有效率的支持任意地方的插入和删除操作。

list 容器可用的成员函数

成员函数	功能
begin()	返回指向容器中第一个元素的双向迭代器。
end()	返回指向容器中最后一个元素所在位置的下一个位置的双向迭代器。
rbegin()	返回指向最后一个元素的反向双向迭代器。
rend()	返回指向第一个元素所在位置前一个位置的反向双向迭代器。
empty()	判断容器中是否有元素，若无元素，则返回 true；反之，返回 false。
size()	返回当前容器实际包含的元素个数。
max_size()	返回容器所能包含元素个数的最大值。这通常是一个很大的值，一般是 2³²-1，所以我们很少会用到这个函数。
front()	返回第一个元素的引用。
back()	返回最后一个元素的引用。
assign()	用新元素替换容器中原有内容。
push_front()	在容器头部插入一个元素。
pop_front()	删除容器头部的一个元素。
push_back()	在容器尾部插入一个元素。
pop_back()	删除容器尾部的一个元素。
insert()	在容器中的指定位置插入元素。
erase()	删除容器中一个或某区域内的元素。
swap()	交换两个容器中的元素，必须保证这两个容器中存储的元素类型是相同的。
resize()	调整容器的大小。
clear()	删除容器存储的所有元素。
splice()	将一个 list 容器中的元素插入到另一个容器的指定位置。
remove(val)	删除容器中所有等于 val 的元素。
remove_if()	删除容器中满足条件的元素。
unique()	删除容器中相邻的重复元素，只保留一个。
merge()	合并两个事先已排好序的 list 容器，并且合并之后的 list 容器依然是有序的。
sort()	通过更改容器中元素的位置，将它们进行排序。
reverse()	反转容器中元素的顺序。

/**************************************************************** 
 * 代码作者: Alex Li
 * 创建时间: 2023-05-27 21:33:42
 * 最后修改: 2025-01-10 21:34:15
 * 文件描述: list容器的使用
****************************************************************/
#include <iostream>
#include <list>

using namespace std;

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

int main() {
    list<int> lst;

    // 添加节点到链表尾部
    lst.push_back(10);
    lst.push_back(20);
    lst.push_back(30);

    // 打印链表内容
    cout << "链表内容:" << endl;
    for (int val : lst) {
        cout << val << " -> ";
    }
    cout << "NULL" << endl;

    // 在链表头部插入节点
    lst.push_front(5);
    cout << "在头部插入5后:" << endl;
    for (int val : lst) {
        cout << val << " -> ";
    }
    cout << "NULL" << endl;

    // 使用insert在第二个位置插入15
    //list<int>::iterator it = lst.begin(); 
    auto it = lst.begin();
    advance(it, 1); // 移动迭代器到第二个位置
    lst.insert(it, 15);
    
    cout << "在第二个位置插入15后:" << endl;
    for (int val : lst) {
        cout << val << " -> ";
    }
    cout << "NULL" << endl;

    // 在第三个位置插入3个值为9的节点
    it = lst.begin();
    advance(it, 3); // 移动迭代器到第三个位置
    lst.insert(it, 3, 9);
    cout << "在第三个位置插入3个值为9的节点后:" << endl;
    for (int val : lst) {
        cout << val << " -> ";
    }
    cout << "NULL" << endl;

    // 检查链表是否为空
    cout << "链表是否为空: " << (lst.empty() ? "是" : "否") << endl;

    // 打印链表大小
    cout << "链表大小: " << lst.size() << endl;

    // 删除值为20的节点
    it = find(lst.begin(), lst.end(), 20);
    if (it != lst.end()) {
        lst.erase(it);
    }
    cout << "删除值为20的节点后:" << endl;
    for (int val : lst) {
        cout << val << " -> ";
    }
    cout << "NULL" << endl;

    // 修改值为30的节点为40
    it = find(lst.begin(), lst.end(), 30);
    if (it != lst.end()) {
        *it = 40;
    }
    cout << "将值30修改为40后:" << endl;
    for (int val : lst) {
        cout << val << " -> ";
    }
    cout << "NULL" << endl;

    // 查找节点
    cout << "查找值为10的节点:" << (find(lst.begin(), lst.end(), 10) != lst.end() ? "存在" : "不存在") << endl;
    cout << "查找值为50的节点:" << (find(lst.begin(), lst.end(), 50) != lst.end() ? "存在" : "不存在") << endl;

    return 0;
}

Previous Lesson

Back to Lesson

Next Topic