Last Updated on November 14, 2022 by Prepbytes
This blog will describe both approaches (Manual and STL) for creating linked list iterator. Solving for finding iterator for linked list with different approaches will give a better understanding of linked lists. Linked list is an essential topic of data structures. Now let’s move to our topic for getting linked list iterator.
How To Find Iterator For Linked List
Using the STL( Standard Template Library) in C++ makes our life a lot easier. We don’t have to spend time writing and implementing long codes, which are already available. This increases the reusability of the code. But, we should not always depend on library functions. Although it increases our efficiency, we should know its functionalities and way of processing.
Input: 1 3 5
Output: 1 3 5
Explanation:We are traversing through the linked list and printing numbers one by one.
Approach (STL) To Find Iterator For Linked List
Here, we will create a list using STL. To add elements, we will use the keyword push_back and, lastly, iterate through the list using iterators.
Algorithm To Find Iterator For Linked List
- Create a list using the STL.
- Add elements to the list using push_back.
- Use iterators to iterate through the list.
- Print the list items.
Dry Run To Find Iterator For Linked List
Code Implementation (STL and Collections) To Find Iterator For Linked List
#include <bits stdc++.h="">
using namespace std;
int main()
{
vector<int> list;
list.push_back(1);
list.push_back(3);
list.push_back(5);
for (vector<int>::iterator it = list.begin();
it != list.end(); ++it)
cout << *it << " ";
return 0;
}
import java.util.*;
public class PrepBytes
{
public static void main(String[] args)
{
ArrayList<integer> list = new ArrayList<>();
list.add(1);
list.add(3);
list.add(5);
Iterator<integer> it = list.iterator();
while (it.hasNext())
{
System.out.print(it.next() + " ");
}
}
}
if __name__=='__main__': list = [] list.append(1) list.append(3) list.append(5) for it in list: print(it, end = ' ')
Although STL is very efficient when it comes to problem-solving, let’s look at what is going on when we use the iterators.
Approach (Manual) To Find Iterator For Linked List
Firstly, we will input the list items. Here, we will see how push_back works and how the iterator traverses through the linked list. We can sequentially access the nodes of the linked list using the iterator class.
We will define various methods such as begin(), end(), and push_back(). These are some commonly used STL methods. Let us look at the algorithm to get a clearer look.
Algorithm To Find Iterator For Linked List
- Create a custom class to handle linked list operations like push_back(), push_front(), pop_back().
- We wrap the start of the linked list in the begin() method, and the end of the linked list in the end() method.
- We also create a push_back() method to add data to the linked list
- We create methods for operators too. The = operator, prefix operator and the postfix operator.
- Then, we create add functions to create a node and return the new node to the caller method.
- Finally, with the help of all the above-used methods, we implement the push_back() and then print the elements of the linked list.
Code Implementation (Manual) To Find Iterator For Linked List
#include <bits/stdc++.h>
using namespace std;
template <typename T>
class LinkedList
{
class Node;
public:
LinkedList<T>() noexcept
{
m_spRoot = nullptr;
}
class Iterator;
Iterator begin()
{
return Iterator(m_spRoot);
}
Iterator end()
{
return Iterator(nullptr);
}
void push_back(T data);
void Traverse();
class Iterator
{
public:
Iterator() noexcept :
m_pCurrentNode (m_spRoot) { }
Iterator(const Node* pNode) noexcept :
m_pCurrentNode (pNode) { }
Iterator& operator=(Node* pNode)
{
this->m_pCurrentNode = pNode;
return *this;
}
Iterator& operator++()
{
if (m_pCurrentNode)
m_pCurrentNode = m_pCurrentNode->pNext;
return *this;
}
Iterator operator++(int)
{
Iterator iterator = *this;
++*this;
return iterator;
}
bool operator!=(const Iterator& iterator)
{
return m_pCurrentNode != iterator.m_pCurrentNode;
}
int operator*()
{
return m_pCurrentNode->data;
}
private:
const Node* m_pCurrentNode;
};
private:
class Node
{
T data;
Node* pNext;
friend class LinkedList;
};
Node* GetNode(T data)
{
Node* pNewNode = new Node;
pNewNode->data = data;
pNewNode->pNext = nullptr;
return pNewNode;
}
Node*& GetRootNode()
{
return m_spRoot;
}
static Node* m_spRoot;
};
template <typename T>
typename LinkedList<T>::Node* LinkedList<T>::m_spRoot = nullptr;
template <typename T>
void LinkedList<T>::push_back(T data)
{
Node* pTemp = GetNode(data);
if (!GetRootNode())
{
GetRootNode() = pTemp;
}
else
{
Node* pCrawler = GetRootNode();
while (pCrawler->pNext)
{
pCrawler = pCrawler->pNext;
}
pCrawler->pNext = pTemp;
}
}
template <typename T>
void LinkedList<T>::Traverse()
{
Node* pCrawler = GetRootNode();
while (pCrawler)
{
cout << pCrawler->data << " ";
pCrawler = pCrawler->pNext;
}
cout << endl;
}
int main()
{
LinkedList<int> list;
list.push_back(1);
list.push_back(3);
list.push_back(5);
cout << "Traversing through method" << endl;
list.Traverse();
cout << "Traversing through Iterator" << endl;
for ( LinkedList<int>::Iterator iterator = list.begin();
iterator != list.end(); iterator++)
{
cout << *iterator << " ";
}
cout << endl;
return 0;
}
Output
Traversing through method
1 3 5
Traversing through iterators
1 3 5
Time Complexity To Find Iterator For Linked List: O(n), as no nested traversal is required.
So, in this article, we have tried to explain the various approaches to implement an iterator for linked list. This question gives us insights into the iterator usage in a linked list. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.
FAQs
1. Can iterators be used for linked lists?
An Iterator can be used to loop through a Linked List.
2. What is the iterator in the linked list C++?
An iterator is an object that allows you to traverse a list.
3. Why do we need an iterator?
The primary purpose of an iterator is to allow a user to process every element of a container while isolating the user from the internal structure of the container.