Array vs Linked List. Intro, Pros & Cons, Usage, etc.

Array

Possibly the most common data structure used to store data. One memory block is allocated for the entire array which holds all the initialized (and rest of the uninitialized) elements of the array. Indexing is 0-based and the elements can be accessed in a constant time by using the index of the particular element a as the subscript.

Why constant time for accessing array elements? - The address of an element is computed as an offset from the base address of the array and one multiplication is needed to compute what is supposed to be added to the base address to get the memory address of the element. Since memory requirements for every data type is different, so first the size of an element of that data type is computed and then it's multiplied with the index of the element to get the value to be added to the base address. So, the process requires just one multiplication and one addition and this is required for every element irrespective of its position in the array. Hence access is faster and requires a constant time.

Advantages of using arrays:

• Easier to use and access
• Faster access to the elements

Disadvantages of using arrays:

• Fixed size - the size of the array is static
• One block allocation - if you don't have enough memory to provide a single block (but you have sufficient scattered memory blocks) to allocate the space for the array then you'll need to defragment and other similar stuff to first create a free block of that size. So you may like to term it as improper utilization of memory :-)
• Complex position-based insertion - if you want to insert an element at a position already covered by some other element then you got to shift right by one position all the elements to the right of that position. This will vacate the position for you to insert the new element at the desired position. The more elements you have to the right of the desired position, the more expensive the process will be :-)

Linked List

Elements are not stored in contiguous memory locations, not at least guaranteed to be stored like that :-) Every node contains an element and a link to the next element. The allocation is not static instead it's dynamic. Whenever a need arises, you got to first allocate memory for the node (Using malloc() in C/C++. In Java it'll be like any other object creation) and then use it to store the new element and link either as 'null' (in case it's the last element) or the link will store the address of the element, which is supposed to be next to the element being added. Since the memory is allocated dynamically, so it'll continue to exist unless you will need to explicitly kill it in the languages not having automatic memory management (Using free() in C/C++. Java enjoys the facilities of the garbage collector).

Node definition in C/C++: we assume that elements are of type 'int'

struct node {
int element;
struct node * link;
};

In Java it is even simpler, so I'm skipping that here.

Advantages of using Linked Lists:

• Flexibility - insert at (or delete from) any position in contant time
• No single allocation of memory needed - fragmented memory can be put to a better use
• Dynamic allocation - the size is not required to be known in advance

Disadvantages of using Linked Lists:

• Complex to use and access - relatively complex as compared to arrays
• No constant time access to the elements - simply because it doesn't involve the simple arithmetic used by arrays to compute the memory address, so relatively inefficient as compared to arrays

When to use what?

The interesting fact about Linked List is that it's normally used as a complimentary solution to handle the disadvantages of arrays. Arrays certainly have their own advantages and they're still used more widely, but Linked Lists has provided an efficient and effective alternative to arrays in the cases where you're bothered by the limitations of the arrays. So, you may see both arrays and linked lists as complimentary to each other and not as rivals. Choice is based mainly on the context you're planning to use any of the two data structures.