【C++】: list介绍以及模拟实现

List是STL中的双向链表，我们通常使用它来作为一种可灵活进行**数据更换（即插入和删除）**的数据结构。

std::list 是 C++ STL 中的一个容器类，底层实现是 双向链表，相比于 vector（底层是数组），它在插入和删除元素时性能更好（不需要移动元素），但在随机访问方面效率较低。

它定义在头文件 <list> 中。

我们来看看它基本的特性都有哪些。

一、基本特性

特性	说明
存储结构	双向链表（每个节点含有前驱和后继指针）
随机访问	不支持（不像 `vector[i]`）
插入/删除效率	高效，O(1)，特别适合频繁插入和删除
内存使用	比 `vector` 更高，因为每个元素多了两个指针
迭代器稳定性	插入删除不会使其他元素的迭代器失效

)

二、list的使用

因为list的接口较多，而且大部分都是STL其他数据结构的同类接口，所以这里只介绍它较为特殊和带有自身特性的。

访问接口

接口	功能
`front()` / `back()`	获取首/尾元素的引用
`begin()` / `end()`	获取迭代器范围（正向）
`rbegin()` / `rend()`	反向迭代器范围

修改接口

接口	功能
`push_back(val)` / `push_front(val)`	尾部/头部插入元素
`pop_back()` / `pop_front()`	删除尾部/头部元素
`insert(pos, val)`	在迭代器 `pos` 前插入元素
`insert(pos, n, val)`	插入 `n` 个 `val`
`insert(pos, first, last)`	插入一段区间
`emplace(pos, args...)`	原地构造插入
`erase(pos)`	删除 `pos` 位置的元素
`erase(first, last)`	删除区间元素
`clear()`	清空链表

链表操作接口

接口	功能
`remove(val)`	删除所有等于 `val` 的元素
`remove_if(pred)`	根据条件删除元素
`unique()`	删除连续重复元素
`sort()`	排序（归并排序）
`reverse()`	反转链表
`merge(list& other)`	合并两个有序链表，`other` 清空
`splice(pos, other)`	将 `other` 整体剪切到 `pos` 处
`splice(pos, other, it)`	将 `other` 的一个元素移动过来
`splice(pos, other, first, last)`	移动区间元素

三、list的迭代器详解

对于 std::list 来说，它的迭代器是一个双向迭代器（Bidirectional Iterator），支持：

向前 ++it
向后 --it

而对于反向迭代器来说，它的 ++ 就是正向迭代器的 – ，灵活变通，可以互相成为对方。

另外关于迭代器失效问题，可参考下表。

操作	是否导致迭代器失效	说明
`insert()` 插入	❌ 不失效（除非插入位置的迭代器）	其他迭代器仍有效
`push_front/back()`	❌ 不失效	因为底层是链表，不会移动其它元素
`erase(it)` 删除	✅ `it` 失效，其他迭代器仍有效	必须用返回的新迭代器继续
`clear()` 清空	✅ 所有迭代器失效	全部节点销毁
`splice()`, `merge()`	✅ 涉及元素的迭代器失效	非目标容器的迭代器失效

总结起来就是：在 std::list 中，只有 你删除了元素 或 清空容器 时，相关迭代器才会失效；插入和其他元素无关的操作不会导致其他迭代器失效，这也是它比 vector 更安全的一大优势。

四、list模拟实现

好，接下来就是list 的模拟实现。

实现了一个简化版的 C++ 双向链表模板类 List<T>，并自定义了双向迭代器与反向迭代器，功能上模拟了 std::list 的许多核心操作。🧩 代码详解：自定义双向链表 joolin::List<T>

命名空间声明

namespace joolin { ... }

节点结构体 `ListNode<T>`

template <typename T>
struct ListNode {
    T data;
    ListNode<T>* prev;
    ListNode<T>* next;

    ListNode(const T &val = T()) : data(val), prev(nullptr), next(nullptr) {}
};

data: 存储节点中的值。
prev, next: 分别指向前一个和后一个节点。
构造函数：默认值为 T()，指针为空。

用于实现双向链表结构的核心单元。

类定义 `List<T>`

基本成员

private:
    ListNode<T> *head;
    ListNode<T> *tail;
    size_t size;

head, tail: 指向链表的头和尾。
size: 当前链表中元素数量。

嵌套类：正向迭代器 `Iterator`

class Iterator {
private:
    ListNode<T>* node;

public:
    Iterator(ListNode<T>* n = nullptr) : node(n) {}
    T& operator*() { return node->data; }
    ...
};

自定义一个双向迭代器类，支持：
- 解引用 *
- 前向移动 ++
- 后向移动 --
- 比较运算符 ==, !=

可以用它像 STL 一样遍历链表：

for (auto it = list.begin(); it != list.end(); ++it) {
    std::cout << *it << std::endl;
}

嵌套类：反向迭代器 `ReverseIterator`

class ReverseIterator { ... }

功能类似 Iterator，但：
- ++ 实际上是向前走 prev。
- 用于从尾到头遍历链表。

类似于 std::list::rbegin() 和 rend()。

构造 & 析构函数

List() : head(nullptr), tail(nullptr), size(0) {}

~List() {
    while (head) {
        ListNode<T>* temp = head;
        head = head->next;
        delete temp;
    }
    tail = nullptr;
    size = 0;
}

默认构造函数：初始化为空链表。
析构函数：释放所有节点的内存。

清空链表 `clear()`

void clear() {
    while (head) {
        ListNode<T>* temp = head;
        head = head->next;
        delete temp;
    }
    tail = nullptr;
    size = 0;
}

和析构函数类似，但不销毁对象，只清空元素。

排序函数 `sort()`

void sort() {
    if (size < 2) return;
    for (ListNode<T>* i = head; i != nullptr; i = i->next) {
        for (ListNode<T>* j = i->next; j != nullptr; j = j->next) {
            if (i->data > j->data) {
                std::swap(i->data, j->data);
            }
        }
    }
}

使用 冒泡排序 对链表排序（稳定、适用于链表）。
排序的是 data 值，而不是节点指针。

插入元素：`push_back()` 与 `push_front()`

void push_back(const T &value) { ... }
void push_front(const T &value) { ... }

创建新节点并插入尾部/头部。
更新 tail 或 head 指针。
空链表时两者处理方式相同。

删除元素：`pop_back()` 与 `pop_front()`

void pop_back() { ... }
void pop_front() { ... }

删除头或尾部元素。
更新 head 和 tail，释放内存。

元素访问接口

T front() const { ... }
T back() const { ... }
size_t get_size() const { return size; }

front()、back()：返回第一个和最后一个元素。
抛出异常如果链表为空。
get_size()：返回链表当前长度。

插入指定位置 `insert(pos, value)`

void insert(size_t pos, const T &value) { ... }

在指定 pos 位置插入（0为头，size为尾）。
如果越界则抛出 out_of_range 异常。
中间插入时更新前后指针连接。

删除指定位置 `erase(pos)`

void erase(size_t pos) { ... }

越界检查。
若 pos == 0 调用 pop_front()。

若 pos == size - 1 错误！⚠️

if(pos = size - 1)  // ❌ 错误！应该是 ==

应该写成：

if (pos == size - 1)

中间删除时，断开连接、释放节点。

begin()/end() 与 rbegin()/rend()

Iterator begin() { return Iterator(head); }
Iterator end() { return Iterator(nullptr); }

ReverseIterator rbegin() { return ReverseIterator(tail); }
ReverseIterator rend() { return ReverseIterator(nullptr); }

提供正向和反向遍历的起点与终点。

总代码如下：

#include <iostream>
namespace joolin
{
    template <typename T>
    struct ListNode
    {
        T data;
        // 两个指针
        ListNode<T> *prev;
        ListNode<T> *next;

        // 构造函数
        ListNode(const T &val = T())
            : data(val), prev(nullptr), next(nullptr) {}
    };

    template <typename T>
    class List
    {
    private:
        ListNode<T> *head;
        ListNode<T> *tail;
        size_t size;

    public:
        //迭代器
        class Iterator{
            private:
            ListNode<T>* node;

            public:
            Iterator(ListNode<T>* n = nullptr) : node(n) {}
            T& operator *() { return node->data; }
            
            Iterator& operator++() {
                node = node->next;
                return *this;
            }
            Iterator operator++(int) {
                Iterator temp = *this;
                node = node->next;
                return temp;
            }
            Iterator& operator--() {
                node = node->prev;
                return *this;
            }
            Iterator operator--(int) {
                Iterator temp = *this;
                node = node->prev;
                return temp;
            }
            bool operator==(const Iterator& other) const { return node == other.node; }
            bool operator!=(const Iterator& other) const { return node != other.node; }

        };

        //返回迭代器
        Iterator begin() { return Iterator(head); }
        Iterator end() { return Iterator(nullptr); }

        //反向迭代器
        // 反向迭代器
        class ReverseIterator {
            private:
                ListNode<T>* node;
    
            public:
                ReverseIterator(ListNode<T>* n = nullptr) : node(n) {}
    
                T& operator*() { return node->data; }
                ReverseIterator& operator++() {
                    node = node->prev;
                    return *this;
                }
                ReverseIterator operator++(int) {
                    ReverseIterator temp = *this;
                    node = node->prev;
                    return temp;
                }
                bool operator==(const ReverseIterator& other) const { return node == other.node; }
                bool operator!=(const ReverseIterator& other) const { return node != other.node; }
            };
    
            //返回反向迭代器
            ReverseIterator rbegin() { return ReverseIterator(tail); }
            ReverseIterator rend() { return ReverseIterator(nullptr); }


        // 构造函数
        List()
            : head(nullptr), tail(nullptr), size(0)
        {
        }

        // 析构函数
        ~List()
        {
            while (head)
            {
                ListNode<T> *temp = head;
                head = head->next;
                delete temp;
            }
            tail = nullptr;
            size = 0;
        }

        //清除
        void clear()
        {
            while (head)
            {
                ListNode<T>* temp = head;
                head = head -> next;
                delete temp;
                /* code */
            }
            tail =nullptr;
            size = 0;   
        }

        //排序
        void sort()
        {
            if(size < 2) return;
            for (ListNode<T>* i = head; i != nullptr; i = i->next) {
                for (ListNode<T>* j = i->next; j != nullptr; j = j->next) {
                    if (i->data > j->data) {
                        std::swap(i->data, j->data);
                    }
                }
            }
        }



        // 增加
        void push_back(const T &value)
        {
            ListNode<T> *newNode = new ListNode<T>(value);
            if (!head)
            {
                head = tail = newNode;
            }
            else
            {
                tail->next = newNode;
                newNode->prev = tail;
                tail = newNode;
            }
            ++size;
        }

        void push_front(const T &value)
        {
            ListNode<T> *newNode = new ListNode<T>(value);
            if (!head)
            {
                head = tail = newNode;
            }
            else
            {
                newNode->next = head;
                head->prev = newNode;
                head = newNode;
            }
            ++size;
        }

        // 删除
        void pop_back()
        {
            if (!tail)
                return;
            if (tail == head)
            {
                delete tail;
                head = tail = nullptr;
            }
            else
            {
                ListNode<T> *temp = tail;
                tail = tail->prev;
                tail->next = nullptr;
                delete temp;
            }
            --size;
        }

        void pop_front()
        {
            if (!head)
                return;
            if (head == tail)
            {
                delete head;
                head = tail = nullptr;
            }
            else
            {
                ListNode<T> *temp = head;
                head = head->next;
                head->prev = nullptr;
                delete temp;
            }
            --size;
        }

        // 返回
        T front() const
        {
            if (!head) {
                throw std::runtime_error("List is empty!");
            }
            return head->data;
        }
        T back() const
        {
            if (!tail) {
                throw std::runtime_error("List is empty!");
            }
            return tail->data;
        }
        size_t get_size() const
        {
            return size;
        }

        // 插入和消除
        void insert(size_t pos, const T &value)
        {
            if (pos > size)
                throw std::out_of_range("Position out of range");
            if (pos == 0)
            {
                push_front(value);
                return;
            }
            if (pos == size)
            {
                push_back(value);
                return;
            }

            ListNode<T> *current = head;
            for (size_t i = 0; i < pos - 1; i++)
            {
                current = current->next;
            }

            ListNode<T> *newNode = new ListNode<T>(value);
            newNode->next = current->next;
            newNode->prev = current;
            current->next->prev = newNode;
            current->next = newNode;

            ++size;
        }

        void erase(size_t pos)
        {
            if (pos >= size) throw std::out_of_range("Position out of range");
            if(pos == 0){
                pop_front();
                return;
            }
            if(pos = size - 1){
                pop_back();
                return;
            }
            
            ListNode<T>* current = head;
            for (size_t i = 0; i < pos; i++)
            {
                current = current -> next;
            }

            current->prev->next = current ->next;
            current->next->prev = current -> prev;

            --size;            
        }
    };

} // namespace joolin

转载自CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/Skrrapper/article/details/152092127

【C++】: list介绍以及模拟实现

一、基本特性

二、list的使用

三、list的迭代器详解

四、list模拟实现

命名空间声明

节点结构体 `ListNode<T>`

类定义 `List<T>`

基本成员

嵌套类：正向迭代器 `Iterator`

嵌套类：反向迭代器 `ReverseIterator`

构造 & 析构函数

清空链表 `clear()`

排序函数 `sort()`

插入元素：`push_back()` 与 `push_front()`

删除元素：`pop_back()` 与 `pop_front()`

元素访问接口

插入指定位置 `insert(pos, value)`

删除指定位置 `erase(pos)`

begin()/end() 与 rbegin()/rend()

评论

评论列表

微信小程序

QQ小程序

关于作者

【C++】: list介绍以及模拟实现

一、基本特性

二、list的使用

三、list的迭代器详解

四、list模拟实现

命名空间声明

节点结构体 ListNode<T>

类定义 List<T>

基本成员

嵌套类：正向迭代器 Iterator

嵌套类：反向迭代器 ReverseIterator

构造 & 析构函数

清空链表 clear()

排序函数 sort()

插入元素：push_back() 与 push_front()

删除元素：pop_back() 与 pop_front()

元素访问接口

插入指定位置 insert(pos, value)

删除指定位置 erase(pos)

begin()/end() 与 rbegin()/rend()

评论

评论列表

微信小程序

QQ小程序

关于作者

节点结构体 `ListNode<T>`

类定义 `List<T>`

嵌套类：正向迭代器 `Iterator`

嵌套类：反向迭代器 `ReverseIterator`

清空链表 `clear()`

排序函数 `sort()`

插入元素：`push_back()` 与 `push_front()`

删除元素：`pop_back()` 与 `pop_front()`

插入指定位置 `insert(pos, value)`

删除指定位置 `erase(pos)`