On Mon, 02 Apr 2012 17:10:40 -0400, Andrej Mitrovic
<andrej.mitrov...@gmail.com> 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.
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
