Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
The space-time complexity of getting the size of the linked list can differ in different implementations as far as I understand it.
In the Boost C++ library one finds that the size() function can be constant time or linear time.
I was wondering what the differences are in getting the size to be constant time over getting it to be linear?
Can anyone elaborate on the algorithm differences?
The key difference is that you have a field tracking the size of the list. This field can be accessed in constant time. The field must be updated for every addition or removal. If you compute the size of the list by counting the elements, then it will be linear.
It is common to implement lists using arrays for obvious reasons (random access). If you have an implementation that extends the array by a constant number of fields $k$ every time it is full, you can achieve constant time for figuring out the number of elements without having additional information stored.
Execute a linear search for $A[A.length - k - 1]$ to $A[A.length - 1]$. By data structure invariants you know that the list's end has to be in this interval; hence you can simply calculate the total number of elements. This only works if you also decrease your array, of course, or consider szenarios where only adding occurs.
Since you have to consider at worst $k$ elements, you are in $\mathcal{O}(k) = \mathcal{O}(1)$. This does obviously only work if you can identified unused indices (e.g. by null references).
Of course an expected runtime of $\frac{k}{2}$ is worse than $1$ (for $k>2$).
Disclaimer: I am sure most people would opt for the additional variable when implementing lists. I just wanted to point out an additional possibility that is equivalent in terms of rough worst-case bounds.
