Hi, I had been thinking about this problem from quite sometime. Linked lists are good dynamic data structures and solve the main problems associated with arrays(static memory allocation)
On the other hand, one of the biggest disadvantages of linked lists is that their cache utilization is extremely poor. This results mainly from poor spatial locality because nodes of linked list are allocated in non-sequential memory locations. So when one accesses a node of linked list, a single cache line(fixed bunch of bytes) is fetched, and as the other nodes are present far in memory, the cache line most of the time will not contain other nodes. So every time a new node is accessed, the previous cache line has to be flushed and replaced by new cache line containing new node. This means on every access of node we pay the cost of reading data from main memory(which is very expensive) and bringing it into cache Main problem is that the poor cache utilization can sometimes result very bad extremely performance especially if the program is memory intensive (uses lot of heap memory) My question is that are their any other data structures which provide the benefits of linked lists (using dynamic memory allocation) but are as efficient as arrays in context of cache utilization? Thanks Varun -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
