Static and dynamic data structures; array list

Static and dynamic data structures

A static data structure has a fixed size decided at compile time. Memory is allocated once and cannot grow or shrink at run time. Example: an array int a[100];.

A dynamic data structure can change its size during execution; memory is requested (malloc) and released (free) as needed. Examples: linked list, dynamic stack/queue, tree.

Array implementation of a list

The elements of the list are stored in consecutive locations of an array, and a variable n (or last) records how many elements are present. The i-th element is list[i], so the order of elements is given by the physical order in memory.

 list[]   10  20  30  40   _   _      MAX = 6
 index     0   1   2   3   4   5      n = 4

• Insert at k: if n = MAX report overflow; else shift list[k..n-1] one place right, put the item at list[k], n = n + 1.
• Delete at k: if n = 0 report underflow; else shift list[k+1..n-1] one place left, n = n - 1.

int insert(int list[], int *n, int k, int x) {
    if (*n == MAX) return 0;
    for (int i = *n - 1; i >= k; i--) list[i + 1] = list[i];
    list[k] = x; (*n)++;
    return 1;
}

Limitations

1. Size is fixed; the list cannot grow beyond MAX (overflow), and a big array wastes memory if only few items are stored.
2. Insertion and deletion in the middle need shifting of many elements: O(n) time.
3. The array must occupy one contiguous block, which may not be available.
4. Size cannot be changed at run time; resizing means allocating a new array and copying.
5. Elements of different types cannot be mixed, and deleted slots stay reserved.