overload == to compare two linked list recursively

Question

I have a homework problem, which asks me to overload == operator to compare two linked-list. And i need to do this in recursion.

Here is my .h file

class  LList {
   public:
      friend bool operator == (const LList& lfSide, const LList& rtSide);
   private:
      struct Node {
         int item;
         Node* next;
      };
      friend bool operator == (const LList& lfSide, Node* headlf, const LList& rtSide, Node* headrt);
      Node* head;
}

I tried to use a helper function to make the recursion happen, but it still gives error saying Node is not defined.

friend bool operator == (const LList& lfSide, Node* headlf, const LList& rtSide, Node* headrt);

Can anyone help me with this?

Answer 1

This might help you. I kept the things simple by making some member variables as public.

class Node
{
public:
    int m_Value = -1;
    Node* m_Next = nullptr;
    Node()
    {
        m_Value = -1;
        m_Next = NULL;
    }
};

//Linked List class
class LinkedList
{
    //Head Node
    Node* m_Head;
    //Tail Node
    Node* m_Last;

public:
    //Constructor
    LinkedList()
    {
        m_Head = nullptr;
        m_Last = nullptr;
    }
    //Add value to list
    void AddValue(int value)
    {
        if (m_Head == nullptr)
        {
            m_Head = new Node();
            m_Head->m_Value = value;
            m_Last = m_Head;
        }
        else
        {
            Node* newNode = new Node();
            newNode->m_Value = value;
            m_Last->m_Next = newNode;
            m_Last = newNode;
        }
    }

    //Display the elements of the list
    void display()
    {
        Node* travelNode = m_Head;
        while (travelNode != nullptr)
        {
            cout << travelNode->m_Value << " ==> ";
            travelNode = travelNode->m_Next;
        }
    }

    //Compare function
    bool operator==(const LinkedList& List)
    {
        return CompareList(this->m_Head, List.m_Head);
    }

    bool CompareList( Node* LeftList,  Node* rightList)
    {
        //If both nodes reaches to end then it is equal
        if (LeftList == nullptr && rightList == nullptr) return true;

        //If one of the node has more nodes then list are not equal
        if (LeftList == nullptr || rightList == nullptr) return false;

        //Compare the values
        if (LeftList->m_Value != rightList->m_Value) return false;

        //Call recursion
        CompareList(LeftList->m_Next, rightList->m_Next);
    }
};

int main()
{
    //First List
    LinkedList list1;
    list1.AddValue(1);
    list1.AddValue(2);
    list1.AddValue(3);
    list1.AddValue(4);
    list1.AddValue(5);

    //list1.display();

    //Second List
    LinkedList list2;
    list2.AddValue(1);
    list2.AddValue(2);
    list2.AddValue(3);
    list2.AddValue(4);
    list2.AddValue(5);

    //list2.display();

    //Compare
    bool areEq = list1 == list2;
    cout << "Are Equal " << areEq << endl;
}

Answer 2

One more approach could be to have only one argument passed to operator == as this is passed implicitly.Here is complete code

template <typename T>
struct Node
{
    T data;
    Node<T>* next;
};
template <class T>
class LinkedList
{
private:
    Node<T>* head;  

    bool internalCompare(Node<T>* first, Node<T>* second)
    {
        if((first == nullptr) && (second == nullptr))
        {
            return true;
        }
        else if(((first == nullptr) && (second != nullptr)) || ((first != nullptr) && (second == nullptr)))
        {
            return false;
        }
        else if (first->data != second->data)
        {
            return false;
        }
        return internalCompare(first->next,second->next);
    }
public:
    LinkedList() :head(nullptr) {}      
    bool operator ==(LinkedList<T> & second)
    {
        if(internalCompare(head,second.head))
        {
            return true;
        }
        return false;
    }
};

Answer 3

The structure Node is a private data member, It may not be used in the friend declaration

friend bool operator == (const LList& lfSide, Node* headlf, const LList& rtSide, Node* headrt);

You could define the structure like

#include <iostream>
class  LList {
   public:
      friend bool operator == (const LList& lfSide, const LList& rtSide);
   private:
      struct Node {
         int item;
         Node* next;
         bool operator ==( const Node &headrt);
      };
      Node* head;
};

And within the friend operator use the operator == of the structure Node.