Skip to main content

Array list; static or dynamic choice

Short answer

Array implementation stores elements in consecutive locations with a count n, giving O(1) access and O(n) insert/delete due to shifting. Choose static when maximum size is known and random access is important; choose dynamic linked list when size varies and many insertions/deletions occur.

Explain array implementation of list. State the reason why would you choose either static implementation or dynamic implementation for list.

Array implementation of a list

A list is a linear sequence of elements. In array (static) implementation the elements occupy consecutive locations of an array LA[0..MAX-1], and an integer n counts the elements in use. The position of an element gives the order.

index:   0    1    2    3    4 ...  MAX-1
       | 10 | 20 | 30 | 40 |    | ...  |      n = 4
  • Access to the i-th element: LA[i], O(1).
  • Insert at k: shift LA[k..n-1] right, store item, n++. O(n).
  • Delete at k: shift LA[k+1..n-1] left, n--. O(n).
  • Overflow when n == MAX; underflow when n == 0.
#define MAX 100
int la[MAX], n = 0;
void insert(int k, int item) {          /* 0 <= k <= n */
    if (n == MAX) { printf("Overflow\n"); return; }
    for (int j = n - 1; j >= k; j--) la[j + 1] = la[j];
    la[k] = item;  n++;
}

Choosing static or dynamic implementation

Choose static (array) whenChoose dynamic (linked list) when
Maximum size is known in advanceSize is unknown or varies a lot
Fast random access is neededAccess is mostly sequential
Few insertions/deletions in the middleMany insertions/deletions
Memory per element must be small (no pointers)Extra pointer memory is acceptable
Simple code is preferredFlexible memory use is preferred

For example, a list of the 12 months is best kept in an array (fixed size, indexed access), while a waiting list of customers whose number changes constantly is best kept as a linked list.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 3 questions →