Array Basics and Operations: Concepts, Worked Examples and Exam Traps

Understand array indices, size, capacity and operation costs through a single worked array. Then practise insertion, deletion, search and address calculation without off-by-one errors.

KnowledgeGate Team

Exam prep & CS education

Updated 1 Nov 20265 min read
Array Basics and Operations: Concepts, Worked Examples and Exam Traps

An array looks simple, but exam errors come from confusing an index with a value, logical size with capacity, or an O(1) lookup with an O(n) insertion. A zero-based array model links direct access, insertion, deletion and boundary checks.

Array basics: slots, indices, size and capacity

A one-dimensional array has indexed slots holding elements of one declared type. In this C-like model, logical size n gives valid indices 0 through n - 1.

Take this running state:

A = [12, 7, 25, 9, 18, _, _, _]

Here C = 8, but n = 5. Only indices 0 through 4 are logical elements. Indices 5 through 7 are allocated but unused.

Reading A[5] is therefore invalid. A valid end insertion may write there because capacity remains.

Contiguous storage enables direct address calculation. Languages may add bounds checks or array-object behaviour, but the same indexed model helps. See CS Fundamentals for the wider programming foundation.

What each basic array operation actually costs

Complexity follows from the work performed:

Operation

Typical or worst-case cost

Why

Access or update by valid index

O(1)

Calculate one address and read or write one slot

Traverse all logical elements

O(n)

Visit n slots

Search an unsorted array

O(n)

The target may be last or absent

Insert at an arbitrary position

O(n) worst case

Shift later elements right

Delete at an arbitrary position

O(n) worst case

Shift later elements left

Inserting at index n can take O(1) when capacity exists because nothing shifts. Deleting index n - 1 can also take O(1). Arbitrary insertion or deletion remains O(n) worst case.

A growable container may allocate new storage and copy elements, so an append that triggers resizing is not an O(1) individual operation.

Start with A = [12, 7, 25, 9, 18, _, _, _], n = 5, C = 8.

Insert 16 at index 2, moving right to left:

  1. Move 18 from index 4 to index 5.

  2. Move 9 from index 3 to index 4.

  3. Move 25 from index 2 to index 3.

  4. Write 16 at index 2 and set n = 6.

Result: [12, 7, 16, 25, 9, 18, _, _], with three shifts and one inserted write.

Delete index 4, whose value is 9. Move 18 from index 5 to 4, then reduce n to 5. Within capacity the result is [12, 7, 16, 25, 18, _, _, _]. This used one shift.

Searching left to right for 25 succeeds at index 3 after four comparisons. Searching for 11 fails after five. The successful result is index 3, not value 25.

The array diagram shows insertion of 16 at index 2 and deletion of 9 at index 4, with capacity 8 and final logical size 5.

The operation loops and their invariants

For insertion, require 0 <= pos <= n and n < C.

Code
for i from n down to pos + 1:
    A[i] = A[i - 1]
A[pos] = value
n = n + 1

Right-to-left movement preserves unread elements. The opposite direction would overwrite 25 before moving it.

For deletion, require 0 <= pos < n. Save A[pos] first if needed.

Code
for i from pos through n - 2:
    A[i] = A[i + 1]
n = n - 1

Left-to-right movement lets each next element fill the gap.

Traversing [12, 7, 16, 25, 18] gives running sums 12, 19, 35, 60, 78, total 78, and maximum 25.

Direct access and address calculation

With lower bound L and element width w bytes:

LOC(A[k]) = base + (k - L) * w

For a C-style int A[8] with base = 1000, L = 0 and w = 4:

  • LOC(A[2]) = 1000 + (2 - 0) * 4 = 1000 + 8 = 1008

  • LOC(A[6]) = 1000 + (6 - 0) * 4 = 1000 + 24 = 1024

For one-based B[1..8], base 500 and width 2:

LOC(B[5]) = 500 + (5 - 1) * 2 = 500 + 8 = 508

Subtracting the lower bound keeps both cases consistent. Address 1024 is allocated, but index 6 is not logical when n = 5.

Use Array Basics in C: Indexing, Memory Layout and Worked Exam Traces for declaration, initialization, sizeof and mutation traces. The address calculation above answers a different question: an allocated slot can still sit outside logical size. Pointers in C: Memory Diagrams develops the next layer of pointer arithmetic.

The contiguous memory strip shows base address 1000, four-byte cells, and LOC(A[6]) computed as 1024 outside logical size 5.

Common array traps and how to repair them

  • Indices 0..n: use 0..n-1.

  • Size versus capacity: n = 5 elements, C = 8 slots.

  • Insertion shifting left: move right to left to preserve unread values.

  • Deletion shifting right: move left to right to close the gap.

  • Value instead of position: searching for 25 returns index 3.

Index 5 may receive a new end element during insertion, but cannot be read as current beforehand. After deletion, the last logical element is A[4] = 18.

Access is O(1) because address calculation uses constant work, not because the array is small. Unsorted search is O(n). The example insertion moved three elements even though its final write was constant time.

How exams test array basics and operations

Start with [4, 8, 15, 16, 23] and delete index 1. Moving 15, 16 and 23 left gives [4, 15, 16, 23], with three shifts.

Insert 9 at index 3. Move 23 to index 4, write 9, and get [4, 15, 16, 9, 23], with one shift. Therefore:

A[2] + A[4] = 16 + 23 = 39

Questions may ask you to trace code, select a valid range, count shifts, calculate an address, identify complexity, or spot an invalid access. Write n, index labels and loop direction first.

The short version and the next practice step

Remember five ideas:

  1. Indices identify positions, not values.

  2. Logical size may be smaller than allocated capacity.

  3. Address arithmetic makes valid indexed access O(1).

  4. Middle insertion and deletion require shifts.

  5. Every loop needs an explicit valid-index invariant.

For a 15-minute drill, take capacity 7 with [6, 10, 14, 18, _, _, _]. Insert 12 at index 2, delete index 4, then search for 18. Record each array, n and every shift.

Repeat the 15-minute drill above, test each boundary case, then use Zero to Hero for a broader CS path or the C Language course for direct array practice.