Speed of changing memory addresses

Question

I guess the best way to explain this question is by iterating over a linked list vs array.

Given an array and linked list of size n purely based on time it takes to move to a different memory address would iterating through an array be any faster than iterating through a linked list. As arrays are a continuous block of memory and linked lists contain pointers to other spots in memory, would an array be any faster? If it was a large enough amount of memory would there be any noticeable difference in speed?

Thanks for any input!

Such an open ended question - considering CPU/Memory/OS/What else is running.... — Ed Heal, Nov 01 '14 at 18:10
In general it's likely iterating over an array would be faster since it's a more 'cache friendly' operation. — hatchet - done with SOverflow, Nov 01 '14 at 18:18
possible duplicate of [Array versus linked-list](http://stackoverflow.com/questions/166884/array-versus-linked-list) and also http://stackoverflow.com/questions/19064384/arrays-vs-linked-lists-in-terms-of-locality — hatchet - done with SOverflow, Nov 01 '14 at 18:18

score 2 · Accepted Answer · answered Nov 01 '14 at 18:19

An array would be faster. Think about it like this, for a linked list you need to find element i you need to look into each node and find the pointer to move to the next element. While for an array we simply need to shift in memory (based on the datatype), and it most cases for most CPU's shifting is a fast operation, faster than looking into a pointer and moving to it's location.

Also more importantly is that for an array the next elements can be found in parallel, we don't need to know what i-1 was to find element i. But for an linked list you need to know the last element to find the next one. And when you do iterate through an array (if you have a good cache memory) it could move the next elements into cache for faster access. Mostly for iteration cache is likely to be stored and used. For a linked list you could not predict the next items to place into cache memory as well, because it can be random.

Speed of changing memory addresses

1 Answers1