Amazon Interview Question Software Engineer / Developers
The advantage of continous memory is that the memory is assigned during compile time and hence we do not hold risk of running out of memory during run time coz its already there. where as in case of link list, every node is created on need basis and a chance may come where we run out of memory and no more nodes are created and the program execution halts.
A few reasons why contiguous memory are better is because
1) You have random access.
2) Better locality - Whenever the OS brings data into memory, it loads a whole page. Less page fault. With linked list, different parts of the linked list are stored at different parts of memory.
Branch Prediction doesn't work as well with linked list. This causes the pipeline to be flushed more often which result in poor performance.
Arrays often have fixed size.. could be two dimensional where as Link List always points to another node There are types of Link List like Circular, etc..
- OldGuru April 20, 2007