CODEWITHSUNDEEP
pythonarrayspython-3.xlist
Dheeraj Chelaramani
Dheeraj Chelaramani

Reputation: 81

Reason Behind O(1) in finding the length of List in python

I was going through https://wiki.python.org/moin/TimeComplexity of Lists in python. I know python list internally works as an Array. But how internally length of list is O(1). As it needs to traverse till end of list and increment the counter and return it.

Thanks in Advance

Upvotes: 1

Views: 542

Answers (1)

DeepSpace
DeepSpace

Reputation: 81604

TL;DR lists keep track of their length.

In CPython, calling len([]) invokes the Py_SIZE C macro, which simply returns the value of the ob_size attribute.

https://github.com/python/cpython/blob/cda73a5af2ff064ca82140342b3158851d43868f/Objects/listobject.c#L438-L442

static Py_ssize_t
list_length(PyListObject *a)
{
    return Py_SIZE(a);
}

https://github.com/python/cpython/blob/9bdd2de84c1af55fbc006d3f892313623bd0195c/Include/object.h#L128

#define Py_SIZE(ob) (_PyVarObject_CAST(ob)->ob_size)

Upvotes: 5

Related Questions