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

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

Rudolfs Bundulis
commented

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

Rudolfs Bundulis
commented

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

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.

sfrehse
posted this

## Have an answer?

JD

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) ?