Implement Iterator for a Doubly Linked List in C++
Syed Hassan Sabeeh Kazmi
Feb 03, 2023
Oct 06, 2022
- Use Classes to Implement Iterator for a Doubly Linked List in C++
- Use Nodes to Implement Iterator for a Doubly Linked List in C++
As the doubly linked data structure consists of a set of sequentially linked nodes, its beginning and ending node’s previous and next links point to a terminator (typically a sentinel node or null) to facilitate traversal of the linked list. This tutorial will teach you how to implement an iterator for a doubly linked list in C++.
In general, the iterator class is implemented as a pointer to a linked list node as a new element because it belongs to the linked list class as its sub-class. Four primary operations utilize the iterator class, including; dereference assignment, comparison, and increment operation.
Use Classes to Implement Iterator for a Doubly Linked List in C++
The use of classes for writing doubly linked lists is an excellent practice because it enables you to optimize the iterator and the doubly linked list. In terms of adding new elements to the doubly linked list, the iterator classes are capable of building the T-type objects.
Furthermore, the C++ compiler allows iterator initialization using simple list (as data structure) initialization without any manual help to specify it. Moreover, you can call the default constructor of T when you create a Node object by explicitly initializing the value member.
Regarding this method, the iterator class accepts/takes two arguments, including the iterator<T> as an iterator object and the constT& as an item to be inserted. It returns an iterator as a result to the newly inserted node.
As a result, a new doubly-linked list node is created, which contains the constT& item as its element because the iterator class produces it and can be successfully inserted into the linked list before any insertion by the iterator.
#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;
}
Output:
Iterator for the doubly-linked list is successfully implemented!
3
4
7
2
9
As an iterator can manipulate the data in the linked list class, it points to a node in a linked list that you would like to erase, update, or create. The insert and erase from the iterator class can solve this problem, but this solution creates another problem.
The problem is to handle the begin() method, which supposes to return an iterator pointing to the starting point of a linked list. To handle this problem, you will use a dummy head node before the actual starting node of the list, something like,
iterator begin() const {return iterator(head);} // to handle begin()
The pre-increment ++itr and the post-increment itr++ operators are supported by the iterator, and their difference becomes clearer when utilized alongside the other operators in the same statement in C++ code.
Use Nodes to Implement Iterator for a Doubly Linked List in C++
It involves implementing an iterator to a fairly standard doubly-linked list as a C++ template. It uses conditional compilation directives in the sample code and doesn’t contain any serious or other flaws that enable you to add features if you want to modify its members.
C++ supported the increment operators (pre-increment ++itr and post-increment itr++) and required a peculiar convention to define or clarify their unique nature by overloading them in the iterator class. Use the iterator& operator++() or the iterator operator++(int) respectively for pre- or post-increment, and you can use the return *this; function to perform increment in a compound C++ expression.
#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;
}
Output:
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
In conclusion, the doubly linked list requires extra space and memory to store pointers and make searching efficient. It is also highly efficient to implement the iterators when the limitation of its memory is not a problem.
Author: Syed Hassan Sabeeh Kazmi
Hassan is a Software Engineer with a well-developed set of programming skills. He uses his knowledge and writing capabilities to produce interesting-to-read technical articles.
GitHub