Pieter de Goeje
pieter at degoeje.nl
Fri Apr 23 18:21:52 UTC 2010
On Friday 23 April 2010 17:40:12 Joerg Sonnenberger wrote:
> On Fri, Apr 23, 2010 at 06:18:46PM +0300, Eitan Adler wrote:
> > > - use a matrix is faster than use a linked list?
> > For what?
> > For insertion and deletion no - linked list is faster. For sequential
> > access they are the same speed (forgetting look-ahead caching). For
> > random access matrix is faster.
> Actually -- it depends. Removing the tail and inserting at tail is
> amortised constant time for arrays if done using the double-on-full
> trick. In that case, array can be the faster datastructure too.
Random deletes can be made O(1) if you don't care about the order of the
elements in an array.
More information about the freebsd-hackers