Re: [Caml-list] ocamlgraph predecessors

[Jacques Garrigue <garrigue@math.nagoya-u.ac.jp>]

From: rixed@happyleptic.org
> > What you're asking is similar to the problem of finding the predecessor
> > of an arbitrary node in a singly-linked-list.  You have no option but to
> > scan the whole list to find its predecessor.  If you had a
> > doubly-linked-list, predecessor lookups would work easily, but that's a
> > different data structure, with much more overhead.
> 
> Much more overhead, really ?
> So this is for performance reasons that all functionnal languages
> promote singly-linked lists, while for instance in Linux every list
> is implemented with a doubly linked list for purely ideological reasons ?
> 
> :-)

Yes indeed, much more overhead. But the source is not the fact you
have to maintain backlinks, but their impact on the GC.
With a GC, any modification on existing values has a cost, since you
have to keep track of them independently of the value itself.
Since linux has no GC, using doubly linked lists has only a very
limited cost, mostly related to the extra space needed.
By the way, BSD uses lots of singly-linked lists, probably because it
comes from a time when there was not so much memory.

Jacques Garrigue