Questions on Using Python to Teach Data Structures and Algorithms

[sturlamolden]

sturlamolden wrote:

> Remember that O(1) is not neccesarily faster than O(N)! Unless your
> linked list is very big, you will get something called a 'cache miss'
> inside your CPU. Thus it is usually more efficient to work with dynamic
> arrays.

This was a bit ackwardly formulated. What I was trying to say is that
linked lists produces cache misses rather often, whereas small dynamic
arrays do not. This is because linked lists are not contigous in
memory, in contrast to dynamic arrays. Thus, adding an element to a
dynamic array is in most cases faster, even tough you have to make a
copy the whole array. The same is true when you try do delete some
elements from a list. Small dynamic arrays are faster than linked
lists, because they can be kept in cache. Creating a new array in cache
is faster than tracing after pointers. It is only when dynamic arrays
are to large to fit in cache that linked lists perform better. But in
this case, something like Java's ArrayList is the preferred data
structure.

That is the reason only fools and DSA students use linked lists. They
are a nice teoretical cobnstruct, but not friendly to real-world
computer hardware. Perhaps they were the better option some time in the
past, when CPUs had much less cache and could only accomodate very
short arrays.