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