ToB企服应用市场:ToB评测及商务社交产业平台

标题: 从零开始实现 C++ 双向链表:深入明白链表底层原理 [打印本页]

作者: 汕尾海湾    时间: 2024-11-10 14:00
标题: 从零开始实现 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;      // 指向上一个节点
  6.     // 构造函数
  7.     list_node(const T& x = T())
  8.      : _data(x)
  9.      , _next(nullptr)
  10.      , _prev(nullptr) {}
  11. };
复制代码
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;  // 当前迭代器指向的节点
  6.     list_iterator(Node* node) : _node(node) {}
  7.     Ref& operator*() { return _node->_data; }
  8.     Ptr* operator->() { return &_node->_data; }
  9.     // 前置++,移动到下一个节点
  10.     self& operator++() {
  11.         _node = _node->_next;
  12.         return *this;
  13.     }
  14.     // 前置--,移动到上一个节点
  15.     self& operator--() {
  16.         _node = _node->_prev;
  17.         return *this;
  18.     }
  19.     // 后置++,移动到下一个节点,返回之前的状态
  20.     self operator++(int) {
  21.         self tmp(*this);
  22.         _node = _node->_next;
  23.         return tmp;
  24.     }
  25.     // 后置--,移动到上一个节点,返回之前的状态
  26.     self operator--(int) {
  27.         self tmp(*this);
  28.         _node = _node->_prev;
  29.         return tmp;
  30.     }
  31.     bool operator!=(const self& s) { return _node != s._node; }
  32.     bool operator==(const self& s) { return _node == s._node; }
  33. };
复制代码
迭代器主要提供以下功能:
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;  // 常量迭代器
  7.     // 构造函数
  8.     list() {
  9.         empty_init();
  10.     }
  11.     // 拷贝构造函数
  12.     list(const list<T>& lt) {
  13.         empty_init();
  14.         for (auto& e : lt) {
  15.             push_back(e);
  16.         }
  17.     }
  18.     // 赋值操作符
  19.     list<T>& operator=(list<T> lt) {
  20.         swap(lt);
  21.         return *this;
  22.     }
  23.     // 析构函数
  24.     ~list() {
  25.         clear();
  26.         delete _head;
  27.         _head = nullptr;
  28.     }
  29. private:
  30.     Node* _head;   // 哨兵节点
  31.     size_t _size;  // 链表的大小
  32.     // 初始化空链表
  33.     void empty_init() {
  34.         _head = new Node();
  35.         _head->_next = _head;
  36.         _head->_prev = _head;
  37.         _size = 0;
  38.     }
  39. };
复制代码
在 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;
  5.     prev->_next = newnode;
  6.     newnode->_prev = prev;
  7.     newnode->_next = cur;
  8.     cur->_prev = newnode;
  9.     ++_size;
  10.     return iterator(newnode);
  11. }
复制代码
对于删除操纵,我们通过 erase 函数实现。erase 函数移除指定位置的节点,并将该节点前后的节点重新连接。
  1. iterator erase(iterator pos) {
  2.     assert(pos != end());
  3.     Node* del = pos._node;
  4.     Node* prev = del->_prev;
  5.     Node* next = del->_next;
  6.     prev->_next = next;
  7.     next->_prev = prev;
  8.     delete del;
  9.     --_size;
  10.     return iterator(next);
  11. }
复制代码
3.3 其他成员函数

我们还实现了链表的其他常用操纵,如 push_back 和 push_front,用于在链表尾部和头部插入元素。pop_back 和 pop_front 则用于删除尾部和头部的元素。
  1. void push_back(const T& x) {
  2.     insert(end(), x);
  3. }
  4. void push_front(const T& x) {
  5.     insert(begin(), x);
  6. }
  7. void pop_back() {
  8.     erase(--end());
  9. }
  10. void pop_front() {
  11.     erase(begin());
  12. }
复制代码
这些操纵都依赖于 insert 和 erase 函数,实现起来相对简单。
4. 迭代器操纵与遍历链表

我们为链表提供了 begin() 和 end() 函数,用于获取链表的起始和竣事迭代器。通过这些迭代器,用户可以遍历整个链表,访问每个元素。
  1. iterator begin() {
  2.     return iterator(_head->_next);
  3. }
  4. iterator end() {
  5.     return iterator(_head);
  6. }
复制代码
可以通过以下代码遍历链表的元素:
  1. list<int> lt;
  2. lt.push_back(1);
  3. lt.push_back(2);
  4. lt.push_back(3);
  5. for (auto it = lt.begin(); it != lt.end(); ++it) {
  6.     cout << *it << " ";
  7. }
  8. // 输出: 1 2 3
复制代码
5. 拷贝构造与赋值运算符

我们实现了拷贝构造函数和赋值运算符,通过它们可以确保链表被精确复制。赋值运算符通过 swap 函数互换两个链表的内部布局,从而实现高效的赋值。
  1. list<T>& operator=(list<T> lt) {
  2.     swap(lt);
  3.     return *this;
  4. }
  5. void swap(list<T>& tmp) {
  6.     std::swap(_head, tmp._head);
  7.     std::swap(_size, tmp._size);
  8. }
复制代码
6. 总结

本文从底层实现的角度详细解说了如何手动实现一个双向链表容器 list。我们计划了双向链表的数据布局,通过节点、迭代器、基本的插入、删除操纵,终极实现了一个功能完备的链表容器。以下是本文的主要内容回顾:
1.双向链表节点计划:每个节点存储数据元素,同时通过两个指针 _prev 和 _next 链接到前一个和后一个节点。这种计划使得我们可以在链表中进行双向遍历,并支持 O(1) 时间复杂度的插入和删除操纵。
2.迭代器的实现:为了让链表可以像标准库中的容器一样被遍历,我们实现了 list_iterator。通过运算符重载,用户可以使用迭代器访问链表元素,进行正向和反向遍历。迭代器操纵封装了链表内部的指针操纵,使链表的使用更加简洁直观。
3.链表类的实现
4.迭代器操纵与遍历:通过 begin() 和 end() 函数,我们可以使用 C++ 标准的范围遍历方式遍历链表的所有元素。这使得链表容器的使用方式与 C++ 标准库中的其他容器一致,低沉了使用门槛。
5.拷贝构造与赋值运算符:为了确保链表可以被精确拷贝,我们实现了拷贝构造函数和赋值操纵符。在赋值操纵中,我们通过 swap 函数实现高效的资源互换,避免了复杂的手动赋值操纵。

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




欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) Powered by Discuz! X3.4