Implementing Iterator pattern of a single linked list

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we will be implementing the Iterator pattern of a singly linked list.

Problem Statement Understanding

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)

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

  • 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

Code Implementation (STL and Collections)


#include 
using namespace std;
 
int main()
{
    vector list;
    list.push_back(1);
    list.push_back(3);
    list.push_back(5);
 
    for (vector::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 list = new ArrayList<>();

        list.add(1);
        list.add(3);
        list.add(5);
 

        Iterator it = list.iterator();
        while (it.hasNext())
        {
            System.out.print(it.next() + " ");
        }
    }
}

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)

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

  • 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)



#include 
using namespace std;

template 
class LinkedList
{
    class Node;

public:
    LinkedList() 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 LinkedList::Node* LinkedList::m_spRoot = nullptr;

template 
void LinkedList::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 
void LinkedList::Traverse()
{
    Node* pCrawler = GetRootNode();

    while (pCrawler)
    {
        cout << pCrawler->data << " ";
        pCrawler = pCrawler->pNext;
    }

    cout << endl;
}

int main()
{
    LinkedList 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::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: O(n), as no nested traversal is required.

So, in this article, we have tried to explain the most efficient approach to implement the iterator pattern of a single 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.

Previous post Insert a node after the n-th node from the end
Next post Memory efficient doubly linked list

Leave a Reply

Your email address will not be published. Required fields are marked *