How to calculate the length of the linked list using constant time (O(1))

[philip1999]

I have a function to calculate the length of the list. But this is in linear time. How could I convert this to constant time (O(1))

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

with

Node *front;
 Node *back;

This is function to calculate the length of the linked list

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

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

    return n;
}

[kbw]

How could I convert this to constant time (O(1))

You can't. You have to maintain the length as a separate variable.

[jonnin]

if your underlying list storage used a vector instead of pointers, you could extract it from that as well. there are pros and cons to such a simulated list, so this isn't always worth doing.

[philip1999]

@kbw, But, I was asked to make modifications to the above function to make that to constant time.

[Duthomhas]

With your current Node structure it is entirely possible to make calculating the length a constant time operation, at the cost of increased complexity for insertion and delete.

A better choice would be to maintain a specific Head object that keeps the length of the list as a member variable, in addition to the first Node pointer. Then when you pass the Head object around (which I would actually name “List”), you can get the length.

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

template <typename T>
struct List
{
  int   size;
  Node* head;
};

Now whenever you insert or delete nodes, you must also adjust the size in the head object.

BTW, there is no point in maintaining a Node* back for a singly-linked list. (See ne555’s comment following)

Hope this helps.

[ne555]

> BTW, there is no point in maintaining a Node* back for a singly-linked list.
push_back() in O(1)

[Duthomhas]

Oh, duh. Thanks. Fixed.