链接列表的相等运算符C++

Question

我正在尝试创建一个链接列表类，并且在确定如何使用operator== (相等运算符)检查两个列表的相等性时遇到了困难。我将如何遍历每个节点并检查它们中的元素在各自位置上是否相等？

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

根据您的代码，myFirst是一个指针，因此以下内容是错误的：

if(myFirst == list2.myFirst)

除非一个节点等于另一个节点，只有当它是同一个节点时(指针明智)。

当列表为空时，有一个特殊情况，您可以捕捉到：

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

那将是个空箱子。

否则，您正确地获得了时间，如果您的项(节点)可以简单地进行比较，您可以这样做：

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;

注意，如果节点只有在具有相同指针的情况下才能相等，则比较如下：

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

有人提到使用递归算法。这是一个想法，从概念上说是很棒的。然而，在现实世界中使用这种方法时，您会注意到它可能会慢很多。它必须非常大量地使用堆栈，并且使用非常大的列表，它可能会破坏您的软件。

Answer 2

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

但这是检查两个列表是否相同的方法(nPtr1和nPtr2指向相同的列表)。如果您真的想按内容比较列表，则必须比较以下内容：

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

并更改第一个指针检查：

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