[prev in list] [next in list] [prev in thread] [next in thread] 

List:       freebsd-hackers
Subject:    Re: c question
From:       Pieter de Goeje <pieter () degoeje ! nl>
Date:       2010-04-23 18:21:25
Message-ID: 201004232021.26160.pieter () degoeje ! nl
[Download RAW message or body]

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.

- Pieter
_______________________________________________
freebsd-hackers@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/freebsd-hackers
To unsubscribe, send any mail to "freebsd-hackers-unsubscribe@freebsd.org"
[prev in list] [next in list] [prev in thread] [next in thread]