C++ forward_list单向链表用法_C++轻量级链表的插入与删除

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

C++ forward_list单向链表用法_C++轻量级链表的插入与删除

2025-12-05

浏览次数：次

返回列表

forward_list是C++ STL中的单向链表，内存开销小，适用于频繁插入删除且无需反向遍历的场景。它定义于头文件，仅支持前向迭代，不提供size()方法（C++11起可选），需用distance(begin(), end())计算长度。其节点只含下一节点指针，插入删除操作高效，时间复杂度为O(1)，但只能在指定位置之后进行，因此使用insert_after、erase_after等操作时需通过before_begin()获取前置迭代器。常用方法包括push_front、emplace_front、pop_front及remove等，适合内存敏感和顺序访问应用，若需随机访问或频繁查重，则推荐vector或deque。

c++ forward_list单向链表用法_c++轻量级链表的插入与删除

C++ 中的 forward_list 是一种轻量级的单向链表容器，属于标准模板库（STL）的一部分。与 list（双向链表）相比，它只支持单向遍历，但内存开销更小，适合对插入、删除操作频繁且不需要反向访问的场景。

forward_list 基本特性

forward_list 定义在头文件 <forward_list></forward_list> 中，其主要特点包括：

单向链表结构：每个节点只保存下一个节点的指针
不提供 size() 方法（C++11 起可选实现），需用 distance(begin(), end()) 获取长度
插入和删除操作高效，时间复杂度为 O(1)，前提是已知位置的迭代器
不支持反向迭代器

注意：forward_list 的设计目标是极简和高效，因此接口与其他序列容器略有不同。

插入元素：从头部和指定位置添加节点

由于是单向链表，forward_list 不直接支持在任意位置的随机插入，而是通过“在给定位置之后”插入来实现。

常用插入方法包括：

push_front()：在链表头部插入一个元素
insert_after()：在指定位置之后插入元素
emplace_front() 和 emplace_after()：原地构造对象，减少拷贝开销

示例代码：

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

int main() {
    forward_list<int> flist = {1, 3, 4};

    flist.push_front(0);                    // 结果: 0 1 3 4
    auto pos = flist.before_begin();        // 获取前一个位置（用于 insert_after）
    ++pos;                                  // 移动到值为1的节点前（即插入到1之后）
    flist.insert_after(pos, 2);             // 在1之后插入2 → 0 1 2 3 4

    for (int n : flist) {
        cout << n << " ";
    }
    // 输出: 0 1 2 3 4
}

删除元素：移除头部或指定位置后的节点

删除操作也遵循单向逻辑，只能高效删除当前位置之后的元素。

常用删除方法：

Lateral App

整理归类论文

85 查看详情 Lateral App

pop_front()：删除第一个元素
erase_after()：删除指定位置之后的一个或多个元素

示例：

flist.pop_front();                                // 删除首元素 → 1 2 3 4

auto pos = flist.before_begin();
++pos;                                            // 指向1
flist.erase_after(pos);                           // 删除2 → 1 3 4

若要删除某个特定值（如删除所有值为3的节点），可结合循环使用：

flist.remove(3);  // 直接移除所有等于3的元素

或者手动遍历：

for (auto it = flist.before_begin(); it != flist.end(); ) {
    auto next = it;
    ++next;
    if (next != flist.end() && *next == 3) {
        it = flist.erase_after(it);
    } else {
        it = next;
    }
}