C++:链表表示

Question

我知道如何表示链表的方法基本上是创建一个 Node 类（最好是结构体），并创建实际的 linkedList 类。但是，昨天我正在寻找反转单向链表操作的逻辑，我遇到的几乎 90% 的解决方案都包含返回数据类型 Node* 的函数。因此，我感到困惑，因为如果您无论执行什么操作都想反转列表，它不会再次出现在 linkedList 的类型中吗？我做错了吗？

我一直在做的链表实现;

#include <iostream>
using namespace std;
struct Node
{
    int data;
    Node *next;
};
class linkedList
{
public:
    Node* firstPtr;
    Node* lastPtr;
    linkedList()
    {
        firstPtr=lastPtr=NULL;
    }
    void insert(int value)
    {
        Node* newNode=new Node;
        newNode->data=value;
        if(firstPtr==NULL)
            firstPtr=lastPtr=newNode;
        else {
            newNode->next=firstPtr;
            firstPtr=newNode;
        }
    }
    void print()
    {
        Node *temp=firstPtr;
        while(temp!=NULL)
        {
            cout<<temp->data<<" ";
            temp=temp->next;
        }
    }
};

Answer 1

你的方法没有错，但你可能过于强调你的linkedList类。

该类实际上包含什么？指向第一个节点的指针和指向最后一个节点的指针（这是冗余信息，因为您只能通过知道第一个节点来找到最后一个节点）。所以基本上linkedList只是一个没有额外信息的帮助类。

来自linkedList的成员函数可以很容易地在Node内部移动，或者成为以Node作为参数的自由函数。

Answer 2

那么，什么是链表，而是指向第一个节点的指针？只要您可以访问第一个节点，列表是完全可访问的，您所需要的只是一个指向第一个节点的指针。

除非要存储有关列表的额外控件信息（例如其长度），否则不需要为列表本身使用单独的数据类型。

现在，为了提高效率，一些实现（例如您的实现）还可以存储指向列表中最后一个节点的指针，从而允许您在 O（1） 而不是 O（n） 中附加项目。但这是列表的额外功能，而不是一般列表的要求。

Answer 3

这些函数可能返回 Node* 类型，因为在反转链表后，它们将返回指向列表第一个节点的指针。