Как рассчитать длину связанного списка, используя постоянное время (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;
    }
};