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. -- http://mail.python.org/mailman/listinfo/python-list
