list如何实现元素的插入和删除？

八股文_C++STL面试题 0 3

参考回答

std::list 使用 双向链表 作为底层实现，因此插入和删除操作的效率非常高。插入和删除时，只需要调整相关节点的指针，不需要像 std::vector 那样移动大量元素。

插入元素：
- 时间复杂度：(O(1))，无需移动其他元素。
- 方法：insert() 或 push_front() / push_back()。
删除元素：
- 时间复杂度：(O(1))（删除指定位置）。
- 方法：erase() 或 pop_front() / pop_back()。

详细讲解与拓展

1. 插入元素

插入元素时，std::list 创建一个新节点并调整指针连接。操作分为三种场景：

头部插入（push_front）：
直接将新节点的 next 指针指向当前头部节点，并更新链表的 head 指针。
尾部插入（push_back）：
将当前尾部节点的 next 指向新节点，并更新链表的 tail 指针。
中间插入（insert）：
调整前后节点的 next 和 prev 指针。

示例代码：

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

int main() {
    list<int> lst = {1, 2, 3};

    // 头部插入
    lst.push_front(0);

    // 尾部插入
    lst.push_back(4);

    // 中间插入
    auto it = next(lst.begin(), 2);  // 指向第3个元素
    lst.insert(it, 99);

    for (int val : lst) {
        cout << val << " ";
    }
    return 0;
}

输出：

0 1 99 2 3 4

2. 删除元素

删除元素时，std::list 直接调整前后节点的指针，然后释放被删除节点的内存。常见场景包括：

删除头部元素（pop_front）：
更新头部节点指针，释放原头节点。
删除尾部元素（pop_back）：
更新尾部节点指针，释放原尾节点。
删除中间元素（erase）：
通过迭代器指定要删除的元素，调整其前后节点的指针。

示例代码：

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

int main() {
    list<int> lst = {1, 2, 3, 4, 5};

    // 删除头部元素
    lst.pop_front();

    // 删除尾部元素
    lst.pop_back();

    // 删除中间元素
    auto it = next(lst.begin(), 1);  // 指向第2个元素
    lst.erase(it);

    for (int val : lst) {
        cout << val << " ";
    }
    return 0;
}

输出：

2 4

3. 插入和删除的底层操作

std::list 的插入和删除操作依赖于双向链表的指针调整。以下是操作过程：

插入节点：
1. 创建一个新节点 N。
2. 设置新节点的 prev 和 next 指针，指向目标位置的前后节点。
3. 修改目标位置前后节点的指针，使它们指向新节点 N。
删除节点：
1. 更新被删除节点的前后节点，使它们直接指向彼此。
2. 释放被删除节点的内存。

插入示意图：

原链表：A <-> B <-> C
插入节点N后：A <-> N <-> B <-> C

删除示意图：

原链表：A <-> B <-> C
删除节点B后：A <-> C

4. 性能比较

插入和删除性能：
由于不需要移动其他元素，std::list 的插入和删除性能始终为 (O(1))。
遍历性能：
遍历链表时，需要逐一访问节点，因此访问性能为 (O(n))。

与 vector 的对比：
– 如果频繁插入或删除元素（尤其是头部和中间位置），list 的性能更优。
– 如果需要随机访问或顺序读取大量数据，vector 的性能更优。

总结

std::list 利用双向链表的特性实现高效的插入和删除操作，适用于需要频繁修改容器内容的场景。头部、尾部和中间位置的插入和删除操作都只需调整指针，时间复杂度为 (O(1))。然而，由于链表不支持随机访问，遍历的时间复杂度为 (O(n))。合理选择场景可以充分发挥其优势。