Array implementation of list in C

Array implementation of a list

A list of elements is stored in consecutive cells of an array list[MAX]. A counter n tells how many cells are used, so valid elements are list[0] ... list[n-1]. Operations: insert at a position (shift right), delete from a position (shift left), traverse, search.

 before insert 25 at index 2        after
 [10][20][30][40][ ][ ]      ->     [10][20][25][30][40][ ]
   0   1   2   3  4  5               0   1   2   3   4  5

#include <stdio.h>
#define MAX 10

int list[MAX];          /* contiguous storage */
int n = 0;              /* number of elements currently in the list */

int insert(int pos, int x) {          /* pos = 0..n */
    if (n == MAX || pos < 0 || pos > n) return 0;   /* overflow / bad position */
    for (int i = n - 1; i >= pos; i--) list[i + 1] = list[i];  /* shift right */
    list[pos] = x;
    n++;
    return 1;
}

int delete_at(int pos) {              /* pos = 0..n-1 */
    if (n == 0 || pos < 0 || pos >= n) return 0;    /* underflow / bad position */
    for (int i = pos; i < n - 1; i++) list[i] = list[i + 1];   /* shift left */
    n--;
    return 1;
}

void traverse(void) {
    for (int i = 0; i < n; i++) printf("%d ", list[i]);
    printf("\n");
}

int main(void) {
    insert(0, 10); insert(1, 30); insert(1, 20);   /* 10 20 30 */
    traverse();
    delete_at(0);                                    /* 20 30 */
    traverse();
    return 0;
}

Output:

10 20 30
20 30

Limitations

1. Fixed size: MAX must be decided in advance. Too small gives overflow; too large wastes memory.
2. Costly insertion/deletion: shifting elements takes O(n) time.
3. Contiguous memory is required; a large array may fail to be allocated even if total free memory is enough.
4. Cannot grow or shrink at run time without allocating a new array and copying.
5. Poor for lists whose size changes frequently; a linked list is a better choice there.