On 04/02/2012 02:10 PM, Andrej Mitrovic wrote: > On 4/2/12, Justin Whear<jus...@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
