双向链表的有效性

我目前在数据结构课程中。教授将提供一个单链表。我想制作一个双向链接列表以“学习”如何做。我对其进行了测试，并且认为它可行。制作完之后，我确实将其与其他双向链接列表进行了比较，但我仍然想看看是否缺少任何内容。还有其他问题吗？

LinkNode类别：

#ifndef LINKNODE_H_
#define LINKNODE_H_
#include <iostream>
template<class E>
class LinkNode {

public:
    E data;
    LinkNode<E> *leftNode;
    LinkNode<E> *rightNode;
    LinkNode() {

    }
    LinkNode(E e) {
        this->data = e;
    }
    ~LinkNode() {
    }
    E getData() {
        return data;
    }
    void setData(E e) {
        this->data = e;
    }
    LinkNode<E> getLeftNode() {
        return leftNode;
    }
    void setLeftNode(LinkNode<E> node) {
        this->leftNode = node;
    }
    LinkNode<E> getRightNode() {
        return rightNode;
    }
    void setRightNode(LinkNode<E> node) {
        this->rightNode = node;
    }

};

#endif /* LINKNODE_H_ */

LinkedList类别：

    #ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include "LinkNode.h"
template<class T>
class LinkedList {
private:
    int size;
    LinkNode<T> *firstNode;
    LinkNode<T> *lastNode;
public:

    LinkedList() {
        firstNode = new LinkNode<T>();
        lastNode = firstNode;
        size = 0;
    }

    ~LinkedList() {
    }

    void pushFront(T t) {
        if (size == 0) {
            pushBack(t);
            return;
        }
        LinkNode<T> *linkNode = new LinkNode<T>(t);
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
        size++;
    }

    void pushBack(T t) {
        LinkNode<T> *linkNode = new LinkNode<T>(t);
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
        if (size == 0) {
            firstNode = lastNode;
        }
        size++;
    }

    T pollFirst() {
        T t = firstNode->data;
        firstNode = firstNode->rightNode;
        size--;
        return t;
    }

    T pollLast() {
        T t = lastNode->data;
        lastNode = lastNode->leftNode;
        size--;
        return t;
    }

    LinkNode<T> getFirstNode() {
        return firstNode;
    }

    LinkNode<T> getLastNode() {
        return lastNode;
    }

    T searchNode(T t) {
        return t;
    }
    int Size() {
        return size;
    }

    void printLinkedList() {
        LinkNode<T> *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }

};
#endif /* LINKEDLIST_H_ */

新LinkedList类别：

#ifndef LINKEDLIST_H_
#define LINKEDLIST_H_
#include <iostream>
template<class T>
class LinkedList {
    /**
     * Private inner node class
     */
    //Have to use new template. Does not run if I try to use T
    template<class E>
    class LinkNode {
    public:
        E data;
        LinkNode<E> *leftNode;
        LinkNode<E> *rightNode;
        LinkNode() {

        }
        LinkNode(E e) {
            this->data = e;
        }
        ~LinkNode() {
        }
    };
private:
    int size;
    LinkNode<T> *firstNode;
    LinkNode<T> *lastNode;
public:

    LinkedList() {
        firstNode = new LinkNode<T>();
        /*
         * Init left and right node to null to prevent exception.
         */
        firstNode->leftNode = NULL;
        firstNode->rightNode = NULL;
        lastNode = firstNode;
        size = 0;
    }

    ~LinkedList() {
        LinkNode<T> *linkNode = firstNode->rightNode;
        while (linkNode != NULL) {
            delete linkNode->leftNode;
            linkNode = linkNode->rightNode;
        }
    }

    void pushFront(T t) {
        //the size is zero therefore we are really justing pushing to the back of the linked list
        if (size == 0) {
            pushBack(t);
            return;
        }
        LinkNode<T> *linkNode = new LinkNode<T>(t);
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
        size++;
    }

    void pushBack(T t) {
        LinkNode<T> *linkNode = new LinkNode<T>(t);
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
        if (size == 0) {
            firstNode = lastNode;
        }
        size++;
    }

    T pollFirst() {
        LinkNode<T> *temp = firstNode;
        T t = firstNode->data;
        firstNode = firstNode->rightNode;
        delete temp;
        size--;
        return t;
    }

    T pollLast() {
        LinkNode<T> *temp = lastNode;
        T t = lastNode->data;
        lastNode = lastNode->leftNode;
        delete temp;
        size--;
        return t;
    }

    LinkNode<T> getFirstNode() {
        return *firstNode;
    }

    LinkNode<T> getLastNode() {
        return *lastNode;
    }

    int const Size() {
        return size;
    }

    void const printLinkedList() {
        LinkNode<T> *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }

};
#endif /* LINKEDLIST_H_ */

Xubuntu 13.10
使用sudo apt-get install g ++安装的GCC编译器

#1 楼

新的链接列表类

这是对新的“新的链接列表类”的评论。

您在这里写道：

//Have to use new template. Does not run if I try to use T
template<class E>
class LinkNode {
public:
    E data;
    LinkNode<E> *leftNode;
    LinkNode<E> *rightNode;
    LinkNode() {

    }
    LinkNode(E e) {
        this->data = e;
    }
    ~LinkNode() {
    }
};

我说，“ LinkNode不再是模板类：它是模板类的嵌套类。”

您说过不想阅读我的代码，但是下面是我的代码：

    // Not a template class.
    // template<class E>
    class LinkNode {
    public:
        E data;
        LinkNode *leftNode;
        LinkNode *rightNode;
        LinkNode() {

        }
        LinkNode(E e) {
            this->data = e;
        }
        ~LinkNode() {
        }
    };
private:
    int size;
    LinkNode *firstNode;
    LinkNode *lastNode;

在C ++中，与Java不同，成员不会自动初始化为0。也许您的编译器将它们初始化为0，但我的不是。您的编译器可能会给您留下未初始化的内存，该内存刚好是零填充，但是如果您的程序在许多先前的new和delete上运行了更长的时间，则该内存将不再为零填充。

如果我在第一次按下按钮后执行printLinkedList，它将崩溃。那是因为您的push方法是这样的：

void pushBack(T t) {
    LinkNode<T> *linkNode = new LinkNode<T>(t);
    linkNode->leftNode = lastNode;
    lastNode->rightNode = linkNode;
    lastNode = linkNode;
    if (size == 0) {
        firstNode = lastNode;
    }
    size++;
}

它不会初始化新linkNode的rightNode成员。

您可能想要初始化LinkNode构造函数中的所有内容：将leftNode和rightNode设置为0。

在第一次推送之前，firstNode和lastNode指向您的初始空“哨兵”节点。 >
第一次推送后，firstNode和lastNode指向新节点，新节点的leftNode指向您的前哨节点。

然后在下一个pushFront之后，没有任何东西指向您的前哨节点。如果您将要失去列表中的前哨节点，那么我认为没有任何理由创建它。（我在其他答案中提出的解决方案没有创建初始的哨兵节点，而是将列表设置为空时设置并期望firstNode和lastNode为NULL）。

如果我在将任何内容推入列表之前先调用printLinkedList，它会打印出初始的，空的，前哨节点中包含的值（可能为0，可能还有其他值）。

如果运行以下测试代码，然后打印无限数量的2 s：

LinkedList<int> linked;
linked.printLinkedList();
linked.pushFront(10);
linked.printLinkedList();
linked.pollFirst();
linked.printLinkedList();
linked.pushBack(2);
linked.printLinkedList();

#2 楼

假设这不是内部类：

一个大问题（可能是最大的问题）是，所有问题都是public。这三个数据成员应为private。数据成员应始终为private，否则任何外部代码都可以访问它们。与class相比，这违背了使用struct的目的。

您也不应具有任何访问器（“获取器”）和变异器（“ setters”）。该节点应仅属于该类，并且其实现都不应公开。列表本身应该使用节点，并且应该能够直接访问该节点的成员。

节点的实现包括其指针（对于单个列表，请使用next；对于单个节点，请使用previous和next节点双重清单）及其数据。可以是列表类内部的struct或class，作为private数据成员。

class的模板化节点实现示例：

template <typename T>
class Node
{
    T data;
    Node<T>* previous;
    Node<T>* next;
};

LinkedList

巨大的问题：没有析构函数！您需要一个用于链表的析构函数，以便其分配的节点在使用后将被删除。否则，您将发生内存泄漏。析构函数应该遍历每个节点，在每个节点上使用delete直到列表为空。
您应该定义一个复制构造函数和赋值运算符（operator=）。默认的拷贝构造函数执行的是浅拷贝而不是深拷贝，并且浅拷贝很难将指针用作成员。复制仍然可以编译（使用默认值），但是不能正确完成。

size()应该是const，因为它没有修改任何数据成员：

int Size() const { return size; }

另一方面，Size()应该小写以匹配您的其他功能。不必使用其他名称。

printLinkedList()也应该是const，因为它没有修改任何数据成员。由于其性质，这通常适用于显示函数。
searchNode()仅返回其自变量而不是进行实际搜索，因此它已过时，应将其删除。
pollFirst()和pollLast()分别用于什么？名称不是很清楚。如果它们不足，则将其全部写出。
摆脱getFirstNode()和getLastNode()。您不应该将节点公开给公众，这对封装不利。将节点功能保留在列表中。

\ $ \ begingroup \ $
我是Java开发人员，“他们”的链接列表包含pollFirst（）和pollLast（）。它返回第一个或最后一个节点数据，然后从链接列表中将其删除。
\ $ \ endgroup \ $
– Horvste
14年2月14日，0：04

\ $ \ begingroup \ $
@horvste：好的。我是C ++审阅者（并且没有Java经验），所以我没有意识到。
\ $ \ endgroup \ $
– Jamal♦
2014年2月14日下午0:06

\ $ \ begingroup \ $
@horvste这些方法将满足（De）Queue接口。
\ $ \ endgroup \ $
– David Harkness
2014年2月14日下午4:02

#3 楼

当我在计算机上运行测试代码时，它崩溃。

列表中的第一个节点包含'10'
列表中的第二个节点包含'0'
列表中的第3个节点包含'2'
当尝试取消引用第4个节点时，第3个节点的rightNode元素包含垃圾地址=>异常

所以我将尝试清理该节点

，紧接着Jamal的回答，下面的代码重新制作了代码以实现他的建议。

首先，唯一的变化是我使LinkNode成为LinkList的私有嵌套类。

其次，我们不再需要两个单独的模板参数：因此，摆脱E，而只有T。 LinkNode不再是模板类：它是模板类的嵌套类。

#include <iostream>
template<class T>
class LinkedList {
private:
    class LinkNode {

    public:
        T data;
        LinkNode *leftNode;
        LinkNode *rightNode;
        LinkNode() {
        }
        LinkNode(T e) {
            this->data = e;
        }
        ~LinkNode() {
        }
        T getData() {
            return data;
        }
        void setData(T e) {
            this->data = e;
        }
        LinkNode getLeftNode() {
            return leftNode;
        }
        void setLeftNode(LinkNode node) {
            this->leftNode = node;
        }
        LinkNode getRightNode() {
            return rightNode;
        }
        void setRightNode(LinkNode node) {
            this->rightNode = node;
        }

    };
    int size;
    LinkNode *firstNode;
    LinkNode *lastNode;
public:

    LinkedList() {
        firstNode = new LinkNode();
        lastNode = firstNode;
        size = 0;
    }

    ~LinkedList() {
    }

    void pushFront(T t) {
        if (size == 0) {
            pushBack(t);
            return;
        }
        LinkNode *linkNode = new LinkNode(t);
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
        size++;
    }

    void pushBack(T t) {
        LinkNode *linkNode = new LinkNode(t);
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
        if (size == 0) {
            firstNode = lastNode;
        }
        size++;
    }

    T pollFirst() {
        T t = firstNode->data;
        firstNode = firstNode->rightNode;
        size--;
        return t;
    }

    T pollLast() {
        T t = lastNode->data;
        lastNode = lastNode->leftNode;
        size--;
        return t;
    }

    LinkNode getFirstNode() {
        return firstNode;
    }

    LinkNode getLastNode() {
        return lastNode;
    }

    T searchNode(T t) {
        return t;
    }
    int Size() {
        return size;
    }

    void printLinkedList() {
        LinkNode *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }

};

接下来，我尝试调用其中一个返回LinkNode的方法。在测试程序中添加linked.getFirstNode();语句会给我带来以下编译器错误：

'LinkedList<T>::LinkNode::LinkNode(T)' : cannot convert parameter 1 from 'LinkedList<T>::LinkNode *' to 'int'

getFirstNode（）方法的问题在于，它承诺会返回一个LinkNode，然后尝试返回作为LinkNode *指针的firstNode（这是非法的）。对于C ++模板，除非您使用它，否则编译器不会尝试实例化该方法。您没有尝试使用它，因此编译器没有注意到该编码错误。

幸运的是，您不应该尝试使用它：LinkNode应该是LinkedList的私有实现细节。因此，我只删除getFirstNode和getLastNode方法。

还不清楚您的searchNode方法在做什么，并且您也没有对其进行测试，因此我也将其删除。 >
我将删除大多数LinkNode方法，因为LinkedList直接访问其数据成员，并且因为LinkedList之外的其他类根本无法访问其任何成员。

#pragma once
#include <iostream>
template<class T>
class LinkedList {
private:
    class LinkNode {

    public:
        T data;
        LinkNode *leftNode;
        LinkNode *rightNode;
        LinkNode() {
        }
        LinkNode(T e) {
            this->data = e;
        }
        ~LinkNode() {
        }
    };
    int size;
    LinkNode *firstNode;
    LinkNode *lastNode;
public:

    LinkedList() {
        firstNode = new LinkNode();
        lastNode = firstNode;
        size = 0;
    }

    ~LinkedList() {
    }

    void pushFront(T t) {
        if (size == 0) {
            pushBack(t);
            return;
        }
        LinkNode *linkNode = new LinkNode(t);
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
        size++;
    }

    void pushBack(T t) {
        LinkNode *linkNode = new LinkNode(t);
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
        if (size == 0) {
            firstNode = lastNode;
        }
        size++;
    }

    T pollFirst() {
        T t = firstNode->data;
        firstNode = firstNode->rightNode;
        size--;
        return t;
    }

    T pollLast() {
        T t = lastNode->data;
        lastNode = lastNode->leftNode;
        size--;
        return t;
    }

    int Size() const {
        return size;
    }

    void printLinkedList() const {
        LinkNode *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }

};

下一个问题是在列表为空时使用哨兵节点。

以下方法创建了一个初始的空节点...

LinkedList() {
    firstNode = new LinkNode();
    lastNode = firstNode;
    size = 0;
}

...，但未初始化该节点的leftNode和rightNode元素（稍后会导致崩溃）。

我也对列表中有一个空节点的想法感到困惑：如何确保printLinkedList不会尝试打印该空节点的内容？

因此，我按如下所示更改代码以摆脱空节点：

从LinkNode中删除默认构造函数（因此只能在有数据时实例化）。
在LinkNode构造函数中将LinkNode的指针元素初始化为null
在LinkedList构造函数中将LinkedList的指针元素初始化为null
pushFront和pushBack中的特殊情况以处理插入到空列表中的情况
使用pollFirst和pollLast处理列表中的最后一个节点的特殊情况

这些更改之后，代码如下所示：

#pragma once
#include <iostream>
template<class T>
class LinkedList {
private:
    class LinkNode {

    public:
        T data;
        LinkNode *leftNode;
        LinkNode *rightNode;
        LinkNode(T e) {
            this->data = e;
            leftNode = 0;
            rightNode = 0;
        }
        ~LinkNode() {
        }
    };
    int size;
    LinkNode *firstNode;
    LinkNode *lastNode;
public:

    LinkedList() {
        firstNode = 0;
        lastNode = 0;
        size = 0;
    }

    ~LinkedList() {
    }

    void pushFront(T t) {
        LinkNode *linkNode = new LinkNode(t);
        ++size;
        if (size == 1) {
            firstNode = lastNode = linkNode;
            return;
        }
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
    }

    void pushBack(T t) {
        LinkNode *linkNode = new LinkNode(t);
        ++size;
        if (size == 1) {
            firstNode = lastNode = linkNode;
            return;
        }
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
    }

    T pollFirst() {
        T t = firstNode->data;
        firstNode = firstNode->rightNode;
        if (firstNode)
            firstNode->leftNode = NULL;
        --size;
        return t;
    }

    T pollLast() {
        T t = lastNode->data;
        lastNode = lastNode->leftNode;
        if (lastNode)
            lastNode->rightNode = NULL;
        --size;
        return t;
    }

    int Size() const {
        return size;
    }

    void printLinkedList() const {
        LinkNode *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }
};

也测试输出如下所示（这是正确的结果，并且不再崩溃）：

10      0       2

剩下的问题是您不删除节点您创建的。我将代码更改如下：

向poll方法添加delete语句（以删除从列表中删除的节点）
从LinkedList析构函数调用delete语句（在删除列表时删除列表上的节点）

进行这些更改之后，代码如下：

#pragma once
#include <iostream>
#include <assert.h>
template<class T>
class LinkedList {
private:
    class LinkNode {
    public:
        T data;
        LinkNode *leftNode;
        LinkNode *rightNode;
        LinkNode(T e) {
            this->data = e;
            leftNode = 0;
            rightNode = 0;
        }
        ~LinkNode() {
        }
    };
    int size;
    LinkNode *firstNode;
    LinkNode *lastNode;
public:

    LinkedList() {
        firstNode = 0;
        lastNode = 0;
        size = 0;
    }

    ~LinkedList() {
        LinkNode *temp = firstNode;
        while (temp != NULL) {
            LinkNode *next = temp->rightNode;
            delete temp;
            temp = next;
        }
    }

    void pushFront(T t) {
        LinkNode *linkNode = new LinkNode(t);
        ++size;
        if (size == 1) {
            firstNode = lastNode = linkNode;
            return;
        }
        linkNode->rightNode = firstNode;
        firstNode->leftNode = linkNode;
        firstNode = linkNode;
    }

    void pushBack(T t) {
        LinkNode *linkNode = new LinkNode(t);
        ++size;
        if (size == 1) {
            firstNode = lastNode = linkNode;
            return;
        }
        linkNode->leftNode = lastNode;
        lastNode->rightNode = linkNode;
        lastNode = linkNode;
    }

    T pollFirst() {
        LinkNode *found = firstNode;
        T t = found->data;
        firstNode = found->rightNode;
        if (firstNode)
            firstNode->leftNode = NULL;
        else {
            assert(size == 1);
            lastNode = 0;
        }
        delete found;
        --size;
        return t;
    }

    T pollLast() {
        LinkNode *found = lastNode;
        T t = found->data;
        lastNode = found->leftNode;
        if (lastNode)
            lastNode->rightNode = NULL;
        else {
            assert(size == 1);
            firstNode = 0;
        }
        delete found;
        --size;
        return t;
    }

    int Size() const {
        return size;
    }

    void printLinkedList() const {
        LinkNode *temp = firstNode;
        while (temp != NULL) {
            std::cout << temp->data << "\t";
            temp = temp->rightNode;
        }
    }
};

\ $ \ begingroup \ $
现在，这是一些认真的史诗答案！
\ $ \ endgroup \ $
– Mathieu Guindon♦
2014年2月14日在3:09

\ $ \ begingroup \ $
@ lol.upvote：它确实需要大量清洁。 :-)这样的实现非常重视。
\ $ \ endgroup \ $
– Jamal♦
2014-2-14在3:14

\ $ \ begingroup \ $
我的不会崩溃。可能与编译器有所不同吗？我正在使用gcc编译器。无论如何，我会根据您的建议进行一些清理，然后将代码重新发布以进行进一步检查。我正在尝试学习它，所以我阅读了您的建议，但没有看代码。
\ $ \ endgroup \ $
– Horvste
2014年2月14日在17:55

\ $ \ begingroup \ $
@horvste是的，可能与编译器有所不同。注意，当您调用firstNode = new LinkNode （）;时，您不会初始化该第一个节点的leftValue和rightValue字段。可能/可能对于您的编译器而言，这些字段值恰好为0，这会导致printLinkedList中的while（temp！= NULL）在找到它们时退出。在以调试模式运行的编译器中，未初始化的字段被初始化为类似0xadadadad的值（通过崩溃，该值使检测使用未初始化的指针的尝试更容易）。
\ $ \ endgroup \ $
– ChristW
14年2月14日在18:00

\ $ \ begingroup \ $
@horvste出了什么问题了，在C ++中（与Java不同），如果您未在构造函数中初始化字段，则该字段包含伪随机值（可能但不一定为0）。因此，您的LinkNode（）{}构造函数可能应该将其leftField和rightField元素显式初始化为0：LinkNode（）{leftField = 0; rightField = 0;数据= ???; }
\ $ \ endgroup \ $
– ChristW
2014年2月14日的19:00

#4 楼

使用链接列表时，要做的一件非常重要的事情是在添加/删除节点时链接和取消链接上一个/下一个节点。

如果只能在末尾添加，那很好，但是如果可以在任何地方插入节点，则必须小心。删除节点也是如此。

         +--------+    +--------+    +--------+
         |    A   |    |   B    |    |    C   |
         |   A.n  |--->|  B.n   |--->|   C.n  |---> null
null <---|   A.p  |<---|  B.p   |<---|   C.p  |
         +--------+    +--------+    +--------+

在此表示中，从列表中删除B意味着将An指向C而不是B，并将Cp指向A而不是B B.并将Bn和Bp设置为nullptr。类似地，如果您只有A和C并且想添加B，那么现在需要将Bp设置为A并将An设置为B。然后将Cp设置为B和Bn转换为C。

您似乎只想提供推式和弹出式按钮，所以它使它更简单，但这是需要牢记的。

另外两个注意：

我看到您在类中使用this-> ...；
您可能要考虑使用std::shared_ptr<>()，以便多个人可以拥有一个节点，并且在完成所有操作之前不会删除它。

编程黑洞网

双向链表的有效性

#1 楼

#2 楼

评论

#3 楼

评论

#4 楼