Implementing our own Iterator Pattern
Although using STL makes our lives easier but it is always good to have a clear knowledge of the internal structure of the algorithm you are using so that you can get a clear picture of what's happening.
Our goal would be to implement push_back(), end(), and begin() methods so that we can use our Class just like we were using the implementation of STL.
Before Implementation let’s first look at the Algorithm or Steps that we can follow.
Algorithm
-
Create a custom LinkedList class with methods like push_back, traverse.
-
Create the Node class which represents the single Node in our list.
-
Create an Iterator class inside our LinkedList class and using operator overloading define the functionality of different operators.
-
Using the Iterator class define two methods namely begin() and end() which will return the start and the end of our linkedlist.
- Finally using all the defined method create a list and traverse it.
Implementation in C++
// C++ Code to implement the iterator.
#include <bits/stdc++.h>
using namespace std;
// Custom linkedlist class
template<typename T> class List {
private:
// represents a single node
class Node{
T data;
Node *next;
// LinkedList can access private members of Node
friend class List;
};
// takes in the data and returns the newly created node
Node *getNode(T data){
Node *newNode = new Node;
newNode->data = data;
newNode->next = nullptr;
return newNode;
}
// returns rootnode
Node* &getRootNode(){
return rootNode;
}
// static declaration
static Node *rootNode;
public:
// constructor
List<T>() {
rootNode = nullptr;
}
// Iterator class
class Iterator{
private:
const Node* currentNode;
public:
// constructor
Iterator() : currentNode(rootNode){ }
Iterator(const Node* node) : currentNode (node) { }
// overloading = operator
Iterator& operator=(Node* node){
this->currentNode = node;
return *this;
}
// overloading ++ operator (postfix)
Iterator& operator++(){
if(currentNode){
currentNode = currentNode->next;
}
return *this;
}
// overloading ++ operator (prefix)
Iterator operator++(int){
Iterator it = *this;
++*this;
return it;
}
// != operator overloading
bool operator!= (const Iterator& it){
return currentNode != it.currentNode;
}
// * operator overloading
int operator*(){
return currentNode->data;
}
};
// returns the iterator pointing at the start of our list
Iterator begin(){
return Iterator(rootNode);
}
// returns iterator pointing at the end of the list.
Iterator end() {
return Iterator(nullptr);
}
// implementation of push_back
// adds the data at the end of our list
void push_back(T data){
Node *temp = getNode(data);
if(getRootNode() == nullptr){
getRootNode() = temp;
}
else {
Node *head = getRootNode();
while(head->next){
head = head->next;
}
head->next = temp;
}
}
// traversing our list
void traverse(){
Node *head = getRootNode();
while(head){
cout << head->data << " ";
head = head->next;
}
cout << '\n';
}
};
// static variable initialisation
template <typename T> typename List<T>::Node* List<T>::rootNode = nullptr;
// main method
int main(){
// creating our list
List<int> list;
// adding elements
list.push_back(1);
list.push_back(2);
list.push_back(3);
list.push_back(4);
list.push_back(5);
// traversing using method
cout << "Traversing using method: ";
list.traverse();
// traversing using iterator
cout << "Traversing using Iterator: ";
for (List<int>::Iterator it = list.begin(); it != list.end(); it++){
cout << *it << ' ';
}
cout << '\n';
return 0;
}
You can also try this code with Online C++ Compiler
Output
Traversing using method: 1 2 3 4 5
Traversing using Iterator: 1 2 3 4 5
Time Complexity
As we are only traversing the list to the overall time complexity will be O(n).
Space complexity
Since no extra space is used the space complexity will be O(1).
Must Read: Java List Iterator
Frequently Asked Questions
What is STL in C++?
The C++ STL (standard template library) is a software library that provides a collection of templates that represent containers, iterators, algorithms, and function objects in the C++ programming language.
What is an iterator in C++?
An iterator is a C++ Standard Library container object that can loop over elements and provides access to individual elements.
Why are iterators used in C++?
We can use an iterator to go from one element to another. An iterator's key benefit is that it provides a common interface for all container types.
Conclusion
In this article, we have implemented our own Iterator pattern in a Singly linked list and also shown the difference between the normal traversal and the traversing using an iterator.
We hope that this blog has enhanced your knowledge and cleared all of your doubts regarding the above question. Check out our articles on our Website to learn more
Visit our Guided Path on Coding Ninjas Studio to upskill yourself in Competitive Programming, Data Structures and Algorithms, System Design, JavaScript, and many more! Check out the mock test series and participate in the contests hosted on Coding Ninjas Studio to test your proficiency in coding. But if you have just started your learning process and are looking for questions asked by tech giants like Amazon, Microsoft, etc; you must look at the interview experiences, problems, and interview bundle for placement preparations.
Nevertheless, you can also consider our paid courses to give your career an edge over others!
Do upvote the blog if you find it helpful and engaging!
Happy Learning!
116+ registered 