Length of an SLIst ?

[Ali Çehreli]

On 04/02/2012 02:10 PM, Andrej Mitrovic 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.

Length is not a property of singly-linked lists partly because they are 
supposed to be very light weight data structures. Imagine a hash table 
with buckets based on singly-linked lists. The length property would not 
add any value there but would double the table size.

I remember Matt Austern's presentation on a C++ singly linked list 
implementation where he had explicitly mentioned that he had decided to 
not provide length for the same reason. (I vaguely remember that his 
implementation was for addition to the C++ library, perhaps only to 
support the hash table? I don't remember now.)

Ali