<p>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.</p>

CC BY-SA 2.5
2010-10-07T10:56:14.257Z
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.
Raphael
CC BY-SA 2.5
2010-10-07T10:21:52.733Z
2010-10-07T10:21:52.733Z
Dave Clarke
<p>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.</p>

<p>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.</p>

<p>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).</p>

<p>Of course an expected runtime of $\frac{k}{2}$ is worse than $1$ (for $k>2$).</p>

<p><em>Disclaimer</em>: 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.</p>

CC BY-SA 2.5
2010-10-07T11:42:23.943Z
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.
Per Vognsen
CC BY-SA 2.5
2010-10-07T13:07:46.767Z
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.
Raphael
CC BY-SA 2.5
2010-10-07T11:02:56.037Z
2010-10-07T11:02:56.037Z
Raphael
<p>The space-time complexity of getting the size of the linked list can differ in different implementations as far as I understand it.</p>

<p>In the Boost C++ library one finds that the size() function can be constant time or linear time.</p>

<p>I was wondering what the differences are in getting the size to be constant time over getting it to be linear?</p>

<p>Can anyone elaborate on the algorithm differences?</p>

CC BY-SA 2.5
2010-10-07T10:20:25.653Z
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.
András Salamon
CC BY-SA 2.5
2010-10-07T10:21:50.487Z
Wasn't too sure which Q&A site it belonged to...
Tony The Lion
CC BY-SA 2.5
2010-10-07T10:43:12.957Z
Question is too basic for this site!
Dai Le
CC BY-SA 2.5
2010-10-07T10:44:13.937Z
@András: Oops. I didn't see your answer when I wrote mine.
Dave Clarke
CC BY-SA 2.5
2010-10-07T15:20:14.310Z
This is exactly a homework question from a first-year programming class that I TA'ed last spring...
Daniel Apon
CC BY-SA 2.5
2010-10-07T15:42:19.230Z
Well, given the crude answers some teachers give to very basic questions we might all be in need of this kind of question although -- because! -- it _is_ very basic. One gets an answer, the other learns expressing his thoughts understandably, that is as clear as possible whithout oversimplifying.
Raphael
CC BY-SA 2.5
2010-10-07T16:10:36.397Z
@Raphael: In my opinion, that is not the purpose of this website.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-07T16:39:47.750Z
@Raphael: I suggest you read this: http://meta.cstheory.stackexchange.com/questions/316/is-cstheory-aimed-at-degree-level-masters-or-phd-students. The issue is not what could be useful. The issue is whether it is within the scope of this site.
Aryabhata
CC BY-SA 2.5
2010-10-07T18:25:34.267Z
I am aware of this but I am not sure wether I like it. And in the end, we define the scope, right? I just find the idea disturbing that people with simple (as in "from our point of view") questions cannot get answers here, where allegedly competent people are active. Were else can they go? I'd rather have a question like this here answered soundly on this site than roughly on some SW Engineer portal.
Raphael
CC BY-SA 2.5
2010-10-07T18:39:36.727Z
@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.
Aryabhata
CC BY-SA 2.5
2010-10-07T21:15:00.553Z
I can certainly understand the premise. Nobody wants to dig through two dozen homework questions every day to find two advanced questions. Maybe we can have a closely releated sister site, e.g. tcsnovice.stackexchange.com?
Raphael
CC BY-SA 2.5
2010-10-08T05:37:41.350Z
to be fair, a number of basic but not obvious algorithms questions get asked on SO, so that's a reasonable place for this. Raphael, I'd recommend you continue this discussion on the linked meta post if you'd like to expand the scope.
Suresh Venkat
CC BY-SA 2.5
2010-10-08T13:59:05.103Z
Did that. I am not talking only algorithms, though; http://cstheory.stackexchange.com/q/1977/1546 , for instance, _is_ a homework example but was accepted. Also, I do not think your usual programmer can perform an average case analysis properly, even in homework settings. But I do not know what people hang around SO, so maybe they can cover this.
Raphael
<time-complexity>
Linked List size in constant time or linear time
Tony The Lion
# Linked List size in constant time or linear time

(Asked by: username_0 on 2010-10-07)

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?

**Tags:** time-complexity
> **Comments:**
> **username_1**: 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.  
> **username_0**: Wasn't too sure which Q&A site it belonged to...  
> **username_2**: Question is too basic for this site!  
> **username_3**: @András: Oops. I didn't see your answer when I wrote mine.  
> **username_4**: This is exactly a homework question from a first-year programming class that I TA'ed last spring...  
> **username_5**: Well, given the crude answers some teachers give to very basic questions we might all be in need of this kind of question although -- because! -- it _is_ very basic. One gets an answer, the other learns expressing his thoughts understandably, that is as clear as possible whithout oversimplifying.  
> **username_6**: @Raphael: In my opinion, that is not the purpose of this website.  
> **username_7**: @Raphael: I suggest you read this: http://meta.cstheory.stackexchange.com/questions/316/is-cstheory-aimed-at-degree-level-masters-or-phd-students. The issue is not what could be useful. The issue is whether it is within the scope of this site.  
> **username_5**: I am aware of this but I am not sure wether I like it. And in the end, we define the scope, right? I just find the idea disturbing that people with simple (as in "from our point of view") questions cannot get answers here, where allegedly competent people are active. Were else can they go? I'd rather have a question like this here answered soundly on this site than roughly on some SW Engineer portal.  
> **username_7**: @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.  
> **username_5**: I can certainly understand the premise. Nobody wants to dig through two dozen homework questions every day to find two advanced questions. Maybe we can have a closely releated sister site, e.g. tcsnovice.stackexchange.com?  
> **username_8**: to be fair, a number of basic but not obvious algorithms questions get asked on SO, so that's a reasonable place for this. Raphael, I'd recommend you continue this discussion on the linked meta post if you'd like to expand the scope.  
> **username_5**: Did that. I am not talking only algorithms, though; http://cstheory.stackexchange.com/q/1977/1546 , for instance, _is_ a homework example but was accepted. Also, I do not think your usual programmer can perform an average case analysis properly, even in homework settings. But I do not know what people hang around SO, so maybe they can cover this.  

---

## 2 answers

### Answer by username_3 on 2010-10-07. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_5**: 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.  

---

### Answer by username_5 on 2010-10-07. Score: 1

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.

> **Comments:**
> **username_9**: 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.  
> **username_5**: 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.  

---

