Arrays as a data structure: the ADT idea; address calculation (row-major, column-major, non-zero lower bounds); cost of insert, delete and search

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• What is the order of growth of two nested loops each running n times? from Lesson 2.2
• How many moves does Tower of Hanoi need for n disks? from Lesson 2.1.3
• In int a[R][C] starting at B (4-byte ints), where is a[i][j]? from Lesson 1.5.2

1 · The Hook

🎣

A library catalogue promises three things: you can look up a book, add a book, and remove a book. Whether the catalogue is a card box, a register or a computer file, readers only care about those promises and how fast they are kept. Thinking about what a container does separately from how it is built is the starting idea of every structure in this phase.

2 · Predict First

🤔

An array holds 1000 numbers in order. Inserting a new number at position 0 (keeping the order) needs how many element moves? Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

1000. Every existing element must shift one place right to make room. Reading any element is instant, but inserting near the front is expensive.

Abstract data types

An abstract data type (ADT) is a description of a kind of data by its operations and their behaviour, not by its layout in memory. A data structure is a concrete way of storing data in memory that implements an ADT. The same ADT can have several implementations with different costs; that choice is what this phase is about.

The array as a structure

An array stores n elements in consecutive memory. Its strengths and weaknesses:

int a[10] = {10, 20, 30, 40, 50};
int n = 5, pos = 1, x = 15, i, shifts = 0;
for (i = n; i > pos; i--) {      /* move the tail one place right */
    a[i] = a[i - 1];
    shifts++;
}
a[pos] = x;
n++;
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("| shifts = %d\n", shifts);

Output

10 15 20 30 40 50 | shifts = 4

Binary search

In a sorted array, compare the key with the middle element and discard the half that cannot contain it. At most ⌊log₂ n⌋ + 1 probes (the guessing game of Lesson 0.2.1).

int a[7] = {1, 3, 5, 7, 9, 11, 13};
int lo = 0, hi = 6, mid = -1, key = 11, probes = 0, found = 0;
while (lo <= hi) {
    mid = (lo + hi) / 2;
    probes++;
    if (a[mid] == key) { found = 1; break; }
    if (a[mid] < key) lo = mid + 1;
    else hi = mid - 1;
}
printf("found=%d at %d after %d probes\n", found, mid, probes);

Output

found=1 at 5 after 2 probes

Address calculation with any lower bounds

Arrays in questions may start at indices other than 0, written A[l₁ … u₁][l₂ … u₂]. Let n₁ = u₁ − l₁ + 1 rows and n₂ = u₂ − l₂ + 1 columns, element size w, base address B (the address of the first element).

Three dimensions, row-major, A[n₁][n₂][n₃] from 0: B + (i·n₂·n₃ + j·n₃ + k)·w.

4 · Visual

A[1..3][1..4] stored two ways (cells show i,j):

row-major:     [1,1][1,2][1,3][1,4] [2,1][2,2][2,3][2,4] [3,1][3,2][3,3][3,4]
column-major:  [1,1][2,1][3,1] [1,2][2,2][3,2] [1,3][2,3][3,3] [1,4][2,4][3,4]

Insert 15 at position 1 of [10 20 30 40 50 _]:
  shift 50, 40, 30, 20 right  ->  [10 _ 20 30 40 50]  ->  [10 15 20 30 40 50]   (4 moves)

The same table can be laid out row by row or column by column; insertion pays for the shifting.

After inserting 15 at index 1: four elements moved one place right.

5 · Worked Examples

Example 1 Easy

int A[1..10][1..20] is stored row-major from 1000, with 4-byte ints. Find the address of A[5][6].

Solution

n₂ = 20. Offset = ((5 − 1)·20 + (6 − 1))·4 = (80 + 5)·4 = 340 → 1340.

Example 2 Medium

The same array stored column-major (n₁ = 10 rows). Where is A[5][6]? And short X[−2 … 4][3 … 8] (2 bytes), row-major from 2000: where is X[1][5]?

Solution

Column-major: ((6 − 1)·10 + (5 − 1))·4 = 54 × 4 = 216 → 1216. For X: n₂ = 8 − 3 + 1 = 6; ((1 − (−2))·6 + (5 − 3))·2 = (18 + 2)·2 = 40 → 2040.

Example 3 GATE

int T[3][4][5] (4-byte ints, indices from 0) is stored row-major from 500. Find the address of T[2][1][3]. How many element moves does deleting index 2 of a 6-element array need?

Solution

(2·4·5 + 1·5 + 3)·4 = (40 + 5 + 3)·4 = 192 → 692. Deleting index 2 of 6 elements shifts indices 3, 4, 5 left: 3 moves.

int a[6] = {10, 15, 20, 30, 40, 50};
int n = 6, pos = 2, i;
for (i = pos; i < n - 1; i++)      /* close the gap */
    a[i] = a[i + 1];
n--;
for (i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n");

Output

10 15 30 40 50

6 · GATE Traps

⚠️

• Subtract the lower bounds first: with indices from 1, A[1][1] is the base address.
• Row-major multiplies the row offset by the number of columns; column-major multiplies the column offset by the number of rows.
• Number of elements in l … u is u − l + 1.
• Binary search needs a sorted array.
• Insertion and deletion cost depends on the position: near the end is cheap, near the front is O(n).

8 · Memory Hook

🧠

“Arrays read fast and move slowly.” Any seat is found instantly by its number, but squeezing a new person into row 1 makes everybody behind shuffle one seat along.

9 · Connect the Dots

Lesson 1.5.2 gave row-major addressing for C arrays; this lesson added lower bounds, column-major order, and the costs of operations. Many problems only ever need the most recently added item, like plates in a canteen. Next lesson answers: what is the structure that only lets you add and remove at one end, and how is it built on an array?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT2 marksRow-major

int A[0..9][0..14] (4-byte ints) is row-major from 2000. What is the address of A[6][7]?

Numerical answer: ________

Q2NAT2 marksColumn-major

double D[0..4][0..9] (8 bytes) is column-major from 100. What is the address of D[3][4]?

Numerical answer: ________

Q3MCQ1 markCosts

Which operation on an unsorted array of n elements takes O(1) time?

• (A) read the element at index i
• (B) insert at index 0
• (C) search for a value
• (D) delete at index 0

Q4MCQ1 markADT

An abstract data type specifies:

• (A) the address of the first element
• (B) the memory layout
• (C) the programming language
• (D) the operations and their behaviour

Q5MCQ1 markOutput

What does this print?

int a[7] = {1, 3, 5, 7, 9, 11, 13};
int lo = 0, hi = 6, mid = -1, key = 11, probes = 0, found = 0;
while (lo <= hi) {
    mid = (lo + hi) / 2;
    probes++;
    if (a[mid] == key) { found = 1; break; }
    if (a[mid] < key) lo = mid + 1;
    else hi = mid - 1;
}
printf("found=%d at %d after %d probes\n", found, mid, probes);

• (A) found=1 at 5 after 6 probes
• (B) found=1 at 3 after 1 probes
• (C) found=1 at 5 after 2 probes
• (D) found=0 at 6 after 3 probes

11 · Rule Card

• ADT = operations + behaviour; data structure = an implementation.
• Array: access O(1); insert/delete at p O(n − p); search O(n), sorted O(log n).
• Row-major: B + ((i − l₁)·n₂ + (j − l₂))·w; column-major: B + ((j − l₂)·n₁ + (i − l₁))·w.
• nₖ = uₖ − lₖ + 1; 3-D row-major: B + (i·n₂n₃ + j·n₃ + k)·w (from 0).
• Binary search: sorted only; ⌊log₂ n⌋ + 1 probes.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

abstract data type (ADT)data structureinsertion / deletion by shiftingbinary searchcolumn-major ordernon-zero lower bounds

13 · Answer Vault