Arrays, Strings, and Dynamic Collections

Introduction

Programs rarely operate on one value at a time. They process marks, prices, names, sensor readings, transactions, and records. Data structures provide organized ways to store and manipulate such collections of values. This chapter examines fixed-size arrays, strings, two-dimensional arrays (matrices), lists, and dynamic collection facilities in Java and Python.

The central design issue is choosing a representation that matches the problem. Arrays provide fast indexed access and compact storage, but their size is normally fixed. Dynamic collections grow and shrink conveniently, but may require additional memory and may involve shifting or hashing costs. Strings are specialized sequences whose immutability affects both correctness and performance.

Learning Objectives

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

• Declare, initialize, access, update, and traverse arrays in Java and Python.
• Explain indexing, bounds, mutability, and memory trade-offs.
• Process strings using common operations while recognizing immutability.
• Represent and compute with matrices.
• Use Java collections and Python lists, tuples, and dictionaries appropriately.
• Compare common operations using asymptotic time and space complexity.
• Select a suitable collection for a practical application.

1. The Sequence Abstraction

A sequence is an ordered collection in which each element has a position. Most programming languages use zero-based indexing: the first element has index 0, the second has index 1, and so on. For a sequence of length n, valid indices are 0 through n − 1. An index outside this range is an error or produces an exception, depending on the language and operation.

An indexed access such as A[i] is efficient when the structure supports direct access. In a conventional array, the address of an element can be conceptually calculated as:

Here, base(A) is the starting address, i is the index, and s is the storage size of one element in bytes. This relationship assumes a contiguous array representation and gives constant-time access, commonly written O(1). The notation O(1) describes an operation whose running time does not grow with the number of elements.

Insertion or deletion in the middle of an array usually requires later elements to move. If n elements may need to be shifted, the worst-case time is O(n). Appending to a dynamic array is often amortized O(1), meaning that occasional expensive resizing is averaged over many insertions.

2. Fixed Arrays

Java arrays

Java arrays have a fixed length and store elements of one declared type. The array object records its length, which cannot be changed after creation.

int[] scores = new int[4];
scores[0] = 72;
scores[1] = 81;
scores[2] = 69;
scores[3] = 90;

for (int score : scores) {
    System.out.println(score);
}

An array can also be initialized directly:

int[] scores = {72, 81, 69, 90};
System.out.println(scores.length); // 4

Java checks array bounds at runtime. Accessing scores[4] raises ArrayIndexOutOfBoundsException. This protects memory safety but requires programmers to use valid indices.

Java arrays of primitive values, such as int[], store values directly in the array storage. Arrays of objects, such as String[], store references to objects. This distinction affects memory use and the possibility of null elements.

Python list-like arrays

Python’s built-in list is a resizable sequence rather than a fixed low-level array. It is commonly used where a beginner might use an array:

scores = [72, 81, 69, 90]
for score in scores:
    print(score)

Python also provides the array module for compact arrays of values of one basic type, and libraries such as NumPy for numerical arrays. A standard Python list is more flexible because it can contain objects of different types, although mixed types can make programs harder to reason about.

values = [10, 20, 30]
values.append(40)
values[1] = 25
print(values)       # [10, 25, 30, 40]

Traversal patterns

An index-based traversal is useful when the index is needed:

for (int i = 0; i < scores.length; i++) {
    System.out.println(i + ": " + scores[i]);
}

for i, score in enumerate(scores):
    print(i, score)

An enhanced or direct traversal is clearer when only values are required. A common error is changing the loop variable rather than changing the array element. In Java, for (int x : scores) { x = 0; } does not modify the array because x receives a copy of each primitive value.

3. Strings and Text Processing

A string is an ordered sequence of characters or, more precisely in modern systems, a sequence of encoded text units. Text may contain letters, digits, punctuation, and characters from many writing systems. Unicode allows programs to represent international text, but the number of user-perceived characters is not always identical to the number of bytes or code units.

Java strings

Java String objects are immutable. Once created, their character sequence cannot be changed. Operations that appear to modify a string create another string.

String name = "Ada";
String greeting = "Hello, " + name;
String upper = greeting.toUpperCase();
System.out.println(greeting); // Hello, Ada
System.out.println(upper);    // HELLO, ADA

For repeated modification, use StringBuilder:

StringBuilder report = new StringBuilder();
for (int i = 1; i <= 3; i++) {
    report.append("Item ").append(i).append("\n");
}
System.out.print(report.toString());

Repeated concatenation in a loop can create many temporary strings. StringBuilder is generally more suitable when constructing a large result incrementally.

String equality must be tested with .equals, not ==:

if (userInput.equals("yes")) {
    System.out.println("Confirmed");
}

The operator == compares references for objects; .equals compares string content.

Python strings

Python strings are also immutable. Methods return new strings rather than altering the original.

text = "  Data Structures  "
clean = text.strip().lower()
words = clean.split()
print(words)  # ['data', 'structures']

For many fragments, accumulate them in a list and join once:

parts = ["Java", "and", "Python"]
result = " ".join(parts)

This avoids repeatedly creating intermediate strings. Python’s == compares string content, while is tests object identity and should not be used for ordinary text equality.

Common string operations

Important operations include length, indexing, slicing, searching, splitting, joining, replacement, and case conversion. Their exact complexity can depend on the language implementation and encoding. Treating string length as n, scanning the entire string is generally O(n). Searching with a straightforward scan is also typically O(n), while repeated concatenation may become costly if each operation copies the accumulated result.

Input validation is especially important. A program should define whether leading spaces, capitalization, empty strings, punctuation, and non-ASCII characters are acceptable. Security-sensitive programs must also avoid assuming that visual characters correspond one-to-one with bytes.

4. Matrices and Two-Dimensional Arrays

A matrix is a rectangular arrangement of values with rows and columns. A matrix with r rows and c columns contains r × c elements. In programming, it is commonly represented as an array of arrays.

Java example:

int[][] temperatures = {
    {18, 20, 21},
    {17, 19, 22}
};

for (int row = 0; row < temperatures.length; row++) {
    for (int col = 0; col < temperatures[row].length; col++) {
        System.out.print(temperatures[row][col] + " ");
    }
    System.out.println();
}

Java technically permits jagged arrays, in which rows have different lengths:

int[][] jagged = {{1, 2}, {3, 4, 5}};

Python representation:

matrix = [
    [18, 20, 21],
    [17, 19, 22]
]

for row in matrix:
    for value in row:
        print(value, end=" ")
    print()

A safe way to create independent Python rows is:

matrix = [[0 for _ in range(3)] for _ in range(2)]

The expression [[0] 3] 2 should be avoided for mutable row lists because both rows refer to the same inner list. Updating one row would then appear to update the other.

Matrix computation

For matrices A and B of equal dimensions, element-wise addition is defined by:

Matrix multiplication is more restrictive. If A has dimensions m × n and B has dimensions n × p, then C = AB has dimensions m × p, with:

The shared dimension n must match. A direct multiplication algorithm performs m × n × p multiplications and additions, giving time complexity O(mnp).

For example, if

A = [[1, 2],
     [3, 4]]
B = [[5, 6],
     [7, 8]]

then:

• C[0][0] = 1×5 + 2×7 = 19
• C[0][1] = 1×6 + 2×8 = 22
• C[1][0] = 3×5 + 4×7 = 43
• C[1][1] = 3×6 + 4×8 = 50

Thus C = [[19,22],[43,50]].

5. Dynamic Collections

Dynamic collections manage changing numbers of elements. They typically maintain an internal storage area and resize when capacity is reached. Resizing may involve allocating a larger area and copying existing elements. Consequently, a single append can be O(n), but append is commonly amortized O(1).

Java collection framework

Java’s main collection interfaces include:

Example using ArrayList:

import java.util.ArrayList;
import java.util.List;

List<String> tasks = new ArrayList<>();
tasks.add("compile");
tasks.add("test");
tasks.add("document");
tasks.remove("test");

for (String task : tasks) {
    System.out.println(task);
}

ArrayList is usually a good default for an indexed, resizable sequence. It provides fast indexed access and efficient append, but insertion near the beginning requires shifting elements. LinkedList can insert or remove efficiently after a node has been located, but locating an indexed position is linear and its node overhead can be substantial. In many practical programs, ArrayList performs better than a linked list even when theoretical operations appear similar, because contiguous memory improves cache behavior.

A HashMap supports key-based lookup on average in constant time, subject to suitable hashing and implementation behavior:

Map<String, Integer> inventory = new HashMap<>();
inventory.put("pens", 40);
inventory.put("books", 12);
int quantity = inventory.getOrDefault("pens", 0);

Never assume that a hash map provides sorted iteration. Use TreeMap when sorted key order is required, accepting logarithmic-time ordered operations in typical implementations.

Python collections

Python’s list is a dynamic sequence:

tasks = ["compile", "test", "document"]
tasks.remove("test")
tasks.append("deploy")

A tuple is an immutable sequence:

coordinate = (12.5, 8.0)

Use tuples when the grouping should not be changed, although immutability of the tuple does not make mutable objects stored inside it immutable.

A dictionary maps keys to values:

inventory = {"pens": 40, "books": 12}
quantity = inventory.get("pens", 0)

A set stores unique elements and is useful for membership tests and eliminating duplicates:

registered = {"Amina", "Jon", "Amina"}
print(registered)  # Amina occurs once

Python also supplies collections.deque for efficient insertion and removal at both ends, and collections.Counter for frequency counting.

6. Complexity and Memory Trade-offs

Big-O notation describes growth as input size increases; it does not predict exact elapsed time on every machine. The following typical comparisons assume ordinary implementations and no unusual hashing behavior.

A fixed array can use less overhead and may improve locality. A dynamic array reserves spare capacity, which costs memory but avoids resizing on every insertion. A linked structure stores additional references or node metadata. A dictionary or hash map requires a table and hashing-related overhead, but provides convenient key-based access.

Space complexity should include both stored values and structural overhead. For a matrix with r × c values, storage is O(rc). A list containing references to objects may use more memory than a packed numerical array because the objects and references are separate.

7. Choosing the Appropriate Structure

Use a fixed array when the number of elements is known and indexed access is central. Use a dynamic list when the sequence changes size or when convenient built-in operations are valuable. Use a set when uniqueness and membership are more important than position. Use a map or dictionary when each value is naturally identified by a key. Use a queue or deque when elements are processed from an endpoint. Use a matrix or numerical array when data has row-and-column structure.

The choice should also consider:

• Access pattern: sequential, indexed, key-based, or endpoint-based.
• Mutation pattern: frequent append, middle insertion, deletion, or no mutation.
• Ordering: whether insertion order or sorted order matters.
• Memory constraints: object overhead and spare capacity may be significant.
• Type safety: homogeneous structures make errors easier to detect.
• Clarity: the simplest suitable abstraction is normally preferable.

8. Applied Case: Course Assessment Manager

Background

This illustrative case concerns a small training centre that records learner names and assessment scores. The system must calculate averages, identify learners requiring support, and produce a report.

Problem

The initial design stores every score in separate variables. This makes it difficult to process an arbitrary number of learners and encourages duplicated code. The centre needs a representation that supports changing enrolment and clear lookup by learner identifier.

Analysis

Scores form a sequence for each learner, so a list is suitable. Learner records are naturally associated with identifiers, so a dictionary in Python or a Map in Java is appropriate. If the number of assessments is fixed, an array could store each learner’s scores; if assessments can be added, a dynamic list is more flexible.

For n scores with values x₁, x₂, …, x_n, the arithmetic mean is:

This formula assumes n > 0 and that all scores are measured on the same scale. An empty score list has no defined arithmetic mean and must be handled explicitly.

Python solution

records = {
    "L001": [72, 81, 69],
    "L002": [55, 61, 58],
    "L003": [90, 87, 93]
}

for learner_id, scores in records.items():
    if not scores:
        print(learner_id, "has no scores")
        continue
    average = sum(scores) / len(scores)
    status = "support required" if average < 60 else "satisfactory"
    print(learner_id, round(average, 2), status)

For each learner, computing the average takes time proportional to the number of scores. If there are L learners and each has at most a scores, the complete processing cost is O(La) in the worst case. The records themselves require O(La) storage.

Outcome

The new design supports additional learners by adding dictionary entries and supports additional assessments by appending scores. It also separates identity, collection, and calculation, making future changes easier.

Learning points

The case demonstrates that a data structure is part of the application design, not merely a storage detail. A list models ordered scores, while a map models lookup by learner ID. Validation is required for empty records, invalid score ranges, and duplicate identifiers. In a production system, access control and privacy protections would also be necessary because assessment data is sensitive personal information.

9. Challenges, Governance, and Best Practices

Collection code can fail through off-by-one errors, accidental aliasing, invalid indices, null values, and unintended mutation. Defensive practices include validating input, using meaningful variable names, preferring direct iteration when indices are unnecessary, and writing tests for empty, one-element, duplicate, and unusually large inputs.

Sensitive strings and collections may contain passwords, personal data, or confidential records. Programs should minimize collection of unnecessary data, restrict access, avoid logging secrets, and delete information according to institutional policy. A collection’s technical efficiency does not justify retaining data without a legitimate purpose.

Modern languages increasingly provide immutable collections, generic type systems, static analysis, and library algorithms. Java generics such as List<String> prevent many type errors at compile time. Python type hints such as list[str] improve tooling, although they do not by themselves enforce types at runtime. Numerical and data-science applications may use specialized packed arrays, but these should be chosen deliberately because they introduce library dependencies and different semantics from ordinary lists.

Best practice is to measure before optimizing. Choose a clear representation, establish correctness with tests, then profile genuine bottlenecks. Avoid replacing a simple list with a complex structure merely because its theoretical complexity appears better; workload, memory locality, and implementation overhead also matter.

Chapter Summary

Arrays and collections represent ordered or associated groups of values. Fixed arrays provide predictable size and constant-time indexed access, while dynamic arrays provide flexible growth with amortized constant-time append. Strings are immutable in both Java and Python, so repeated construction should use StringBuilder or list-and-join techniques when appropriate. Matrices are commonly represented as nested arrays or lists; matrix multiplication requires compatible dimensions and has direct time complexity O(mnp). Java offers interfaces such as List, Set, Map, and Queue, while Python provides lists, tuples, sets, dictionaries, and specialized collection classes. Effective design balances access patterns, mutation, ordering, memory use, type safety, and clarity. Security, privacy, validation, and testing remain essential whenever collections store real-world data.

Key Terms

Array: A fixed-size indexed sequence of elements.

Index: A position used to access an element, commonly beginning at zero.

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

Immutable: Unable to be changed after creation.

StringBuilder: A Java class for efficiently constructing mutable text.

List: An ordered collection that commonly permits duplicates.

Dynamic array: A resizable array-backed collection.

Amortized complexity: Average cost per operation over a sequence of operations.

Matrix: A rectangular arrangement of values in rows and columns.

Jagged array: An array whose rows may have different lengths.

Set: A collection designed to contain unique elements.

Map: A collection associating keys with values.

Dictionary: Python’s key–value collection type.

Hashing: Transforming a key into a value used to locate a collection entry.

Tuple: An immutable Python sequence.

Deque: A double-ended queue supporting operations at both ends.

Aliasing: Multiple references that point to the same mutable object.

Big-O notation: A description of how resource use grows with input size.

Reference: A value identifying or pointing to an object.

Review Questions

Short Answer Questions

1. Why is indexed access in a conventional array usually O(1)?
2. Why must Java strings be compared with .equals rather than normally with ==?
3. What is the difference between a list and a set?
4. What dimension condition is required for matrix multiplication?
5. What does amortized O(1) append mean for a dynamic array?

Long Answer Questions

1. Compare fixed arrays and dynamic arrays in terms of size, memory, access, insertion, and practical use.
2. Explain string immutability in Java and Python and describe techniques for efficient repeated text construction.
3. Describe Java’s List, Set, Map, and Queue abstractions and give an application for each.
4. Explain how a two-dimensional array represents a matrix and derive the direct multiplication cost for dimensions m × n and n × p.
5. Discuss the factors that should guide a programmer when choosing between a list, set, map, array, and deque.

Analytical / Application Questions

1. Design a collection-based solution for a library system that must find books by ISBN, preserve checkout order, and prevent duplicate ISBN entries. Justify each chosen structure.
2. A Python program creates a matrix using [[0] 4] 3. Explain the resulting problem and write a safer construction.
3. An application repeatedly inserts records at the beginning of a large list. Analyze the likely performance issue and recommend a more suitable collection or design.

Multiple Choice Questions with Answers

Question 1

Which statement about a Java array is correct?

A. Its length changes automatically whenever an element is added.

B. Its length is fixed after creation.

C. It can contain only strings.

D. It does not support indexed access.

Correct Answer: B. Its length is fixed after creation.

Question 2

What is the usual time complexity of indexed access in a conventional array?

A. O(1)

B. O(log n)

C. O(n)

D. O(n²)

Correct Answer: A. O(1)

Question 3

Which Java class is most appropriate for repeatedly constructing a large string?

A. StringBuilder

B. HashSet

C. ArrayDeque

D. Scanner

Correct Answer: A. StringBuilder

Question 4

What does a Python set primarily guarantee?

A. Elements are stored in sorted order.

B. Elements are unique.

C. Elements can be accessed only by integer index.

D. Elements are immutable.

Correct Answer: B. Elements are unique.

Question 5

If matrix A has dimensions 2 × 3, which dimension can matrix B have for A × B to be valid?

A. 2 × 2

B. 3 × 4

C. 4 × 3

D. 2 × 4

Correct Answer: B. 3 × 4

Question 6

What is the direct multiplication cost for an m × n matrix multiplied by an n × p matrix?

A. O(m + n + p)

B. O(mn)

C. O(np)

D. O(mnp)

Correct Answer: D. O(mnp)

Question 7

Which Java collection is designed for key–value associations?

A. List

B. Set

C. Map

D. Queue

Correct Answer: C. Map

Question 8

Why can repeated string concatenation in a loop be inefficient?

A. Strings cannot contain spaces.

B. Strings are immutable, so intermediate strings may be created.

C. Strings are always stored as integers.

D. Concatenation automatically sorts characters.

Correct Answer: B. Strings are immutable, so intermediate strings may be created.

Question 9

Which Python construction safely creates three independent rows of four zeros?

A. [[0] 4] 3

B. [0, 0, 0, 0] * 3

C. [[0 for _ in range(4)] for _ in range(3)]

D. {0: 4, 1: 3}

Correct Answer: C. [[0 for _ in range(4)] for _ in range(3)]

Question 10

What is the typical average lookup complexity of a well-implemented hash map?

A. O(1)

B. O(log n)

C. O(n) always

D. O(n²)

Correct Answer: A. O(1)