Equality operator for linked lists C++

Question

I am trying to create a linked list class and I'm having trouble determining how to check the equality of two lists using the operator== (equality operator). How would I go about going through each node and checking if elements within them are equal in their respective positions?

bool List::operator==(const List& list2) const {
    if(mySize != list2.mySize){
        return false;
    }
    if(myFirst == list2.myFirst){
        if(myFirst == NULL){
            return true;
        }

        Node * nPtr1 = myFirst;
        Node * nPtr2 = list2.myFirst;
        while(nPtr1 != NULL){
            //what can I do here to check the equality of each element in both lists?

        }
    }
}

Answer 1

According to your code, myFirst is a pointer, so the following is wrong:

if(myFirst == list2.myFirst)

Unless a node is equal to another node ONLY if it is the same node (pointer wise).

You have a special case when the lists are empty which you kind of captured:

if(myFirst == nullptr && list2.myFirst == nullptr)
{
    return true;
}

That would be the empty case.

Otherwise, you got the while properly, and if your items (Node) can simple be compared you would do:

p = myFirst;
q = list2.myFirst;
while(p != nullptr)
{
    if(*p != *q)  // this is what you're asking about, right?
    {
        return false;
    }
    p = p->next; // not too sure how you have a Node separated from the List
    q = q->next; // and check next/previous items...
}

return true;

Note that if nodes can only be equal if they have the same pointer then the compare becomes:

    if(p != q) // this is a test of pointers instead of objects

P.S. Someone mentioned using a recursive algorithm. That's an idea and conceptually it's great. When using such in the real world, though, you notice that it can be (much) slower. It has to very heavily use the stack and with very large lists, it could break your software.

Answer 2

while(nPtr1 != NULL){
       if(nPtr1 != nPtr2){
          return false;
       }
       nPtr1=nPtr1->next;
       nPtr2=nPtr2->next;
}
return true;

But this is the way to check if the two lists are identical (nPtr1 and nPtr2 are pointing to the same list). If you really want to compare lists by content you have to compare content like:

if(nPtr1->content != nPtr2->content)

and also change your first pointer check:

if(myFirst->content == list.myFirst->content)