在 C++ 中实现双向链表的迭代器

当前位置：主页 > 学无止境 > 编程语言 > C++ >

Python PHP Java Go TypeScript C++ Vba Node.js C语言 MATLAB

在 C++ 中实现双向链表的迭代器

作者：迹忆客最近更新：2023/08/29 浏览次数：

由于双向链接数据结构由一组顺序链接的节点组成，其起始节点和结束节点的上一个和下一个链接都指向一个终止符（通常是哨兵节点或空），以方便链表的遍历。本教程将教您如何在 C++ 中实现双向链表的迭代器。

一般来说，迭代器类被实现为指向链表节点的指针作为新元素，因为它属于作为其子类的链表类。四个主要操作利用迭代器类，包括：取消引用赋值、比较和递增操作。

在 C++ 中使用类实现双向链表的迭代器

使用类来编写双向链表是一种很好的实践，因为它使您能够优化迭代器和双向链表。在向双向链表添加新元素方面，迭代器类能够构建T型对象。

此外，C++ 编译器允许使用简单列表（作为数据结构）初始化进行迭代器初始化，而无需任何手动帮助来指定它。此外，您可以在创建 Node 对象时通过显式初始化 value 成员来调用 T 的默认构造函数。

对于此方法，迭代器类接受/采用两个参数，包括作为迭代器对象的 iterator 和作为要插入的项的 constT&。它将迭代器作为结果返回到新插入的节点。

结果，创建了一个新的双向链表节点，其中包含 constT& 项作为其元素，因为迭代器类生成它，并且可以在迭代器进行任何插入之前成功插入到链表中。

#include <iostream>

// optional: using namespace std;

// template with the `T` typename to manipulate and initialize the variables
template <typename T>

// the `linkedlist_node` class has access to the linked list
class linkedlist_node {

  public:
    T list_data;
    linkedlist_node<T> *node_next;

    linkedlist_node() : node_next(nullptr) {}
    linkedlist_node(const T& con_listitem, linkedlist_node<T> *activelist_ptr = nullptr) :
      list_data(con_listitem), node_next(activelist_ptr) {}
};

// the `linkedlist_main` is the primary/main linked list class
template <typename T>
class linkedlist_main {

  public:

    linkedlist_main() {

      // creating dummy head and tail nodes
      node_head = node_tail = new linkedlist_node<T>();
    }

    linkedlist_main(const linkedlist_main<T>& other) = delete;
    linkedlist_main(linkedlist_main<T>&& other) = delete;

    ~linkedlist_main() {
      while (node_head -> node_next != nullptr) {

          // build the `node_head` head node from the `listdata_temp`
          linkedlist_node<T>* listdata_temp = node_head;

        node_head = node_head -> node_next;
        delete listdata_temp; // delete the temp afterward
      }
      // empty the `node_head` by removing its content
      delete node_head;
    }

    // delete the `linkedlist_main` contents after a successful insertion or creation
    linkedlist_main<T>& operator=(const linkedlist_main<T>& other) = delete;
    linkedlist_main<T>& operator=(linkedlist_main<T>&& other) = delete;

    // the `mainCon_iterator` is an inner class inherited from the `linkedlist_main` class
    // it creates an iterator implemented on a doubly-linked list
    class mainCon_iterator {

        friend class linkedlist_main; // inherited from

      private: // private elements (restricted access)

      linkedlist_node<T> *listnode_ptr; // it's a private node that can only be accessed by authorized personnel

        // only an authorized person can create instances of iterators because the constructor is private
        mainCon_iterator(linkedlist_node<T> *newlist_ptrnode) : listnode_ptr(newlist_ptrnode) {}

      public: // public elements (general access)

      mainCon_iterator() : listnode_ptr(nullptr) {}

        // Overload: comparison operator !=

        // create an object from the `mainCon_iterator` and perform the comparison operator
        bool operator!=(const mainCon_iterator& obj_itr) const {
          return listnode_ptr != obj_itr.listnode_ptr; // comparison
        }

        // Overload: dereference operator *

        // pass the node via `operator` object `const`
        T& operator*() const {
          // access to the `list_node` node
          return listnode_ptr -> node_next -> list_data;
        }

        // Overload: post-increment operator ++
        mainCon_iterator operator++(int) {
            mainCon_iterator iterator_temp = *this;
            listnode_ptr = listnode_ptr->node_next;
          return iterator_temp;
        }
    }; // end of the `mainCon_iterator` inner class

    mainCon_iterator begin() const {
      return mainCon_iterator(node_head);
    }

    mainCon_iterator end() const {
      return mainCon_iterator(node_tail);
    }

    mainCon_iterator insert(mainCon_iterator iterator_pos,const T& itrPos_value) {
        linkedlist_node<T>* new_listnode = new linkedlist_node<T>(itrPos_value, iterator_pos.listnode_ptr->node_next);
      if (iterator_pos.listnode_ptr == node_tail) node_tail = new_listnode;
      iterator_pos.listnode_ptr->node_next = new_listnode;

      return iterator_pos;
    }

    mainCon_iterator erase(mainCon_iterator iterator_pos) {
        linkedlist_node<T> *itrposition_delete = iterator_pos.listnode_ptr->node_next;
        iterator_pos.listnode_ptr->node_next = iterator_pos.listnode_ptr->node_next->node_next;
      if (itrposition_delete == node_tail) node_tail = iterator_pos.listnode_ptr;
      delete itrposition_delete;

      return iterator_pos;
    }

  private:
    linkedlist_node<T>* node_head;
    linkedlist_node<T>* node_tail;
};

int main(int argc,const char* argv[])
{
    std::cout<< "Iterator for the doubly-linked list is successfully implemented!"<< std::endl;
    linkedlist_main<int> list_var;

    list_var.insert(list_var.end(),4);
    list_var.insert(list_var.end(),7);
    list_var.insert(list_var.end(),9);

    auto iterator = list_var.begin();
    iterator = list_var.insert(iterator, 3);
    iterator++;
    list_var.insert(iterator++,6);
    iterator++;
    list_var.insert(iterator,2);

    iterator = list_var.begin();
    iterator++;
    list_var.erase(iterator);

    for(auto iterator = list_var.begin();iterator != list_var.end();iterator++)
        std::cout << *iterator << std::endl;

    return 0;
}

输出:

Iterator for the doubly-linked list is successfully implemented!
3
4
7
2
9

由于迭代器可以操作链表类中的数据，因此它指向链表中您想要删除、更新或创建的节点。迭代器类中的插入和删除可以解决这个问题，但是这个解决方案会产生另一个问题。

问题是处理 begin() 方法，该方法假定返回一个指向链表起始点的迭代器。为了解决这个问题，您将在列表的实际起始节点之前使用一个虚拟头节点，例如，

iterator begin() const {return iterator(head);} // 处理 begin()

迭代器支持预自增 ++itr 和后自增 itr++ 运算符，当在 C++ 代码中的同一语句中与其他运算符一起使用时，它们的区别会变得更加清晰。

C++中使用节点实现双向链表的迭代器

它涉及将一个相当标准的双向链表的迭代器实现为 C++ 模板。它在示例代码中使用条件编译指令，并且不包含任何严重的或其他缺陷，使您能够在要修改其成员时添加功能。

C++ 支持增量运算符（前增量 ++itr 和后增量 itr++），并且需要一种特殊的约定来通过在迭代器类中重载它们来定义或阐明它们的独特性质。分别使用iterator&operator++()或iteratoroperator++(int)进行前后自增，并且可以使用return *this; 在复合 C++ 表达式中执行增量的函数。

#include <ctime>
#include <iostream>
#include <random>
template <typename T>
class linkedlist_main
{
private:
    struct list_node
    {
         list_node *right_node;
         list_node *left_node;
         T list_value;
         list_node(list_node* listnode_left,const T& listnode_value, list_node* listnode_right) : left_node(listnode_left), list_value(listnode_value), right_node(listnode_right) {}
         list_node(list_node* listnode_left,list_node* listnode_right) : left_node(listnode_left) , right_node(listnode_right) {}
    };

public:
    class iterator_mainClass;
    class con_itr_main : public std::iterator<std::bidirectional_iterator_tag,list_node,int,list_node*,T>
    {
        friend class linkedlist_main;
        friend class iterator_mainClass;
    private:
        typename con_itr_main::pointer pointer_main;
        con_itr_main(typename con_itr_main::pointer pointer_first) : pointer_main(pointer_first) {}
    public:
        con_itr_main& operator++()
        {
            pointer_main = pointer_main -> right_node;
            return *this;
        }
        con_itr_main& operator--()
        {
            pointer_main = pointer_main -> left_node;
            return *this;
        }
        con_itr_main operator++(int)
        {
            typename con_itr_main::pointer type_temp = pointer_main;
            pointer_main = pointer_main -> right_node;
            return type_temp;
        }
        con_itr_main operator--(int)
        {
            typename con_itr_main::pointer type_temp = pointer_main;
            pointer_main = pointer_main -> left_node;
            return type_temp;
        }
        typename con_itr_main::reference operator*() { return pointer_main->list_value; }
        friend bool operator==(const con_itr_main& list_first, const con_itr_main& list_second){ return list_first.pointer_main == list_second.pointer_main; }
        friend bool operator!=(const con_itr_main& list_first, const con_itr_main& list_second) { return !(list_first == list_second); }
        friend bool operator==(const con_itr_main& pri_iterator, const iterator_mainClass& itr_ele);
        friend bool operator!=(const con_itr_main& pri_iterator, const iterator_mainClass& itr_ele);
    };

    class iterator_mainClass : public std::iterator<std::bidirectional_iterator_tag,const list_node,int,const list_node *,const T>
    {
        friend class linkedlist_main;
    private:
        typename iterator_mainClass::pointer pointer_main;
        iterator_mainClass(typename iterator_mainClass::pointer pointer_first) : pointer_main(pointer_first) {}
    public:
        iterator_mainClass(const con_itr_main& pri_iter) : pointer_main(pri_iter.pointer_main) {}
        iterator_mainClass& operator++()
        {
            pointer_main = pointer_main -> right_node;
            return *this;
        }
        iterator_mainClass& operator--()
        {
            pointer_main = pointer_main -> left_node;
            return *this;
        }
        iterator_mainClass operator++(int)
        {
            typename iterator_mainClass::pointer death = pointer_main;
            pointer_main = pointer_main -> right_node;
            return death;
        }
        iterator_mainClass operator--(int)
        {
            typename iterator_mainClass::pointer ordinary = pointer_main;
            pointer_main = pointer_main -> left_node;
            return ordinary;
        }
        typename iterator_mainClass::reference operator*() { return pointer_main->list_value; }
        friend bool operator==(const iterator_mainClass& temp_iterator, const iterator_mainClass& temp_iteratorSec) { return temp_iterator.pointer_main == temp_iteratorSec.pointer_main; }
        friend bool operator!=(const iterator_mainClass& temp_iterator, const iterator_mainClass& temp_iteratorSec) { return !(temp_iterator == temp_iteratorSec); }
        friend bool operator==(const con_itr_main& primary_itr, const iterator_mainClass& primary_itrrator_alt);
        friend bool operator!=(const con_itr_main& primary_itr, const iterator_mainClass& primary_itrrator_alt);
    };

    friend bool operator==(const con_itr_main& primary_itr, const iterator_mainClass& primary_itrrator_alt) { return primary_itr.pointer_main == primary_itrrator_alt.pointer_main; }
    friend bool operator!=(const con_itr_main& primary_itr, const iterator_mainClass& primary_itrrator_alt) { return !(primary_itr == primary_itrrator_alt); }

    linkedlist_main() = default;

    template<typename... Types>
    linkedlist_main(const T &value,Types&&... values) :  linkedlist_main(values...)
    {
        add_valuetotop(value);
    }

    linkedlist_main(const linkedlist_main &QEL) { *this = QEL; }
    linkedlist_main(iterator_mainClass position_start,const iterator_mainClass position_end)
    {
        for(;position_start != position_end;position_start++)
            this->add_valuetoend(*position_start);
    }

    linkedlist_main(T &&value) { push_front(value); }
    ~linkedlist_main()
    {
        this->clear();
        delete valueto_end;
    }

    void delete_lastnode()//deletes the last node
    {
        list_node* delete_lasttemp = valueto_end;
        valueto_end = valueto_end->left_node;
        valueto_end->right_node = nullptr;
        delete delete_lasttemp;
        linkedlist_size--;
    }

    void delete_firstnode()//deletes the first node
    {
        list_node* delete_firsttemp = listnode_head;
        listnode_head = listnode_head -> right_node;
        listnode_head -> left_node = nullptr;
        delete delete_firsttemp;
        linkedlist_size--;
    }

    void add_valuetoend(const T &linkedlist_addvalue)//adds the value to the end of the list
    {
        valueto_end = new list_node(valueto_end,nullptr);
        valueto_end -> left_node -> list_value = linkedlist_addvalue;
        if(linkedlist_size > 0) valueto_end -> left_node -> left_node -> right_node = valueto_end -> left_node;
        valueto_end -> left_node -> right_node = valueto_end;
        linkedlist_size++;
    }

    void add_valuetotop(const T &linkedlist_addvalue_top)//adds the value to the top of the list
    {
        listnode_head = new list_node(nullptr,linkedlist_addvalue_top,listnode_head);
        listnode_head -> right_node -> left_node = listnode_head;
        linkedlist_size++;
    }

    void clear()
    {
        list_node *clear_buffer;

        // a loop to clear all the linked lists temp obj
        for(int temp = 0 ; temp < linkedlist_size ; temp++)
        {
            clear_buffer = listnode_head;
            listnode_head = listnode_head -> right_node;
            delete clear_buffer;
        }
        listnode_head = valueto_end;
        linkedlist_size = 0;
    }

    void erase(iterator_mainClass node_current_pos)//deletes the node that the iterator points to (the iterator itself becomes hung)
    {
        if(node_current_pos.pointer_main != listnode_head && node_current_pos.pointer_main != valueto_end->left_node)
        {
            node_current_pos.pointer_main->left_node->right_node = node_current_pos.pointer_main->right_node;
            node_current_pos.pointer_main->right_node->left_node = node_current_pos.pointer_main->left_node;
            delete node_current_pos.pointer_main;
            linkedlist_size--;
        }
        else if(node_current_pos.pointer_main == listnode_head)
        {
            this->delete_firstnode();
        }
        else
        {
            this->delete_lastnode();
        }
    }

    void erase(iterator_mainClass node_startposition,const iterator_mainClass node_endposition)//deletes everything from begin_pos to end_pos (end_pos itself is not deleted)
    {
        while(node_startposition != node_endposition)
        {
            this->erase(node_startposition++);
        }
    }

    // the start of the primary iterator
    con_itr_main begin() { return con_itr_main(listnode_head); }
    iterator_mainClass con_itr_begin() const { return iterator_mainClass(listnode_head); }

    // the end-point of the primary iterator
    con_itr_main end() { return con_itr_main(valueto_end); }
    iterator_mainClass con_itr_end() const { return iterator_mainClass(valueto_end); }

    T& operator[](unsigned const int &oprIndex_con) const
    {
        if(oprIndex_con > (linkedlist_size - 1) / 2)
        {

            return scroll_node (-(linkedlist_size -1 -oprIndex_con), valueto_end -> left_node) -> list_value;
        }
        else
        {
            return scroll_node (oprIndex_con ,listnode_head) -> list_value;
        }
    }

    void operator=(const linkedlist_main &oprQel_var)
    {
        this -> clear();
        auto iter = oprQel_var.con_itr_begin();
        for(;iter != oprQel_var.con_itr_end(); iter++)
        {
            this -> add_valuetoend(*iter);
        }
    }

    size_t size() const { return linkedlist_size; }
    private:
    size_t linkedlist_size = 0;
    list_node *valueto_end = new list_node(nullptr,nullptr);
    list_node *listnode_head = valueto_end;

    list_node* scroll_node(int numIndex_pri ,list_node* node_ptr) const
    {
        if(numIndex_pri > 0)
            for(int i = 0; i < numIndex_pri; i++)
            {
                node_ptr = node_ptr -> right_node;
            }
        else
        {
            numIndex_pri = abs (numIndex_pri);
            for(int i = 0; i < numIndex_pri; i++)
            {
                node_ptr = node_ptr -> left_node;
            }
        }
        return node_ptr;
    }
};

template<typename S>
linkedlist_main<S> template_sort(const linkedlist_main<S> &new_linkedlist)
{
    srand(time(NULL));

    // in case the linked list exists and isn't null
    if(new_linkedlist.size() <= 1)
    {
        return new_linkedlist;
    }

    linkedlist_main<S> size_minimum;
    linkedlist_main<S> size_maximum;
    linkedlist_main<S> list_elements;

    S list_element = new_linkedlist[rand()%new_linkedlist.size()];
    auto opr_iterator = new_linkedlist.con_itr_begin();

    for(;opr_iterator != new_linkedlist.con_itr_end();opr_iterator++)
    {
        if(*opr_iterator > list_element)
        {
            size_maximum.add_valuetoend(*opr_iterator);
        }
        else if(*opr_iterator < list_element)
        {
            size_minimum.add_valuetoend(*opr_iterator);
        }
        else
        {
            list_elements.add_valuetoend(list_element);
        }
    }

    size_minimum = template_sort(size_minimum);
    opr_iterator = list_elements.con_itr_begin();

    for(;opr_iterator != list_elements.con_itr_end();opr_iterator++)
    {
        size_minimum.add_valuetoend(*opr_iterator);
    }

    size_maximum = template_sort(size_maximum);
    opr_iterator = size_maximum.con_itr_begin();

    for(;opr_iterator != size_maximum.con_itr_end();opr_iterator++)
    {
        size_minimum.add_valuetoend(*opr_iterator);
    }
    return size_minimum;
}

template<typename S>
linkedlist_main<S> tempSort_selection(linkedlist_main<S> selection_linkedlist)
{
    linkedlist_main<int> linkedlist_second;

    while(selection_linkedlist.size()>0)
    {
        auto int_maximum = selection_linkedlist.begin();
        auto iterator_main = int_maximum;
        for(;iterator_main != selection_linkedlist.end();iterator_main++)
            if(*iterator_main > *int_maximum)
                int_maximum = iterator_main;
        linkedlist_second.add_valuetotop(*int_maximum);
        selection_linkedlist.erase(int_maximum);
    }
    return linkedlist_second;
}

int main()
{
    linkedlist_main<int> linkedlist_orig(0,1,9,26,8,3,7,4,6,5,11,47,2);
    linkedlist_main<int> linkedlist_rev = template_sort(linkedlist_orig);

    std::cout << "The original list | Size: " << linkedlist_orig.size() << std::endl;
    std::cout << "Revised version of the original list: " << linkedlist_rev.size() << std::endl;

    for(int i = 0; i < linkedlist_rev.size() ; i++)
        std::cout << linkedlist_rev[i] << std::endl;

    linkedlist_main<int> linkedlist_sec(tempSort_selection(linkedlist_main<int>(5,67,4,7,3,8,2,9,1,22,54,6)));

    std::cout << "The sorted list: " << linkedlist_sec.size() << std::endl;

    for(int info = 0; info < linkedlist_sec.size() ; info++)
        std::cout << linkedlist_rev[info] << std::endl;

    std::cout << clock()/static_cast<double>(CLOCKS_PER_SEC) << std::endl;

    return 0;
}

输出:

The original list | Size: 13
Revised version of the original list: 13
0
1
2
3
4
5
6
7
8
9
11
26
47
The sorted list: 12
0
1
2
3
4
5
6
7
8
9
11
26
0

总之，双向链表需要额外的空间和内存来存储指针并提高搜索效率。当内存限制不是问题时，实现迭代器也是非常高效的。

上一篇：用 C++ 编写系统调用

下一篇：没有了

转载请发邮件至 1244347461@qq.com 进行申请，经作者同意之后，转载请以链接形式注明出处

本文地址：

迹忆客专注技术分享