Static and Dynamic list data structure

Static list

One way to implement a list is by using a static array and hence  called static List. The elements of the list are stored in contiguous locations in the array. Thus, each element of the list can be directly accessed using the position in the array and the whole list can be traversed very easily as shown below:

The array implementation of list is quite simple; however, there are certain problems associated with it which are as follows:-

• Since array elements are stored contiguously in memory, a sufficient block of memory need to be allocated to array at a compile-time and once the memory is allocated it cannot be expanded or contracted. For this reason, array is referred to as static data structure. 
• if the number of elements in the list decrease or increase significantly at run-time, it may lead to significant wastage of memory or short of memory respectively. 
• Another problem is that the insertion (except the insertion at the end) and deletion of an element are expensive operations, since they may require a number of elements to be shifted to either make space for new elements or to cover the gap created by deleting the elements. 

Dynamic List structure

The above mentioned limitations of static list can be solved by dynamic list structure called Linked List.

In this implementation, the successive elements of the list are linked by means of pointer or link, therefore named as linked list. This implementation frees the programmer from the constraint of using contiguous memory to store the list. Moreover, the memory is dynamically allocated at run-time. Therefore, linked list are referred to as dynamic data structures. Also, there is no upper limit on the size of the linked list and new nodes can be inserted into it as far as memory is available. In addition, the insertion or deletion of elements does not require shifting of the existing elements as in case of array implementation; elements can be inserted or deleted merely by adjusting the pointers. However, one disadvantage associated with linked implementation is the extra space required for storing the pointers.

Formally, a linked list can be defined as a linear collection of homogeneous elements called nodes. The successive nodes of the linked list are stored non-contiguously and linear order between nodes is maintained by means of a pointer. Each node consists of two or more parts. One part essentially stores an element of the list and the other part stores a pointer to the node containing the previous element, next element or both.