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

1784 views c++
5

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;
}

answered question

The question is a bit vague. What are the restrictions? Why can't you store the length internally and update it on adding/removing nodes and the length function could just return it (making it constant) ?

@RudolfsBundulis So, I need to increment when ever the node is added and decrement whenever the node is deleted?

yep :) That would be the easiest given there are no restrictions that disallow this.

@RudolfsBundulis The restrictions are that I just need to modify my function

Ok you really seem confused. Can you add a size field to your list structure? If so, you can just modify the length function to return that field.

1 Answer

6

You can do some bookkeeping while adding or removing nodes. However, you will need a data structure that keeps all those things. Please find under What is the time complexity of a size() call on a LinkedList in Java? related question.

posted this

Have an answer?

JD

Please login first before posting an answer.