Length of an SLIst ?

[Justin Whear]

On Mon, 02 Apr 2012 23:10:40 +0200, 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.

Generally a singly-linked list is not a single container object, but a 
chain of nodes. Each node knows only of the existence of the next node, 
so operations such as insertion and deletion require just snapping a new 
node into the chain and are constant-time. By contrast, random-access 
operations require walking the chain to find the requested node. In many 
respects, slists and arrays are opposites, with one's weakness being the 
other's strength.