Arrays, Strings, Matrices, and Sequential Structures

Introduction

Sequential structures store elements in a logical order: each element has a position, and traversal proceeds from one position to the next. The array is the fundamental sequential structure in computing. It supports direct access through an index, efficient storage, and predictable memory usage. Strings, matrices, bitsets, dynamic arrays, and sparse representations are specialized or extended forms of sequential storage.

This chapter examines how these structures are represented, implemented, evaluated, and selected for practical software systems. The central design issue is a trade-off between memory efficiency, access speed, update cost, and programming convenience.

Learning Objectives

By the end of this chapter, you should be able to:

• explain the memory model and operations of static and dynamic arrays;
• implement traversal, insertion, deletion, searching, resizing, and reversal;
• distinguish strings from general arrays and apply suitable string operations;
• represent and manipulate one-, two-, and multidimensional arrays;
• compare dense and sparse matrix representations;
• explain bitsets and their applications;
• analyze time and space complexity and select an appropriate sequential structure;
• identify implementation risks involving bounds, overflow, aliasing, and data validation.

1. Array Fundamentals

An array is a finite, indexed collection of elements of the same logical type. In a zero-based array of length n, valid indices are 0 through n-1. The index is not usually stored with the element; it is used to calculate the element's address.

If the first element begins at address B, each element occupies w bytes, and the index is i, then the address of element A[i] is:

Here, 0 ≤ i < n, and all elements must have the same size w. The formula explains constant-time random access: the address calculation does not depend on n. It does not imply that every array operation is constant time.

Static and dynamic arrays

A static array has a fixed capacity determined at creation or compilation. Its advantages are simple representation, low overhead, and predictable memory consumption. Its principal limitation is that its length cannot grow without allocating another array.

A dynamic array maintains a logical size and a physical capacity. The logical size is the number of stored elements; capacity is the number of elements that can be stored before reallocation. A dynamic array normally stores elements contiguously, but it can grow by allocating a larger block, copying elements, and replacing the old block.

The notation O(f(n)) describes an asymptotic upper growth rate while ignoring constant factors and lower-order terms. Amortized analysis averages the cost of an occasional expensive operation over a sequence of operations; it does not claim that every individual operation is inexpensive.

2. Core Array Operations

Traversal

Traversal visits elements in index order. Its time complexity is O(n) and its auxiliary space is O(1) when no additional collection is created.

for i ← 0 to size − 1 do
    process(A[i])
end for

The loop invariant is that, before iteration i, elements at indices less than i have already been processed. Correct bounds are essential: accessing A[size] is an error in a zero-based array.

Linear search

Linear search compares a target with each element until a match is found or the array ends. Its best-case time is O(1), its worst-case time is O(n), and its auxiliary space is O(1). If the array is sorted, binary search may reduce search time to O(log n), but binary search requires random access and a maintained ordering invariant.

Insertion

To insert a value at index p, elements from the last occupied position down to p are shifted one position right. The shift must occur from right to left; copying left to right can overwrite values that have not yet been moved.

if size = capacity then resize()
for i ← size − 1 down to p do
    A[i + 1] ← A[i]
end for
A[p] ← value
size ← size + 1

For insertion at the end, no elements need shifting. For insertion at the beginning, approximately n elements may move. Thus insertion has worst-case time O(n). Preconditions include 0 ≤ p ≤ size and sufficient capacity after resizing.

Deletion

To delete the element at index p, elements after it are shifted left.

removed ← A[p]
for i ← p to size − 2 do
    A[i] ← A[i + 1]
end for
size ← size − 1
return removed

Deletion at the end is O(1), while deletion at the beginning or middle is O(n). In reference-based languages, the unused final slot should be cleared when necessary so that an obsolete object can be reclaimed. This is called avoiding a stale reference.

Reversal

An in-place reversal exchanges symmetric elements. For an array of length n, positions i and n−1−i are exchanged for 0 ≤ i < n/2. The time complexity is O(n) and auxiliary space is O(1).

3. Dynamic Array Resizing

When a dynamic array is full, a common policy is geometric growth. If the old capacity is C and the growth factor is g > 1, the new capacity is often approximately gC. A factor of 2 gives simple implementation; smaller factors use less spare memory but cause more frequent copying.

Suppose capacities begin at 1 and double: 1, 2, 4, 8, and so on. During m append operations, an element can be copied several times, but the total number of copied elements is less than approximately 2m. Therefore, the total cost of m appends is O(m), giving amortized O(1) per append.

A shrink policy must avoid oscillation. Shrinking immediately whenever the array is slightly less than full can cause repeated grow–shrink cycles. A common policy shrinks only when utilization falls below a threshold such as one-quarter, and reduces capacity by a geometric factor. The exact threshold is an engineering choice dependent on memory pressure and workload.

Worked example: insertion and resizing

A dynamic array has size 4 and capacity 4, containing [12, 18, 25, 31]. To insert 20 at index 2:

1. Allocate a new capacity, for example 8.
2. Copy the four existing values.
3. Shift 31 to index 4 and 25 to index 3.
4. Store 20 at index 2.
5. The result is [12, 18, 20, 25, 31], with size 5 and capacity 8.

The resize costs O(4), while the insertion shift also costs O(4). A single operation is therefore linear, even though repeated appends are amortized constant time.

4. Strings

A string is a sequence of characters or, more precisely in many modern systems, a sequence of encoded code units. A string may be represented as a character array plus a length, or as a null-terminated array in which a special zero character marks the end.

A length-stored string can determine its length in O(1). A null-terminated string generally requires O(n) traversal to find its length. Null termination creates a serious safety condition: the terminator must fit within allocated storage, and operations must prevent reading beyond the array.

Important string operations include concatenation, comparison, substring extraction, searching, splitting, and replacement. If two strings of lengths p and q are concatenated into a newly allocated buffer, the copying cost is O(p + q). Repeated concatenation in a loop can become quadratic if each operation copies the entire accumulated result. A string builder or dynamically growing buffer is preferable for substantial construction.

String comparison usually examines characters from left to right. Its worst-case time is O(min(p,q)) for strings of lengths p and q, although a length check may terminate earlier. Character encoding must be considered: a visible character may occupy one or more bytes, and byte length is not necessarily character count.

String-search methods

Naïve pattern matching tests a pattern of length m at successive positions in text of length n. Its worst-case time is O(nm). Algorithms such as Knuth–Morris–Pratt preprocess the pattern and achieve O(n + m) matching time, excluding the cost of reading the input. These methods matter in editors, search systems, log analysis, and intrusion detection.

5. Multidimensional Arrays and Matrices

A matrix is a rectangular arrangement of values with rows and columns. A two-dimensional array A[r][c] has r rows and c columns. Access is constant time when dimensions and element size are known.

In row-major storage, complete rows are placed consecutively. If the base address is B, each element occupies w bytes, and there are C columns, then:

The assumptions are 0 ≤ i < R, 0 ≤ j < C, and a fixed element size. In column-major storage, columns are contiguous:

The storage order affects cache performance. An algorithm traversing a row-major matrix row by row usually has better locality than one traversing it column by column, because nearby accesses are more likely to be in the same cache line.

Matrix operations

For matrices A of dimensions R × K and B of dimensions K × C, multiplication produces D of dimensions R × C:

The conventional algorithm performs R × C × K multiplications and additions, so its time complexity is O(RCK). For square matrices of order n, this becomes O(n³). Matrix multiplication is defined only when the first matrix's column count equals the second matrix's row count.

6. Sparse Matrices

A sparse matrix contains mostly zero or default values. Storing every zero in a dense rectangular array wastes memory and may waste computation. A sparse representation stores only nonzero entries, usually as triples (row, column, value), compressed rows, or linked structures.

The coordinate-list representation for a matrix with z nonzero entries stores triples such as (2, 5, 9). Its storage is O(z) rather than O(RC), plus metadata. It is simple and useful for construction and interchange. Compressed sparse row (CSR) uses three arrays: values, column indices, and row offsets. CSR provides efficient row traversal and matrix–vector multiplication, but arbitrary insertion is expensive because arrays may need shifting or rebuilding.

For a sparse matrix A and dense vector x, the product y = Ax can be computed in time O(z), assuming the sparse structure provides direct access to the nonzero entries. This is preferable to O(RC) dense computation when z is much smaller than RC.

Sparse formats are not universally superior. If most entries are nonzero, metadata overhead and indirect memory access can make a dense array faster and simpler.

7. Bitsets and Packed Sequential Data

A bitset stores Boolean values using individual bits rather than one byte or larger object per value. For n bits, a packed representation requires approximately ceil(n / w) machine words when each word contains w bits.

Bitwise operations are particularly efficient:

• AND computes set intersection;
• OR computes set union;
• XOR identifies differing membership;
• NOT complements bits, subject to masking unused trailing bits.

A bitset can represent permissions, feature membership, visited vertices, or a sieve of prime candidates. It is important to mask unused bits in the final word; otherwise operations may report positions outside the logical range. Bitsets are compact, but they are less suitable when values require more than two states or when sparse true values would make an index list smaller.

8. Correctness, Safety, and Evaluation

Array implementations should maintain explicit invariants:

• 0 ≤ size ≤ capacity;
• every valid logical element lies in indices 0 through size−1;
• no operation reads or writes outside allocated storage;
• metadata agrees with the actual representation;
• a matrix index satisfies its row and column bounds.

Common defects include off-by-one errors, integer overflow in address calculations, incorrect copying direction, use-after-resize references, and accidental shallow copying. For a two-dimensional allocation, it is also necessary to distinguish a true rectangular block from an array of row references: the latter may contain rows of different lengths and may suffer aliasing if rows are reused unintentionally.

Testing should include empty arrays, one-element arrays, full-capacity insertion, repeated resizing, duplicate values, deletion of first and last elements, maximum legal indices, invalid indices, Unicode strings, matrices with zero rows or columns where the language permits them, and sparse matrices with no nonzero entries.

Theoretical complexity should be supplemented by measurement. Cache locality, allocation cost, garbage collection, branch behavior, and element size can substantially affect real performance. Benchmarking should use representative workloads and distinguish construction time from steady-state operation.

9. Applied Case: Sensor-Grid Storage

Background

This illustrative case concerns a campus environmental-monitoring system. Each device reports temperature, humidity, and air-quality readings on a rectangular grid every minute.

Problem

A dense grid of 2,000 × 2,000 cells would contain 4,000,000 positions per measurement. However, construction activity means that only about 30,000 cells contain non-default readings at a particular time. The system must support ingestion, regional scanning, and matrix–vector calculations for a visualization service.

Analysis

A dense matrix offers simple indexing and excellent locality during complete-grid scans, but stores millions of default values. A coordinate list reduces storage for sparse snapshots, while CSR is more suitable if the system repeatedly processes rows. Dynamic arrays are useful for accumulating incoming triples before sorting or compression.

Approach and solution

The ingestion layer collects triples (row, column, value) in a dynamic array. At fixed intervals it sorts or groups them by row and builds CSR arrays. The visualization service uses CSR for row-oriented queries. A separate dense tile cache is used for small, frequently displayed regions, because local dense access is faster than indirect sparse access.

Outcome

The hybrid design avoids treating one representation as universally optimal. Sparse storage reduces memory for the global grid, while dense tiles preserve responsive access where the workload is localized. The system also validates coordinates, timestamps, and sensor identifiers before insertion.

Learning points

Representation should follow density and access pattern. Conversion between representations has a cost and should not occur unnecessarily. Dynamic arrays solve growth during ingestion, but they do not automatically provide efficient two-dimensional queries. Correctness checks are essential because an invalid coordinate can corrupt the entire sparse structure.

10. Best Practices and Contemporary Relevance

Choose an array when direct indexing and compact contiguous storage matter. Choose a linked or other noncontiguous structure only when its update or allocation characteristics justify poorer locality. Reserve capacity when a reliable size estimate is available. Prefer library implementations that have been tested for bounds, encoding, and memory behavior, while still understanding their complexity.

In data engineering and machine learning, arrays and matrices underlie tensors, feature vectors, image data, and numerical kernels. Accelerators often favor contiguous, aligned, and regularly shaped data. Sparse tensors and compressed matrices are important in recommendation systems, graph processing, and scientific computing. AI systems do not eliminate the need for data-structure reasoning: poor layout can increase memory transfer, latency, and energy consumption.

Data governance also matters. Arrays may contain personal, medical, or location data. Developers should minimize collection, enforce access controls, validate input, protect data during storage and transmission, and define retention and deletion procedures. A compact representation is not automatically a secure representation.

Chapter Summary

Arrays provide constant-time indexed access through address arithmetic, but insertion and deletion away from the end generally require linear shifting. Static arrays have fixed capacity; dynamic arrays grow through reallocation and usually provide amortized constant-time append. Strings are sequential character data whose performance and safety depend on representation and encoding. Multidimensional arrays use a defined storage order, and traversal order affects locality. Dense matrices are appropriate when many values are present; sparse formats save space and computation when nonzero entries are relatively few. Bitsets pack Boolean data and support efficient set operations. Correct implementations preserve bounds, size, capacity, layout, and ownership invariants. Selecting a structure requires analysis of density, access pattern, update frequency, memory, and safety requirements.

Key Terms

Array: An indexed, ordered collection of elements.

Static array: An array with fixed capacity.

Dynamic array: A resizable contiguous array with logical size and capacity.

Index: A position used to identify an element.

Capacity: The number of elements that can be stored without resizing.

Amortized analysis: Analysis of average cost over a sequence of operations.

Traversal: Visiting elements according to a specified order.

Row-major order: Storage in which complete rows are contiguous.

Column-major order: Storage in which complete columns are contiguous.

Matrix: A rectangular arrangement of values.

Sparse matrix: A matrix containing relatively few non-default values.

CSR: Compressed sparse row representation.

Bitset: A packed collection of Boolean bits.

String: An ordered sequence of encoded characters or code units.

Null terminator: A special marker indicating the end of some strings.

Cache locality: The tendency to reuse nearby memory efficiently.

Invariant: A condition that remains true during correct execution.

Aliasing: Multiple references that designate the same storage.

Bounds checking: Verification that an index is within its legal range.

Review Questions

Short Answer Questions

1. Why is indexed access in a contiguous array O(1)?
2. Distinguish logical size from capacity in a dynamic array.
3. Why must array elements be shifted from right to left during insertion?
4. What is the main advantage of CSR over dense matrix storage?
5. State two operations naturally supported by bitsets.

Long Answer Questions

1. Explain static and dynamic arrays, including their representations, operations, and complexity trade-offs.
2. Describe string representation choices and analyze the costs and safety concerns of concatenation and comparison.
3. Explain row-major and column-major address calculation and discuss cache locality.
4. Compare coordinate-list, CSR, and dense matrix representations.
5. Describe invariants and test cases needed to validate a dynamic-array implementation.

Analytical / Application Questions

1. A program repeatedly inserts values at the beginning of a sequence. Which representation would you evaluate, and what workload evidence would guide the decision?
2. A 10,000 × 10,000 matrix has only 50,000 nonzero values. Recommend a representation and justify the choice in terms of storage and matrix–vector multiplication.
3. Design a storage strategy for a service that receives unknown numbers of records, frequently appends them, occasionally deletes the last record, and periodically scans all records. Explain capacity, resizing, and safety decisions.

Multiple Choice Questions with Answers

Question 1

What is the worst-case time complexity of inserting an element at the beginning of a contiguous array containing n elements?

A. O(1)

B. O(log n)

C. O(n)

D. O(n log n)

Correct Answer: C. O(n)

Question 2

In a zero-based array of length n, which index is invalid?

A. 0

B. n − 1

C. n

D. n ÷ 2

Correct Answer: C. n

Question 3

Why does repeated append to a geometrically resized dynamic array have amortized O(1) cost?

A. No element is ever copied

B. The total copying over many appends is linear in the number of appends

C. Every append performs binary search

D. The array has unlimited capacity

Correct Answer: B. The total copying over many appends is linear in the number of appends

Question 4

For row-major storage with R rows and C columns, which expression gives the element offset of A[i][j]?

A. j × R + i

B. i × C + j

C. i + j × C × R

D. i × j

Correct Answer: B. i × C + j

Question 5

Which representation is generally most appropriate when a matrix has very few nonzero entries?

A. Dense rectangular array

B. Sparse representation

C. Unbounded string

D. Bitwise complement only

Correct Answer: B. Sparse representation

Question 6

What is the primary purpose of a null terminator in a null-terminated string?

A. To store the string's capacity

B. To mark where the string ends

C. To encode every Unicode character

D. To sort the characters

Correct Answer: B. To mark where the string ends

Question 7

Which bitwise operation commonly represents set intersection in a bitset?

A. AND

B. OR

C. XOR

D. NOT

Correct Answer: A. AND

Question 8

A matrix has dimensions 3 × 4. What are the dimensions of its product with a compatible 4 × 2 matrix?

A. 3 × 2

B. 4 × 4

C. 2 × 3

D. 3 × 4

Correct Answer: A. 3 × 2

Question 9

What is a major risk of shifting array elements from left to right during insertion?

A. The array becomes automatically sorted

B. Unmoved values may be overwritten

C. The capacity doubles incorrectly

D. Indexing becomes one-based

Correct Answer: B. Unmoved values may be overwritten

Question 10

Which condition is a valid dynamic-array invariant?

A. capacity < size always

B. size may be negative

C. 0 ≤ size ≤ capacity

D. Every array must have at least two elements

Correct Answer: C. 0 ≤ size ≤ capacity