从零开始实现 C++ 双向链表：深入明白链表底层原理

前言：

   在 C++ 标准库中，std::list 是一种非经常用的数据布局，其底层接纳了双向链表的实现。在实际开辟中，双向链表是一种具有机动插入和删除操纵的数据布局，尤其得当那些需要频仍操纵非连续内存数据的场景。本文将通过一个手动实现的双向链表类 list 来解说双向链表的底层布局和实现原理。
  1. 主要数据布局

在链表的实现中，节点是最基本的元素，每个节点存储数据以及指向前后节点的指针。为了支持双向操纵，链表的每个节点都有两个指针，分别指向前驱节点和后继节点。下面的 list_node 是一个模板类，存储泛型范例 T 的数据。

1. template <class T>
2. struct list_node {
3.     T _data;               // 存储节点数据
4.     list_node* _next;      // 指向下一个节点
5.     list_node* _prev;      // 指向上一个节点
7.     // 构造函数
8.     list_node(const T& x = T())
9.      : _data(x)
10.      , _next(nullptr)
11.      , _prev(nullptr) {}
12. };

复制代码

2. 迭代器的实现

在链表的操纵中，迭代器是至关紧张的，它提供了与链表元素交互的机制。通过迭代器，用户可以像使用数组指针一样访问链表的元素。我们实现了 list_iterator 模板类，用于模仿标准库的迭代器。它不仅支持对节点的访问，还支持前后移动和增减操纵。

1. template <class T, class Ref, class Ptr>
2. struct list_iterator {
3.     typedef list_node<T> Node;
4.     typedef list_iterator<T, Ref, Ptr> self;
5.     Node* _node;  // 当前迭代器指向的节点
7.     list_iterator(Node* node) : _node(node) {}
9.     Ref& operator*() { return _node->_data; }
11.     Ptr* operator->() { return &_node->_data; }
13.     // 前置++，移动到下一个节点
14.     self& operator++() {
15.         _node = _node->_next;
16.         return *this;
17.     }
19.     // 前置--，移动到上一个节点
20.     self& operator--() {
21.         _node = _node->_prev;
22.         return *this;
23.     }
25.     // 后置++，移动到下一个节点，返回之前的状态
26.     self operator++(int) {
27.         self tmp(*this);
28.         _node = _node->_next;
29.         return tmp;
30.     }
32.     // 后置--，移动到上一个节点，返回之前的状态
33.     self operator--(int) {
34.         self tmp(*this);
35.         _node = _node->_prev;
36.         return tmp;
37.     }
39.     bool operator!=(const self& s) { return _node != s._node; }
40.     bool operator==(const self& s) { return _node == s._node; }
41. };

复制代码

迭代器主要提供以下功能：
operator* 和 operator->：实现解引用操纵，返回当前节点的数据。
operator++ 和 operator–：支持迭代器的进步和后退。
operator!= 和 operator==：支持迭代器的比力，判定是否到达链表末尾。
通过实现这些运算符，我们可以像操纵指针一样操纵链表中的元素。
3. 链表的实现

接下来，我们实现链表的主体类 list。这是一个模板类，可以存储任意范例的数据，并提供一些常见的链表操纵。
3.1 基本布局

首先，我们在链表类中定义一个哨兵节点 _head，这个节点没有实际的数据作用，它的存在是为了简化链表的边界处理。通过让哨兵节点的 _next 和 _prev 指向本身，可以避免处理链表为空时的特殊环境。

1. template <class T>
2. class list {
3.     typedef list_node<T> Node;  // 节点类型
4. public:
5.     typedef list_iterator<T, T&, T*> iterator;  // 可修改的迭代器
6.     typedef list_iterator<T, const T&, const T*> const_iterator;  // 常量迭代器
8.     // 构造函数
9.     list() {
10.         empty_init();
11.     }
13.     // 拷贝构造函数
14.     list(const list<T>& lt) {
15.         empty_init();
16.         for (auto& e : lt) {
17.             push_back(e);
18.         }
19.     }
21.     // 赋值操作符
22.     list<T>& operator=(list<T> lt) {
23.         swap(lt);
24.         return *this;
25.     }
27.     // 析构函数
28.     ~list() {
29.         clear();
30.         delete _head;
31.         _head = nullptr;
32.     }
34. private:
35.     Node* _head;   // 哨兵节点
36.     size_t _size;  // 链表的大小
38.     // 初始化空链表
39.     void empty_init() {
40.         _head = new Node();
41.         _head->_next = _head;
42.         _head->_prev = _head;
43.         _size = 0;
44.     }
45. };

复制代码

在 list 的实现中，除了常见的构造、析构函数，我们还实现了拷贝构造函数和赋值操纵符。这确保了链表在被拷贝时可以或许精确复制内容。
3.2 链表的插入与删除

在双向链表中，插入和删除操纵是其核心功能。我们通过 insert 函数将新元素插入到链表的指定位置。它首先获取要插入位置前后的节点，然后重新设置这些节点的指针，使新节点精确链接到链表中。

1. iterator insert(iterator pos, const T& val) {
2.     Node* cur = pos._node;
3.     Node* newnode = new Node(val);
4.     Node* prev = cur->_prev;
6.     prev->_next = newnode;
7.     newnode->_prev = prev;
9.     newnode->_next = cur;
10.     cur->_prev = newnode;
11.     ++_size;
13.     return iterator(newnode);
14. }

复制代码

对于删除操纵，我们通过 erase 函数实现。erase 函数移除指定位置的节点，并将该节点前后的节点重新连接。

1. iterator erase(iterator pos) {
2.     assert(pos != end());
4.     Node* del = pos._node;
5.     Node* prev = del->_prev;
6.     Node* next = del->_next;
8.     prev->_next = next;
9.     next->_prev = prev;
10.     delete del;
11.     --_size;
13.     return iterator(next);
14. }

复制代码

3.3 其他成员函数

我们还实现了链表的其他常用操纵，如 push_back 和 push_front，用于在链表尾部和头部插入元素。pop_back 和 pop_front 则用于删除尾部和头部的元素。

1. void push_back(const T& x) {
2.     insert(end(), x);
3. }
5. void push_front(const T& x) {
6.     insert(begin(), x);
7. }
9. void pop_back() {
10.     erase(--end());
11. }
13. void pop_front() {
14.     erase(begin());
15. }

复制代码

这些操纵都依赖于 insert 和 erase 函数，实现起来相对简单。
4. 迭代器操纵与遍历链表

我们为链表提供了 begin() 和 end() 函数，用于获取链表的起始和竣事迭代器。通过这些迭代器，用户可以遍历整个链表，访问每个元素。

1. iterator begin() {
2.     return iterator(_head->_next);
3. }
5. iterator end() {
6.     return iterator(_head);
7. }

复制代码

可以通过以下代码遍历链表的元素：

1. list<int> lt;
2. lt.push_back(1);
3. lt.push_back(2);
4. lt.push_back(3);
6. for (auto it = lt.begin(); it != lt.end(); ++it) {
7.     cout << *it << " ";
8. }
9. // 输出: 1 2 3

复制代码

5. 拷贝构造与赋值运算符

我们实现了拷贝构造函数和赋值运算符，通过它们可以确保链表被精确复制。赋值运算符通过 swap 函数互换两个链表的内部布局，从而实现高效的赋值。

1. list<T>& operator=(list<T> lt) {
2.     swap(lt);
3.     return *this;
4. }
6. void swap(list<T>& tmp) {
7.     std::swap(_head, tmp._head);
8.     std::swap(_size, tmp._size);
9. }

复制代码

6. 总结

本文从底层实现的角度详细解说了如何手动实现一个双向链表容器 list。我们计划了双向链表的数据布局，通过节点、迭代器、基本的插入、删除操纵，终极实现了一个功能完备的链表容器。以下是本文的主要内容回顾：
1.双向链表节点计划：每个节点存储数据元素，同时通过两个指针 _prev 和 _next 链接到前一个和后一个节点。这种计划使得我们可以在链表中进行双向遍历，并支持 O(1) 时间复杂度的插入和删除操纵。
2.迭代器的实现：为了让链表可以像标准库中的容器一样被遍历，我们实现了 list_iterator。通过运算符重载，用户可以使用迭代器访问链表元素，进行正向和反向遍历。迭代器操纵封装了链表内部的指针操纵，使链表的使用更加简洁直观。
3.链表类的实现：

• 插入和删除：我们实现了常见的 insert 和 erase 操纵，它们负责在指定位置插入新元素或移除已有元素。双向链表的上风在于，我们可以在常数时间内完成这些操纵，而无需像数组那样需要移动后续元素。
  
• push_back 和 push_front：为了方便用户插入元素，我们提供了头部和尾部的插入操纵，分别对应在链表的首位插入新元素。
  
• pop_back 和 pop_front：链表的首尾删除操纵也被封装在这两个函数中，方便用户快速删除首尾元素。
  

4.迭代器操纵与遍历：通过 begin() 和 end() 函数，我们可以使用 C++ 标准的范围遍历方式遍历链表的所有元素。这使得链表容器的使用方式与 C++ 标准库中的其他容器一致，低沉了使用门槛。
5.拷贝构造与赋值运算符：为了确保链表可以被精确拷贝，我们实现了拷贝构造函数和赋值操纵符。在赋值操纵中，我们通过 swap 函数实现高效的资源互换，避免了复杂的手动赋值操纵。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。