c question

[Pieter de Goeje]

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