【C++】模拟实现 list：双向链表的构建与解析

list 类的核心任务之一便是存储各种类型的元素。它采用节点的形式，每个节点不仅包含数据本身，还具备指向前一个节点（prev）和后一个节点（next）的指针。这些节点如同链条上的一个个坚固环扣，相互连接，构成了一个灵活的数据存储结构。这种非连续内存存储方式使得元素的插入和删除操作不会像数组那样牵一发而动全身，而是能够高效地在链表中任意位置进行操作，就像在链条上轻松增减环扣一样便捷😃。

（二）元素访问与修改✍️

虽然不能像数组那样通过索引迅速定位元素，但 list 为我们提供了强大的迭代器功能。迭代器就像是一位忠诚的导航员🧭，带领我们沿着链表的节点依次前行，从而逐个访问链表中的元素。在遍历过程中，我们不仅可以读取每个元素的值，还能够对其进行修改，以满足各种数据处理需求。此外，在指定位置插入新元素以及删除指定位置的元素也是 list 类的重要功能。插入新元素时，就如同在链条的特定位置巧妙地插入一个新环扣，而删除元素则像是精准地移除某个环扣，同时确保链表的结构依然完整有序😎。

（三）元素数量相关操作📏

了解链表中当前元素的数量对于程序的逻辑控制和数据处理至关重要。list 类需要提供一种方法来获取元素的数量，以便我们在编写程序时能够准确把握链表的规模。当我们对链表的大致长度有一定预期时，虽然 list 无法像数组那样预先分配连续的大块内存，但我们可以根据实际情况进行一些优化策略，例如提前创建一定数量的节点，以减少后续频繁创建节点所带来的开销，提高程序的执行效率😉。

（四）迭代器支持🔍

强大而灵活的迭代器是 list 类的灵魂所在。迭代器就像是一把神奇的钥匙🔑，它为我们打开了遍历链表的大门。通过迭代器，我们可以从链表的头部开始，沿着节点之间的指针链接，逐个访问每个元素，直到到达链表的尾部。在遍历过程中，我们能够方便地进行各种操作，如插入新元素、删除当前元素等。迭代器的存在使得对链表的操作变得简洁、高效且直观，大大提升了我们处理链表数据的能力😃。

（五）内存管理🧹

有效的内存管理是确保程序稳定运行的基石。list 类必须能够精确地管理内存，当某个节点不再被使用时，及时回收其所占用的内存空间，避免内存泄漏的风险。在进行节点的插入和删除操作时，也要正确地分配和回收内存，确保链表在整个生命周期内的内存使用始终处于健康、合理的状态。这就好比一个严谨的仓库管理员，精心打理着链表的内存资源，确保每一寸内存都得到妥善的利用和释放😎。

三、模拟实现的关键步骤和代码解析💻

（一）类的定义🎯

template<typename T> class MyList { private: struct ListNode { T data; ListNode* prev; ListNode* next; ListNode(const T& value) : data(value), prev(nullptr), next(nullptr) {} }; ListNode* head; ListNode* tail; size_t size_; public: MyList(); MyList(size_t n, const T& value = T()); MyList(const MyList<T>& other); ~MyList(); size_t size() const; bool empty() const; void push_front(const T& value); void push_back(const T& value); void pop_front(); void pop_back(); void insert(iterator pos, const T& value); void erase(iterator pos); typedef ListNode* iterator; iterator begin(); iterator end(); };

解释：我们定义了一个名为 MyList 的模板类，它能够存储任意类型的元素。其中，内部结构体 ListNode 代表链表中的节点，包含数据成员 data 以及指向前一个节点的指针 prev 和后一个节点的指针 next。通过 head 和 tail 指针，我们可以快速定位到链表的头部和尾部节点，size_ 变量则用于记录链表中当前元素的数量。此外，类中还声明了一系列成员函数，用于实现链表的各种操作，这些函数将在后续详细阐述😉。

（二）构造函数实现🔨

1.默认构造函数

template<typename T> MyList<T>::MyList() : head(nullptr), tail(nullptr), size_(0) {}

默认构造函数创建一个空的链表，将头指针 head 和尾指针 tail 都初始化为 nullptr，表示链表中没有节点，元素数量 size_ 为 0。这就像是构建了一条没有任何环扣的空链条，等待着元素的加入😃。

2.指定大小和初始值的构造函数

template<typename T> MyList<T>::MyList(size_t n, const T& value) : head(nullptr), tail(nullptr), size_(0) { for (size_t i = 0; i < n; ++i) { push_back(value); } }

这个构造函数根据指定的数量 n 和初始值 value 创建一个包含 n 个相同元素的链表。它通过多次调用 push_back 函数，将 value 逐个添加到链表的尾部，就如同在一条空链条上依次挂上 n 个相同的环扣，构建出一个具有特定长度和初始值的链表🧐。

3.拷贝构造函数

template<typename T> MyList<T>::MyList(const MyList<T>& other) : head(nullptr), tail(nullptr), size_(0) { for (ListNode* node = other.head; node!= nullptr; node = node->next) { push_back(node->data); } }

拷贝构造函数用于创建一个与现有链表 other 完全相同的新链表。它通过遍历 other 链表的每个节点，获取节点中的数据，并使用 push_back 函数将这些数据依次添加到新链表的尾部，从而实现了链表的深度拷贝。这就好比复制了一条一模一样的链条，包括链条上的每个环扣及其连接关系，确保新链表与原链表在数据和结构上完全一致😉。

（三）析构函数实现🚮

template<typename T> MyList<T>::~MyList() { while (head!= nullptr) { ListNode* next = head->next; delete head; head = next; } }

析构函数在链表对象生命周期结束时发挥关键作用，负责释放链表所占用的内存空间。它从链表的头部开始，逐个删除节点。在删除每个节点之前，先保存下一个节点的指针，然后释放当前节点的内存，最后将头指针指向下一个节点。这个过程就像从链条的头部开始，逐个拆卸环扣，直到整个链条被完全拆除，确保不会有任何内存泄漏，保证程序的内存管理健康有序😎。

（四）获取元素数量和判断是否为空函数📏🤔

1.获取元素数量函数

template<typename T> size_t MyList<T>::size() const { return size_; }

该函数简单直接地返回链表中当前元素的数量 size_，就像数一下链条上的环扣个数一样，为我们提供了关于链表规模的重要信息😃。

2. 判断是否为空函数

template<typename T> bool MyList<T>::empty() const { return size_ == 0; }

判断链表是否为空只需检查元素数量 size_ 是否为 0。如果 size_ 等于 0，则表示链表为空，即没有任何环扣，此时函数返回 true；否则返回 false，表明链表中包含至少一个元素😉。

（五）添加和删除元素函数🎯

1.在头部添加元素函数

template<typename T> void MyList<T>::push_front(const T& value) { ListNode* newNode = new ListNode(value); if (head == nullptr) { head = tail = newNode; } else { newNode->next = head; head->prev = newNode; head = newNode; } ++size_; }

此函数用于在链表的头部添加一个新元素。首先创建一个新节点 newNode，并将其数据成员初始化为 value。如果链表为空（即 head 为 nullptr），则将新节点同时设置为头节点和尾节点；否则，将新节点插入到头节点之前，通过调整指针关系，使新节点成为新的头节点。这个过程就像在链条的最前端插入一个新环扣，然后将其与原有的头部环扣正确连接起来，最后更新元素数量 size_😎。

2. 在尾部添加元素函数

template<typename T> void MyList<T>::push_back(const T& value) { ListNode* newNode = new ListNode(value); if (tail == nullptr) { head = tail = newNode; } else { newNode->prev = tail; tail->next = newNode; tail = newNode; } ++size_; }

push_back 函数用于在链表的尾部添加一个新元素。同样先创建新节点 newNode，若链表为空，则新节点成为头节点和尾节点；否则，将新节点插入到尾节点之后，通过更新指针，使新节点成为新的尾节点。这就如同在链条的末尾挂上一个新环扣，确保链条的完整性和连贯性，同时增加元素数量 size_😉。

3. 删除头部元素函数

template<typename T> void MyList<T>::pop_front() { if (head!= nullptr) { ListNode* next = head->next; if (next!= nullptr) { next->prev = nullptr; } else { tail = nullptr; } delete head; head = next; --size_; } }

删除链表头部元素的函数。如果链表不为空，先保存头节点的下一个节点指针 next。若 next 不为空，则将其前驱指针设置为 nullptr，使其成为新的头节点；若 next 为空，说明链表中只有一个节点，删除头节点后链表为空，将尾指针 tail 也设置为 nullptr。然后释放头节点的内存，并更新头指针 head 和元素数量 size_，就像从链条的头部取下一个环扣，同时调整剩余环扣的连接关系😎。

4. 删除尾部元素函数

template<typename T> void MyList<T>::pop_back() { if (tail!= nullptr) { ListNode* prev = tail->prev; if (prev!= nullptr) { prev->next = nullptr; } else { head = nullptr; } delete tail; tail = prev; --size_; } }

删除链表尾部元素的操作。若链表非空，先保存尾节点的前一个节点指针 prev。若 prev 不为空，则将其后继指针设为 nullptr，使其成为新的尾节点；若 prev 为空，表明链表只有一个节点，删除尾节点后链表为空，将头指针 head 设为 nullptr。接着释放尾节点内存，更新尾指针 tail 和元素数量 size_，如同从链条末端摘下一个环扣并调整剩余部分的连接😉。

5. 在指定位置插入元素函数

template<typename T> void MyList<T>::insert(iterator pos, const T& value) { if (pos == begin()) { push_front(value); return; } if (pos == end()) { push_back(value); return; } ListNode* newNode = new ListNode(value); newNode->prev = pos->prev; newNode->next = pos; pos->prev->next = newNode; pos->prev = newNode; ++size_; }

在指定位置插入元素的函数。如果插入位置为链表头部（即 pos 等于 begin() 返回的迭代器），则调用 push_front 函数；若插入位置为链表尾部（即 pos 等于 end() 返回的迭代器），则调用 push_back 函数。否则，创建新节点 newNode，并通过调整指针关系将其插入到指定位置 pos 之前，使链表的结构保持正确。插入完成后，更新元素数量 size_，就像在链条的特定位置巧妙地插入一个新环扣，保持链条的完整性和连贯性😎。

6. 删除指定位置元素函数

template<typename T> void MyList<T>::erase(iterator pos) { if (pos == head) { pop_front(); return; } if (pos == tail) { pop_back(); return; } pos->prev->next = pos->next; pos->next->prev = pos->prev; delete pos; --size_; }

删除指定位置元素的函数。若删除位置为头节点（即 pos 等于 head），则调用 pop_front 函数；若为尾节点（即 pos 等于 tail），则调用 pop_back 函数。否则，通过调整删除位置前后节点的指针关系，跳过要删除的节点，然后释放该节点的内存，并更新元素数量 size_，就像从链条中间精准地移除一个环扣，同时确保剩余部分正确连接😉。

（六）迭代器相关函数🔍

1.迭代器类型定义

template<typename T> typedef ListNode* MyList<T>::iterator;

这里定义了迭代器的类型为指向链表节点的指针 ListNode*。通过这个指针，我们可以在链表中移动，访问每个节点的数据和指针成员，就像给我们提供了一个在链条上行走的工具，方便我们遍历链表中的元素😃。

2. 起始迭代器函数

template<typename T> typename MyList<T>::iterator MyList<T>::begin() { return head; }

起始迭代器函数返回指向链表头部节点的指针，这就像是给我们一个站在链条头部的起点，准备开始遍历链表。从这个位置出发，我们可以沿着节点之间的指针链接，逐个访问链表中的元素😎。

3. 结束迭代器函数

template<typename T> typename MyList<T>::iterator MyList<T>::end() { return nullptr; }

结束迭代器函数返回一个特殊的值 nullptr，表示链表的结束位置。在遍历链表时，当迭代器到达这个位置时，就意味着已经遍历完整个链表。它就像在链条的末尾设置了一个虚拟的终点标志，帮助我们控制遍历的范围😉。

四、总结😎

通过模拟实现 list 类，我们仿佛置身于一个充满挑战与惊喜的编程探险之旅，深入探索了双向链表的奇妙世界。从链表节点的精巧构建，到各种操作函数的细致实现，再到内存管理的严格把控，每一个环节都彰显了链表数据结构的独特魅力和强大功能。希望大家在这次旅程中不仅掌握了 list 类的模拟实现方法，更能深刻理解双向链表的本质，为今后在编程领域中运用各种数据结构解决复杂问题积累宝贵的经验和知识💪！继续加油，探索更多编程世界的奥秘吧😉！

以后我将持续深入研究其他数据结构与算法的奥秘，并将它们巧妙地应用于实际项目中，为大家带来更多实用且有趣的编程知识分享！欢迎关注我👉【A Charmer】