Contiguous list merits and static implementation

A contiguous list stores its elements in adjacent memory locations (an array plus a count of used positions).

Merits

• Direct (random) access: the i-th element is found in O(1) using its index, address = base + i × size.
• Simple: easy to declare, understand and program.
• No extra memory for pointers: only data is stored, so each element needs less memory than a linked node.
• Fast traversal and searching/sorting support: good cache behaviour; binary search is possible on a sorted array.
• Suitable when the maximum size is known and few insertions/deletions occur.

Demerits

• Fixed size: overflow if the list grows beyond MAX; memory wasted if it stays small.
• Slow insertion and deletion: elements must be shifted, O(n).
• Needs a contiguous block of memory.
• Resizing at run time is costly (allocate new array, copy all).
• Deleted positions are not reused automatically unless shifting is done.

Static implementation of a list

In static implementation, the array is declared with a fixed size at compile time and n counts the elements in use.

 #define MAX 100
 int list[MAX];  int n = 0;

 element:  list[0] ... list[n-1]  used
           list[n] ... list[MAX-1] free

Algorithm to insert item X at position K (0 ≤ K ≤ n):

1. If n == MAX, print "overflow" and stop.
2. For i = n-1 down to K: list[i+1] = list[i].
3. list[K] = X; n = n + 1.

Algorithm to delete the element at position K:

1. If n == 0 or K ≥ n, print "underflow/invalid" and stop.
2. For i = K to n-2: list[i] = list[i+1].
3. n = n - 1.

Traversal runs i from 0 to n-1. Memory for the whole array exists from the start of the program until it ends, which is why it is called static.