C++ list链表教程：从入门到实战

一、什么是list链表？

在C++标准库中，list是一种双向链表数据结构。与数组不同，链表中的元素在内存中并不连续存储，而是通过指针（或引用）连接起来的。每个节点包含数据和指向前一个/后一个节点的指针，这使得list在插入和删除操作上具有高效性。

二、list的基本使用

首先，我们需要包含必要的头文件并了解基本的声明方式：

#include <iostream>
#include <list>  // 使用list必须包含的头文件
#include <algorithm>  // 用于使用算法函数

using namespace std;

int main() {
    // 1. 声明list的多种方式
    list<int> myList1;  // 空list
    list<int> myList2(5, 10);  // 包含5个10的list: [10,10,10,10,10]
    list<int> myList3 = {1, 2, 3, 4, 5};  // 初始化列表
    list<int> myList4(myList3);  // 拷贝构造
    list<int> myList5(myList3.begin(), myList3.end());  // 区间构造
    
    // 2. 常用操作函数演示
    cout << "=== 基本操作演示 ===" << endl;
    
    // 2.1 添加元素
    myList1.push_back(10);  // 在尾部添加元素
    myList1.push_front(20);  // 在头部添加元素
    cout << "添加元素后myList1: ";
    for (int num : myList1) {
        cout << num << " ";
    }
    cout << endl;
    
    // 2.2 访问元素
    // list不支持随机访问（如myList[0]），需通过迭代器访问
    list<int>::iterator it = myList3.begin();
    cout << "myList3第一个元素: " << *it << endl;
    
    // 2.3 删除元素
    myList3.pop_back();  // 删除尾部元素
    myList3.pop_front();  // 删除头部元素
    cout << "删除首尾元素后myList3: ";
    for (int num : myList3) {
        cout << num << " ";
    }
    cout << endl;
    
    // 2.4 查找元素
    it = find(myList3.begin(), myList3.end(), 3);
    if (it != myList3.end()) {
        cout << "找到元素3，位置为: " << distance(myList3.begin(), it) << endl;
    }
    
    // 2.5 其他常用函数
    cout << "myList3大小: " << myList3.size() << endl;
    cout << "myList3是否为空: " << (myList3.empty() ? "是" : "否") << endl;
    
    // 3. 迭代器的使用
    cout << "\n=== 迭代器使用演示 ===" << endl;
    cout << "正向遍历myList3: ";
    for (it = myList3.begin(); it != myList3.end(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
    
    cout << "反向遍历myList3: ";
    list<int>::reverse_iterator rIt;
    for (rIt = myList3.rbegin(); rIt != myList3.rend(); ++rIt) {
        cout << *rIt << " ";
    }
    cout << endl;
    
    // 4. 自定义类型的list
    cout << "\n=== 自定义类型list演示 ===" << endl;
    struct Person {
        string name;
        int age;
        
        Person(string n, int a) : name(n), age(a) {}
    };
    
    list<Person> personList;
    personList.push_back(Person("张三", 25));
    personList.push_back(Person("李四", 30));
    personList.push_front(Person("王五", 22));
    
    cout << "人员列表: " << endl;
    for (const Person& p : personList) {
        cout << "姓名: " << p.name << ", 年龄: " << p.age << endl;
    }
    
    // 5. list的高级操作
    cout << "\n=== 高级操作演示 ===" << endl;
    list<int> listA = {1, 2, 3};
    list<int> listB = {4, 5, 6};
    
    // 5.1 合并两个list
    listA.merge(listB);  // listB会被清空
    cout << "合并后listA: ";
    for (int num : listA) {
        cout << num << " ";
    }
    cout << endl;
    
    // 5.2 排序与反转
    listA.sort();  // 升序排序
    cout << "排序后listA: ";
    for (int num : listA) {
        cout << num << " ";
    }
    cout << endl;
    
    listA.reverse();  // 反转
    cout << "反转后listA: ";
    for (int num : listA) {
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}

三、list与vector的区别

理解list和vector的差异有助于我们在合适的场景选择合适的数据结构：

四、list的迭代器

list使用双向迭代器，这意味着：

• 可以向前（++it）和向后（--it）移动
• 不支持随机访问操作（如it + n或it - n）
• 迭代器类型包括：
  • iterator：正向迭代器
  • const_iterator：常量正向迭代器
  • reverse_iterator：反向迭代器
  • const_reverse_iterator：常量反向迭代器

五、list的常用函数详解

下面是list中最常用的一些函数及其功能说明：

1. 元素操作

   • push_back(value)：在列表末尾添加元素
   • push_front(value)：在列表开头添加元素
   • pop_back()：删除末尾元素
   • pop_front()：删除开头元素
   • insert(iterator, value)：在指定位置插入元素
   • erase(iterator)：删除指定位置的元素

2. 访问与遍历

   • begin()：返回指向第一个元素的迭代器
   • end()：返回指向最后一个元素之后的迭代器
   • rbegin()：返回指向最后一个元素的反向迭代器
   • rend()：返回指向第一个元素之前的反向迭代器
   • front()：返回第一个元素的引用
   • back()：返回最后一个元素的引用

3. 容量操作

   • size()：返回列表中元素的数量
   • empty()：判断列表是否为空
   • max_size()：返回列表可容纳的最大元素数量

4. 修改操作

   • clear()：删除列表中的所有元素
   • swap(list)：交换两个列表的内容
   • sort()：对列表进行排序
   • reverse()：反转列表中的元素顺序
   • merge(list)：合并两个已排序的列表

六、实战案例：使用list实现简单通讯录

下面通过一个实际案例来展示list的综合应用：

#include <iostream>
#include <list>
#include <string>
#include <algorithm>

using namespace std;

// 联系人结构体
struct Contact {
    string name;
    string phone;
    string email;
    
    Contact(string n, string p, string e) : name(n), phone(p), email(e) {}
    
    // 用于显示联系人信息
    void display() const {
        cout << "姓名: " << name << ", 电话: " << phone << ", 邮箱: " << email << endl;
    }
    
    // 用于比较联系人姓名（用于排序）
    bool operator<(const Contact& other) const {
        return name < other.name;
    }
};

int main() {
    list<Contact> contactList;
    
    // 添加一些联系人
    contactList.push_back(Contact("张三", "13800138001", "zhangsan@example.com"));
    contactList.push_back(Contact("李四", "13900139001", "lisi@example.com"));
    contactList.push_back(Contact("王五", "13700137001", "wangwu@example.com"));
    
    int choice;
    string name, phone, email;
    list<Contact>::iterator it;
    
    while (true) {
        // 显示菜单
        cout << "\n=== 简单通讯录 ===" << endl;
        cout << "1. 显示所有联系人" << endl;
        cout << "2. 添加新联系人" << endl;
        cout << "3. 删除联系人" << endl;
        cout << "4. 查找联系人" << endl;
        cout << "5. 排序联系人" << endl;
        cout << "0. 退出" << endl;
        cout << "请选择操作: ";
        cin >> choice;
        
        if (choice == 0) {
            cout << "感谢使用，再见！" << endl;
            break;
        }
        
        switch (choice) {
            case 1:
                // 显示所有联系人
                if (contactList.empty()) {
                    cout << "通讯录为空！" << endl;
                } else {
                    cout << "联系人列表：" << endl;
                    for (const Contact& c : contactList) {
                        c.display();
                    }
                }
                break;
                
            case 2:
                // 添加新联系人
                cout << "请输入姓名: ";
                cin >> name;
                cout << "请输入电话: ";
                cin >> phone;
                cout << "请输入邮箱: ";
                cin >> email;
                contactList.push_back(Contact(name, phone, email));
                cout << "联系人添加成功！" << endl;
                break;
                
            case 3:
                // 删除联系人
                cout << "请输入要删除的联系人姓名: ";
                cin >> name;
                it = find_if(contactList.begin(), contactList.end(),
                            [name](const Contact& c) { return c.name == name; });
                if (it != contactList.end()) {
                    contactList.erase(it);
                    cout << "联系人删除成功！" << endl;
                } else {
                    cout << "未找到该联系人！" << endl;
                }
                break;
                
            case 4:
                // 查找联系人
                cout << "请输入要查找的联系人姓名: ";
                cin >> name;
                it = find_if(contactList.begin(), contactList.end(),
                            [name](const Contact& c) { return c.name == name; });
                if (it != contactList.end()) {
                    cout << "找到联系人：" << endl;
                    it->display();
                } else {
                    cout << "未找到该联系人！" << endl;
                }
                break;
                
            case 5:
                // 按姓名排序联系人
                contactList.sort();
                cout << "联系人已按姓名排序！" << endl;
                break;
                
            default:
                cout << "无效选择，请重新输入！" << endl;
        }
    }
    
    return 0;
}

七、list的性能特点与适用场景

1. 优点

   • 在任意位置插入和删除元素的时间复杂度为O(1)（已知迭代器位置）
   • 不需要预先分配内存，动态增长更灵活
   • 双向迭代器支持正向和反向遍历

2. 缺点

   • 不支持随机访问，访问中间元素需要从头遍历
   • 每个节点需要额外的指针空间，内存开销较大
   • 缓存利用率较低，性能可能不如vector

3. 适用场景

   • 需要频繁在序列中间进行插入和删除操作
   • 不需要随机访问元素
   • 数据量动态变化较大，难以预先估计

八、总结

C++的list容器是一种非常有用的双向链表实现，它在插入和删除操作上表现出色。通过本教程，你应该已经掌握了：

• list的基本概念和特点
• list的声明和初始化方法
• list的常用操作和函数
• list迭代器的使用
• list与vector的区别
• list在实际场景中的应用

在实际编程中，根据具体需求选择合适的数据结构是非常重要的。当你需要频繁进行插入和删除操作，而不需要随机访问时，list会是一个很好的选择。