Re: Offtopic: How to Design Programming Tests

[Michael Vanier <mvanier@bbb.caltech.edu>]

> From: Reini Urban <rurban@x-ray.at>
> 
> > > compare the advantages and disadvantages of arrays
> > > versus linked lists.
>  
> Noel Welsh:
> > This is a good question.  My answer would be:
> > - random access time O(1) vs O(n)
> > - queue/stack operations O(n) vs O(1)
> > - memory usage: array better
> > Anything I missed?
> 
> iteration: forward - lists slightly better, backwards - depends on the list :)
> 
> (is there actually any CPU which is faster or equally fast on indexed array 
> access than linked list iteration? assuming typical good languages and
> compilers)
> 

I would imagine that cache size and performance makes a huge difference
here.  Iterating through a linked list tends to lead to jumping around in
memory, thus (potentially) causing a lot of cache misses.  Arrays are less
subject to this.  Thus one might say that current CPU and memory technology
favor imperative languages which use arrays a lot :-(

Mike