Unit 2: Introduction to Array Concepts

I. Orientation — Linear Data Structures

A linear data structure organizes elements sequentially so that, except at the ends, each element has a predecessor and a successor. Arrays, stacks, and queues are linear structures, but they differ in memory organization and rules for accessing data.

• Element: A single stored value, such as 25 in an integer array.
• Index: An integer position used to access an array element; zero-based indexing numbers positions from 0 to n - 1.
• Capacity: The maximum number of elements that allocated storage can hold.
• Logical size: The number of elements currently stored; it may be smaller than the capacity.
• Contiguous storage: Array elements occupy consecutive memory locations.
• Abstract data type (ADT): A structure defined by its permitted values and operations; stacks and queues are ADTs that can be implemented using arrays.
• Complexity convention: Time and auxiliary space are expressed using Big-O notation, such as O(n), where n is the input size.

II. Arrays — Indexed Contiguous Storage

An array is a fixed-capacity collection of same-type elements stored contiguously and accessed by index. Direct indexing is fast, but inserting or deleting within the sequence may require shifting elements.

A. Definition and initialization of arrays

Array initialization allocates indexed storage and may assign initial values to its elements.

• Declaration: A declaration specifies the element type, name, and capacity; int A[5] reserves space for five integers in C-like notation.
• Initialization: Values may be supplied when the array is created.

A = [12, 7, 19, 4, 10]

• Index range: For an array of length n = 5, valid indices are 0 through 4; therefore, A[2] = 19.
• Homogeneity: A conventional array stores values of one declared type, so every element has the same storage size.
• Boundary rule: Accessing an index below 0 or at least n is out of bounds and may cause an error or undefined behavior, depending on the language.

B. Memory representation of one-dimensional arrays

A one-dimensional array maps each index to a memory address using a constant-size offset.

• Address formula:

Address(A[i]) = B + i × w

• Symbols:
  • A[i] is the element at zero-based index i.
  • B is the base address of A[0].
  • w is the number of bytes occupied by one element.
• Example: If B = 1000, w = 4 bytes, and i = 3, then Address(A[3]) = 1000 + 3 × 4 = 1012.
• Consequence: Because the address is calculated directly, indexed access takes O(1) time.
• Locality: Adjacent elements are close in memory, often improving cache performance during sequential processing.

C. Array traversal

Array traversal visits each logical element, usually from the first index to the last.

• Procedure:

for i ← 0 to n - 1
    process(A[i])

• Symbols: i is the current index, n is the logical size, and process represents an operation such as printing or summing.
• Coverage: The loop processes exactly n elements, including A[0] and A[n - 1].
• Complexity: A complete traversal takes O(n) time and O(1) auxiliary space when no additional collection is created.

D. Array insertion

Insertion places a value at a chosen index while preserving the order of existing elements.

• Preconditions: The insertion index p must satisfy 0 ≤ p ≤ n, and the capacity C must satisfy n < C.
• Procedure:

for i ← n - 1 downto p
    A[i + 1] ← A[i]
A[p] ← x
n ← n + 1

• Symbols: p is the insertion index, x is the new value, n is the old logical size, and C is capacity.
• Direction: Elements shift from right to left in the loop so that an unread value is not overwritten.
• Complexity: Insertion at the end is O(1) when capacity exists; insertion at the beginning or middle is O(n) because up to n values move.

E. Array deletion

Deletion removes the element at a specified index and closes the resulting gap.

• Precondition: The deletion index p must satisfy 0 ≤ p < n.
• Procedure:

removed ← A[p]
for i ← p to n - 2
    A[i] ← A[i + 1]
n ← n - 1

• Symbols: removed stores the deleted value, p is its index, and n is the old logical size.
• Logical effect: The capacity is unchanged, but the logical size decreases by one.
• Complexity: Deleting the last element is O(1); deleting near the beginning is O(n) because later elements shift left.

III. Array Searching — Locating a Target Value

Searching determines whether a target occurs in an array and commonly returns its index or a failure indicator such as -1.

A. Linear search

Linear search compares the target with elements sequentially and does not require sorted data.

• Procedure:

for i ← 0 to n - 1
    if A[i] = x
        return i
return -1

• Symbols: x is the target, i is the examined index, and -1 means that no match was found.
• Behavior: In [8, 3, 11, 6], searching for 11 checks indices 0, 1, and 2, then returns 2.
• Complexity: The best case is O(1) when the first element matches; average and worst cases are O(n).
• Use: It is appropriate for small, unsorted arrays or searches performed too rarely to justify sorting.

B. Binary search

Binary search repeatedly halves the search interval and therefore requires an array sorted by the same ordering used in comparisons.

• Procedure:

low ← 0
high ← n - 1
while low ≤ high
    mid ← low + floor((high - low) / 2)
    if A[mid] = x
        return mid
    else if A[mid] < x
        low ← mid + 1
    else
        high ← mid - 1
return -1

• Symbols: low and high bound the active interval, mid is its midpoint, and floor discards the fractional part.
• Elimination rule: If A[mid] < x, all indices through mid are discarded; otherwise, the upper half is discarded.
• Complexity: The best case is O(1), while average and worst cases are O(log n); iterative auxiliary space is O(1).

IV. Sorting and Efficiency — Ordering and Measuring Operations

Sorting rearranges values into a defined order, while complexity analysis describes how resource use grows as the input becomes larger.

A. Bubble sort

Bubble sort repeatedly compares adjacent elements and swaps inverted pairs, causing a largest unsorted value to move toward the end after each pass.

• Procedure:

for pass ← 0 to n - 2
    swapped ← false
    for j ← 0 to n - 2 - pass
        if A[j] > A[j + 1]
            swap A[j], A[j + 1]
            swapped ← true
    if swapped = false
        break

• Symbols: pass counts completed passes, j indexes adjacent pairs, and swapped records whether a change occurred.
• Invariant: After each full pass, one more element at the right is in its final sorted position.
• Properties: Bubble sort is in-place with O(1) auxiliary space and stable when only strictly inverted pairs are swapped.
• Complexity: With early termination, an already sorted array takes O(n) time; average and worst cases take O(n²).

B. Complexity analysis of array operations

Complexity analysis compares operations by their growth rate rather than by machine-dependent execution time.

• Direct access: Reading or updating A[i] is O(1) because one address calculation identifies the element.
• Traversal and linear search: Visiting up to n elements takes O(n).
• Binary search: Halving the remaining interval gives O(log n) search time, provided the array is sorted.
• Insertion and deletion: End operations can be O(1), but position-based operations are O(n) in the worst case because of shifting.
• Bubble sort: Nested comparisons produce O(n²) average and worst-case time.
• Space distinction: The array itself uses O(n) storage; an algorithm using only counters and temporary values requires O(1) auxiliary space.

V. Stacks — Last-In, First-Out Processing

A stack is a linear ADT in which insertion and deletion occur only at the top, following the last-in, first-out (LIFO) rule.

A. Definition and operations of stacks

Stack operations restrict access to the most recently added element.

• Core operations: push inserts, pop removes, peek reads the top, and isEmpty tests whether the stack has no elements.
• Array representation: An array S of capacity C stores values, while top stores the index of the current top element.
• Initial state: top = -1 represents an empty stack; a stack containing one element has top = 0.
• Applications: Function-call management, undo history, expression evaluation, and bracket matching use LIFO order.

B. Stack traversal

Stack traversal visits stored elements without changing the stack’s logical state.

• Top-to-bottom procedure:

for i ← top downto 0
    process(S[i])

• Symbols: S is the stack array, top is the highest occupied index, and i is the traversal index.
• Order: Top-to-bottom traversal displays elements in potential removal order.
• Complexity: Traversing k stored elements takes O(k) time and O(1) auxiliary space.

C. Push operation

Push adds a new element at the top of a non-full stack.

• Procedure:

if top = C - 1
    report overflow
else
    top ← top + 1
    S[top] ← x

• Symbols: C is capacity and x is the value being inserted.
• Order requirement: Incrementing top before assignment selects the next free position.
• Complexity: Array-based push takes O(1) time.

D. Pop operation

Pop removes and returns the current top element.

• Procedure:

if top = -1
    report underflow
else
    x ← S[top]
    top ← top - 1
    return x

• Logical removal: Decrementing top makes the old location inactive even if its bits remain in memory.
• Complexity: Pop takes O(1) time because no elements are shifted.

E. Stack underflow and overflow conditions

Underflow and overflow identify invalid stack operations at its two capacity boundaries.

1. Underflow: Occurs when pop or peek is attempted while top = -1; there is no valid element to return.
2. Overflow: Occurs in a fixed array implementation when push is attempted while top = C - 1; every allocated slot is occupied.
   • Handling: Operations should return an error, raise an exception, or report status without modifying the stack.

VI. Queues — First-In, First-Out Processing

A queue is a linear ADT in which values enter at the rear and leave from the front, following the first-in, first-out (FIFO) rule.

A. Definition and operations of queues

Queue operations preserve arrival order by separating the insertion and deletion ends.

• Core operations: ENQ inserts at the rear, DEQ removes from the front, and peekFront reads the oldest element.
• Array representation: Array Q has capacity C; front and rear identify the first and last occupied indices.
• Initial state: front = rear = -1 represents an empty queue.
• Applications: Print scheduling, request handling, breadth-first search, and buffering use FIFO order.

B. Queue traversal

Queue traversal processes active elements from the front through the rear without removing them.

• Procedure:

if front ≠ -1
    for i ← front to rear
        process(Q[i])

• Symbols: Q is the queue array and i is the current occupied index.
• Order: Traversal follows arrival order, beginning with the next element eligible for removal.
• Complexity: If k elements are stored, traversal takes O(k) time.

C. ENQ operation

ENQ adds a value at the rear of a queue when storage is available.

• Procedure for a linear array queue:

if rear = C - 1
    report overflow
else
    if front = -1
        front ← 0
    rear ← rear + 1
    Q[rear] ← x

• Symbols: x is the incoming value, and C is the array capacity.
• First insertion: Setting front to 0 establishes the first active position.
• Complexity: ENQ takes O(1) time because existing elements do not move.

D. DEQ operation

DEQ removes and returns the element at the front of a non-empty queue.

• Procedure:

if front = -1
    report underflow
else
    x ← Q[front]
    if front = rear
        front ← -1
        rear ← -1
    else
        front ← front + 1
    return x

• Final removal: When front = rear, the removed value was the only element, so both markers return to the empty state.
• Complexity: DEQ takes O(1) time because the remaining elements are not shifted.

E. Queue underflow and overflow conditions

Queue boundary conditions prevent removal from an empty structure and insertion beyond allocated storage.

1. Underflow: Occurs when DEQ is requested while front = -1; no queued value exists.
2. Overflow: In a linear array queue, it occurs when rear = C - 1, even if earlier positions became unused after deletions.
   • Limitation: This “false overflow” results from not reusing vacant leading slots; a circular queue avoids it by wrapping indices around the array.
   • Handling: A failed operation must report the condition and leave front, rear, and stored data logically unchanged.