如何使用常量时间(O(1))计算链表的长度

Question

我有一个函数来计算列表的长度.但这是线性时间.怎么能把它转换成恒定时间(O(1))

struct Node
{
    T data;
    Node *next;
};

同 Node *front; Node *back;

这是计算链表长度的功能

int length() const
{
    Node *p = front;
    int n = 0;

    while (p != nullptr)
    {
        n++;
        p = p->next;
    }

    return n;
}

Answer 1

因为这看起来像是一个家庭作业,我不会为你做这件事,但是因为你似乎对我的评论感到困惑,如果你被允许用新字段改变列表结构,理论上如何做到这一点可能是这样的:

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

template<typename Node>
struct List
{
    // I assume there is a thingy that initializes these, otherwise bad things will happen
    Node *front;
    Node *back;
    int length;

    void add(Node* node) // No idea what the signature is
    {
        // I am not gonna do the adding for you

        // If everything went fine increase the length
        length += 1;
    }

    void remove(Node* node) // Again, no idea of the signature
    {
        // Again, not gonna do the removal

        // If everything went fine decrease the length
        length -= 1;
    }

    int get_length() const
    {
        return length;
    }
};