Necessary and Sufficient

Question: Explain the differences between arrays and linked lists.

Answer: There are several differences which all stem from how the 2 data structures allocate memory.

An array is a linear data structure which allocates a contiguous block of memory on the heap returning a pointer to the start of this block (the base address). Because the compiler needs to know how much memory to allocate they are often fixed in size although some languages offer re-sizing functions which results in a new but bigger contiguous block of memory being allocated and the original data being copied to the new block. Arrays offer direct element addressing using the [] operator and this addressing is extremely fast because the program applies a formula as follows (for zero-based arrays):

A linked list is also a linear data structure but it overlays a structure on top of a collection of homogeneous data items. In a singularly-linked list the structure that encompasses each node/element of a linked list has a pointer/reference to the next element in the sequence. In a doubly-linked list there is also a pointer/reference to the previous element in the sequence. In marked contrast to arrays, the structure of linked lists allows a logical ordering of the elements to be defined which is different to the physical ordering. Furthermore, because the elements need not be contiguous in memory linked lists do not need to be fully provisioned up-front and can easily grow dynamically.

The disadvantage of linked lists is that, unlike arrays, you cannot directly address the i-th element. This is because of the non-contiguous use of memory.