Length of an SLIst ?

[Steven Schveighoffer]

On Mon, 02 Apr 2012 17:10:40 -0400, Andrej Mitrovic  
<andrej.mitrovich at gmail.com> wrote:

> On 4/2/12, Justin Whear <justin at economicmodeling.com> wrote:
>> Classic singly-linked lists must be iterated to determine length
>
> I'm no algorithms buff, but I don't understand the benefit of not
> storing the length in the SList. What does it cost to maintain an
> extra variable? It's a single increment/decrement on each add/remove
> and a little bit of memory to store the count.

It all depends on how you model the data.  If the data is contained/owned  
by a single instance, then you can store the length inside that instance.   
If it's not owned (i.e. sublists are also valid SLists) then you cannot do  
that.

In terms of tradeoffs, generally you have to choose between O(1) splicing  
(i.e. removing the tail elements of a list, or splicing in another list in  
the middle) and O(1) length.

-Steve