https://[Log in to view URL]

Array: Arrays store elements in contiguous memory locations, resulting in easily
calculable addresses for the elements stored and this allows faster access to an
element at a specific index.

Linked List: Linked lists are less rigid in their storage structure and elements
are usually not stored in contiguous locations, hence they need to be stored with
additional tags giving a reference to the next element.

------------------------------------------------------------------------------------

Advantages of Linked Lists:
The size of the arrays is fixed: So we must know the upper limit on the number
of elements in advance. Also, generally, the allocated memory is equal to the 
upper limit irrespective of usage, and in practical uses, the upper limit is
rarely reached.

Inserting a new element in an array of elements is expensive because a room has
to be created for the new elements and to create a room existing elements have
to be shifted. 
Example: 

suppose we maintain a sorted list of IDs in an

array id[ ] = [1000, 1010, 1050, 2000, 2040, …..].

And if we want to insert a new ID 1005, then to maintain the sorted order,
we have to move all the elements after 1000 (excluding 1000). 
Deletion is also expensive with arrays unless some special techniques are used.
For example, to delete 1010 in id[], everything after 1010 has to be moved. 

So Linked list provides the following two advantages over arrays:

Dynamic size 
Ease of insertion/deletion 

------------------------------------------------------------------------------------

Disadvantages of Linked Lists:

Random access is not allowed. We have to access elements sequentially starting
from the first node. So we cannot do a binary search with linked lists. 

Extra memory space for a pointer is required for each element of the list. 

Arrays have a better cache locality that can make a pretty big difference 
in performance.

It takes a lot of time in traversing and changing the pointers.

It will be confusing when we work with pointers.

------------------------------------------------------------------------------------

Advantages of Arrays:

Arrays store multiple data of similar types with the same name.

It allows random access to elements.

As the array is of fixed size and stored in contiguous memory locations there is
no memory shortage or overflow.

It is helpful to store any type of data with a fixed size.

Since the elements in the array are stored at contiguous memory locations it is
easy to iterate in this data structure and unit time is required to access an 
element if the index is known.

------------------------------------------------------------------------------------

Disadvantages of Arrays:

The array is static in nature. Once the size of the array is declared then we 
can’t modify it.

Insertion and deletion operations are difficult in an array as elements are stored
in contiguous memory locations and the shifting operations are costly.

The number of elements that have to be stored in an array should be known in 
advance.

Wastage of memory is the main problem in the array. If the array size is big 
the less allocation of memory leads to wastage of memory.