How to Implement Iterator for a Doubly Linked List in C++

1. Implementing Iterator in a Doubly Linked List in C++ Using Class Method
2. Implementing Iterator in a Doubly Linked List in C++ Using Nodes Method
3. Conclusion

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.

The C++ compiler allows iterator initialization using simple list (as a 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.

In this article, we will explore two approaches—using class and node methods—to implement iterators for a doubly linked list in C++, examining how each method contributes to code organization and efficiency.

Implementing Iterator in a Doubly Linked List in C++ Using Class Method

Using class methods in implementing an iterator for a doubly linked list brings clarity and encapsulation to the code. By employing a separate iterator class, the iteration logic is encapsulated, promoting a clean and modular design.

This approach enhances code readability, making it more intuitive for developers to understand and maintain. Additionally, class methods facilitate a consistent and standardized interface for iteration, contributing to a more organized and user-friendly code structure.

While the node method directly leverages the inherent structure of nodes, the class method offers a higher level of abstraction, particularly beneficial in scenarios where code organization and readability are paramount.

Code Example:

#include <iostream>

template <typename T>
class Node {
 public:
  T data;
  Node* next;
  Node* prev;

  Node(const T& value) : data(value), next(nullptr), prev(nullptr) {}
};

template <typename T>
class DoublyLinkedList {
 private:
  Node<T>* head;
  Node<T>* tail;

 public:
  DoublyLinkedList() : head(nullptr), tail(nullptr) {}

  // Method to add elements to the doubly linked list
  void insertBack(const T& value) {
    Node<T>* newNode = new Node<T>(value);
    if (!head) {
      head = tail = newNode;
    } else {
      tail->next = newNode;
      newNode->prev = tail;
      tail = newNode;
    }
  }

  // Iterator class definition
  class Iterator {
   private:
    Node<T>* current;

   public:
    Iterator(Node<T>* node) : current(node) {}

    T& operator*() { return current->data; }

    Iterator& operator++() {
      if (current) {
        current = current->next;
      }
      return *this;
    }

    Iterator& operator--() {
      if (current) {
        current = current->prev;
      }
      return *this;
    }

    bool operator!=(const Iterator& other) const {
      return current != other.current;
    }
  };

  // Class methods to obtain iterators
  Iterator begin() { return Iterator(head); }

  Iterator end() { return Iterator(nullptr); }
};

int main() {
  // Create a doubly linked list and insert elements
  DoublyLinkedList<int> myList;
  myList.insertBack(1);
  myList.insertBack(2);
  myList.insertBack(3);

  // Iterate through the list using the iterator
  std::cout << "Doubly Linked List Elements: ";
  for (DoublyLinkedList<int>::Iterator it = myList.begin(); it != myList.end();
       ++it) {
    std::cout << *it << " ";
  }

  return 0;
}

Commencing with the Node class, it serves as the fundamental building block for our doubly linked list. Within this class, each node encapsulates data along with pointers pointing to the next node (next) and the preceding node (prev).

This establishes the foundational structure for the doubly linked list, allowing for the connection between individual elements.

Moving forward to the DoublyLinkedList class, it acts as a container for the doubly linked list, encapsulating essential methods for managing the list. Specifically, the insertBack method facilitates the addition of elements to the list at its rear. Additionally, an internal class, Iterator, is introduced within the DoublyLinkedList class.

This iterator class provides a well-defined interface for traversing the elements of the list.

Within the Iterator class, nested within DoublyLinkedList, various operators are overloaded to facilitate smooth iteration. The operator* is overloaded to dereference the current node, allowing access to its data.

Furthermore, the operator++ and operator-- are employed to move to the next and previous nodes, respectively. Importantly, the operator!= ensures the loop termination condition, enhancing the robustness of the iterator.

In the main function, the code instantiation begins with the creation of a DoublyLinkedList instance. Subsequent to this, elements are inserted into the list using the insertBack method.

The iterator is then utilized to traverse the list sequentially, printing the elements during each iteration.

This comprehensive approach, combining the node structure and an internal iterator class, contributes to the clarity and maintainability of the code. The output, exemplified in the provided example, demonstrates the successful traversal of the doubly linked list using the implemented iterator.

Output:

The output confirms that the iterator correctly traverses the doubly linked list, showcasing the successful implementation of the concept. Implementing an iterator using class methods for a doubly linked list in C++ enhances code readability and encapsulation.

The iterator simplifies the process of iterating through the list, making the code more expressive and maintainable. The provided code example demonstrates a straightforward yet powerful way to leverage C++ features for effective doubly linked list iteration.

Implementing Iterator in a Doubly Linked List in C++ Using Nodes Method

Using the node method in implementing an iterator for a doubly linked list promotes a lightweight and straightforward approach. By directly relying on the inherent structure of nodes, it eliminates the need for a separate iterator class, resulting in a more concise and resource-efficient implementation.

This method can be advantageous in scenarios where code simplicity is prioritized, as it simplifies the iteration process without introducing additional layers of abstraction. However, it may sacrifice some encapsulation and may be less suitable for complex data structures where a dedicated iterator class can offer better organization and maintainability.

Code Example:

#include <iostream>

template <typename T>
class Node {
 public:
  T data;
  Node* next;
  Node* prev;

  Node(const T& value) : data(value), next(nullptr), prev(nullptr) {}
};

template <typename T>
class DoublyLinkedList {
 private:
  Node<T>* head;
  Node<T>* tail;

 public:
  DoublyLinkedList() : head(nullptr), tail(nullptr) {}

  // Method to add elements to the doubly linked list
  void insertBack(const T& value) {
    Node<T>* newNode = new Node<T>(value);
    if (!head) {
      head = tail = newNode;
    } else {
      tail->next = newNode;
      newNode->prev = tail;
      tail = newNode;
    }
  }

  // Iterator methods using nodes
  Node<T>* begin() const { return head; }

  Node<T>* end() const { return nullptr; }
};

int main() {
  // Create a doubly linked list and insert elements
  DoublyLinkedList<int> myList;
  myList.insertBack(1);
  myList.insertBack(2);
  myList.insertBack(3);

  // Iterate through the list using nodes
  std::cout << "Doubly Linked List Elements: ";
  for (Node<int>* current = myList.begin(); current != myList.end();
       current = current->next) {
    std::cout << current->data << " ";
  }

  return 0;
}

The first key component is the Node class, which serves as the fundamental building block of the doubly linked list. Each node within the list encapsulates data along with pointers to the next node (next) and the previous node (prev), forming the structural foundation of the data structure.

Moving on to the DoublyLinkedList class, it acts as the container for the doubly linked list, encapsulating methods essential for managing the list. Notably, the insertBack method facilitates the addition of elements to the list, while the iterator methods, namely begin and end, are introduced to retrieve pointers indicating the first and one-past-the-last elements in the list.

Within the main function, a DoublyLinkedList instance is created, and elements are inserted into the list using the insertBack method. Subsequently, a loop is employed to traverse the list using nodes.

The loop initializes the current pointer with the head of the list and iterates until it reaches the end of the list. During each iteration, the current pointer is updated to point to the next node, allowing for a sequential traversal of the doubly linked list.

This approach, utilizing the inherent structure of nodes for iteration, fosters a direct and clear implementation. By foregoing the need for a separate iterator class, the code achieves enhanced readability and simplicity. The output, as demonstrated by the provided example, affirms the successful traversal of the doubly linked list using the iterator based on nodes.

Output:

The output confirms that the iterator using nodes correctly traverses the doubly linked list, showcasing the effectiveness of this method in practice. Implementing an iterator using the nodes method for a doubly linked list in C++ provides a straightforward and direct approach.

This method leverages the inherent structure of the nodes, eliminating the need for a separate iterator class. The code example demonstrates a clean and efficient way to traverse a doubly linked list, enhancing code readability and simplicity.

Conclusion

Implementing an iterator for a doubly linked list in C++ offers two distinct approaches: the class method and the node method. The class method enhances code encapsulation and readability by providing a dedicated iterator class, offering a standardized and organized interface for iteration.

On the other hand, the node method, while more lightweight, may sacrifice some encapsulation. The choice between these methods depends on the specific needs of the codebase, balancing simplicity and clarity with the level of abstraction required.

Both methods showcase the flexibility of C++ in managing doubly linked lists, allowing developers to choose the approach that best suits their design preferences and project requirements.