0
$\begingroup$

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?

Improve this question
$\endgroup$
  • 3
    $\begingroup$ Sounds like a question for StackOverflow. If the list stores its length, clearly this can be accessed in constant time; otherwise the list has to be traversed to count the number of elements. $\endgroup$ – András Salamon Oct 7 '10 at 10:20
  • 2
    $\begingroup$ This is exactly a homework question from a first-year programming class that I TA'ed last spring... $\endgroup$ – Daniel Apon Oct 7 '10 at 15:20
  • 2
    $\begingroup$ @Raphael: In my opinion, that is not the purpose of this website. $\endgroup$ – Tsuyoshi Ito Oct 7 '10 at 16:10
  • 1
    $\begingroup$ @Raphael: I suggest you read this: meta.cstheory.stackexchange.com/questions/316/…. The issue is not what could be useful. The issue is whether it is within the scope of this site. $\endgroup$ – Aryabhata Oct 7 '10 at 16:39
  • 2
    $\begingroup$ @Raphael: The main reason this site was even created was to cater to Research Level CS questions (like MathOverflow). This was never meant to be an all encompassing CS site and IMO, it is a good thing that there is a lower bound on the kind of questions that can be asked here. Not having a lower bound will lead to lot of noise and would likely drive the experts away. In any case, IMO, this particular question is more on-topic for a SW Engineering site (like stackoverflow) than for a research level theoretical CS site. You are free to take it up on Meta though. $\endgroup$ – Aryabhata Oct 7 '10 at 18:39
4
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ Note that redundant data (i.e. the item count as variable) is inherently dangerous. If you do not keep it consistent properly, bad things happen. This is a usual tradeoff: complexity versus performance. In case of a linked list it is simple, obviously. $\endgroup$ – Raphael Oct 7 '10 at 10:56
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • 1
    $\begingroup$ For this to work the domain of elements must set aside a special value for marking unoccupied elements. So this isn't free in terms of space unless the domain is pointer-valued, in which case NULL can be enlisted. For example, if the domain is 32-bit integers and you have a fully occupied array of length 2^16 then the amount of slack has the same information content as a 16-bit integer. You can see that the bit slack scales with length. You could achieve comparable space efficiency scaling with a separate variable-length encoding of the size based on a Golomb code. $\endgroup$ – Per Vognsen Oct 7 '10 at 11:42
  • $\begingroup$ I need a special value, yes; I said as much above. I fail to understand what you mean by "slack"; yes, I shrink my domain, but no, I do not waste space in the list. That is, not more than any (sensible) array-based list implementation would. $\endgroup$ – Raphael Oct 7 '10 at 13:07

Not the answer you're looking for? Browse other questions tagged or ask your own question.