CAB201 – Collections: Comprehensive Study Notes

Acknowledgement of Traditional Owners

• QUT acknowledges the Turrbal and Yugara peoples as First Nations owners of the lands where the university stands.

• Respect is paid to Elders, lores, customs, and creation spirits.

• Recognition that these lands have always been places of teaching, research, and learning.

• Emphasises the important role Aboriginal and Torres Strait Islander people play within the QUT community.

Motivating Scenarios (Café Examples)

• Single-employee wage task:- Worked 3\ \text{h} on Tuesday, 8\ \text{h} on Wednesday, 5\ \text{h} on Friday

  • total hours 3+8+5 = 16\ \text{h}.

  • Pay rate: \$35/\text{h}; tips: \$50.

  • Earnings formula: \text{wage} = (\text{hours}\times\text{rate}) + \text{tips} = 16\times35 + 50 = 610.

  • Steps: calculate hours → multiply by rate → add tips → print.

• Multi-employee wage task (Jake, María, Sam): repeat identical steps per employee.

• Purpose: highlight repetitive computation ⇒ need for structured collections & iteration.

What Is a Collection?

• Type that stores multiple variables/values in one entity.

• Simplifies management and manipulation (add, remove, find, insert).

• Categories presented:

  • Arrays (1-D, parallel, multi-D)

  • Collections Framework (List, SortedList, Dictionary, Queue, Stack)

  • To use non-generic collections (e.g., older ArrayList), using System.Collections; must be added near the top of a C# file.

  • For generic collections (e.g., List<T>, Dictionary<TKey, TValue>), using System.Collections.Generic; is required instead.

Arrays

Core Properties

• Fixed-size, contiguous memory block.

• Elements share one data type; accessed with zero-based index.

• Syntax (declaration): TYPE[] identifier; e.g. int[] ages;

• Typical plural identifiers (names, sales) to signal multiple elements.

Creating Arrays

• Allocate with new & length:

TYPE[] id = new TYPE[length];
// Example:
string[] studentNames = new string[10]; // Declares an array to hold 10 student names

or two-step declaration & allocation.

• Valid length range 0 \ldots 2^{31}-1 (≈ 2 billion).

• Example with constant length:

const int MONTHS = 12;
int[] monthlySales = new int[MONTHS];

• Memory size formula: \text{size(bytes)} = \text{length} \times \text{sizeof(TYPE)}.

  • Example: double[20] ⇒ 20 \times 8 = 160\ \text{bytes}.

• Default values: numeric 0, char \u0000, bool false, reference types null.

Initialising Elements

• At declaration:

int[] hours1 = {30,50,20,15,40};
int[] hours2 = new int[] {30,50,20,15,40};
int[] hours3 = new int[5] {30,50,20,15,40};

• Element-by-element after allocation with index assignments.

int[] temperatures = new int[3]; // Array of size 3 declared
temperatures[0] = 25;           // Assigns value to first element
temperatures[1] = 28;
temperatures[2] = 22;

Take-Home Points on Arrays

• Most common collection; contiguous memory enables efficient access.

• Indices allow both read & write but require bounds safety.

Iterating over Arrays

Options

• Manual Console.WriteLine(array[i]) for each index (error-prone, not scalable).

• for, while, do-while, foreach loops.

For Loop

• Canonical form:

for(int i=0; i<array.Length; i++)
{
    // ... do something with array[i]
}
// Example:
string[] colors = {"Red", "Green", "Blue"};
for (int i = 0; i < colors.Length; i++) {
    Console.WriteLine(colors[i]); // Prints each color
}

• Using Length provides defensive programming; prevents hard-coded bounds errors.

While & Do-While

• while checks before body; do checks after ⇒ risk with empty arrays (body executes once regardless).

// Example for while loop
int[] numbersWhile = {10, 20, 30};
int j = 0;
while (j < numbersWhile.Length) {
    Console.WriteLine(numbersWhile[j]);
    j++;
}

// Example for do-while loop (with guard for empty arrays)
int[] numbersDoWhile = {40, 50};
int k = 0;
if (numbersDoWhile.Length > 0) {
    do {
        Console.WriteLine(numbersDoWhile[k]);
        k++;
    } while (k < numbersDoWhile.Length);
}

Foreach

• Syntax: foreach(TYPE item in collection) { ... }

• Read-only iteration over entire collection.

• Cannot (a) select subset, (b) reassign item; attempting reassignment raises compile-time error.

double[] prices = {1.99, 5.75, 10.00};
foreach (double price in prices) {
    Console.WriteLine($"Price: ${price}");
}

Comparative Table (high-lights)

• Readability: foreach > for > while ≈ do.

• Ability to change elements / subset: only for, while, do.

• Handles zero-length: all except do (needs guard).

Testing Iterations

• Absence, Boundary, Normal, Special cases; e.g. zero-element array, max length Int32.MaxValue.

Array Methods

Copying

• By value vs by reference:

  • Scalar assignment duplicates value.

  • Array assignment copies reference ⇒ both variables point to same memory; modifying one affects both.

• Deep copy utility: Array.Copy(source, dest, length).

int[] original = {1, 2, 3, 4, 5};
int[] copied = new int[5]; // Destination array must be allocated
Array.Copy(original, copied, original.Length); // Copies all elements from original to copied
// copied array now contains {1, 2, 3, 4, 5}

Sorting

• Array.Sort(array) sorts ascending (default comparer).

string[] fruit = {"Orange", "Apple", "Banana"};
Array.Sort(fruit); // fruit array becomes {"Apple", "Banana", "Orange"}

• Must test across absence, boundary (1 element), normal, inverse-sorted, duplicates, etc.

Reversing

• Array.Reverse(array) flips order.

int[] digits = {1, 2, 3, 4};
Array.Reverse(digits); // digits array becomes {4, 3, 2, 1}
// Combined with Sort for descending order:
int[] nums = {5, 1, 4, 2};
Array.Sort(nums);    // nums becomes {1, 2, 4, 5}
Array.Reverse(nums); // nums becomes {5, 4, 2, 1}

• Frequently combined: Sort then Reverse to obtain descending order.

Searching – Binary Search

• Requires sorted array.

• API: Array.BinarySearch(array, element) returns index (≥0) if found, negative if not.

int[] sortedNumbers = {10, 20, 30, 40, 50}; // Array must be sorted first
int index = Array.BinarySearch(sortedNumbers, 30); // index will be 2 (found)
int notFoundIndex = Array.BinarySearch(sortedNumbers, 25); // returns negative, e.g., -3 (not found)

• Example use case: decide whether "Simon" or "Sam" is an employee.

Improvement Suggestions

• Guard zero-length arrays ⇒ explicit user message.

• Case-insensitive search: convert both array and query to same case.

Parallel Arrays

• Definition: two or more arrays with one-to-one positional correlation.

  • Example: int[] hours = {30,50,20,15,40}; correlates with string[] names = {"Jenny","Simon",...}.

• Iteration pattern: single index traverses all arrays synchronously.

• Risks: correlation can break if arrays are sorted independently; lengths may diverge.

• Mitigation: length equality checks; avoid independent sorting or perform coordinated operations.

Multidimensional Arrays

Why

• Represent tabular data (e.g. hours per employee per day).

• Employees as rows x; days as columns y.

Declaration & Creation

• 2-D: TYPE[,] id = new TYPE[xLen,yLen];

int[,] matrix = new int[3, 4]; // Declares a 3x4 2D array (3 rows, 4 columns)

• 3-D: commas = dimensions − 1 (TYPE[,,] for 3-D).

double[,,] cube = new double[2, 3, 4]; // Declares a 2x3x4 3D array

• Inline initialiser examples:

int[,] hoursPerDay = {
     {6,8,4,12},
     {11,12,13,14},
     {12,0,3,5},
     {0,0,9,6},
     {12,6,8,14}
  };

Traversal

• Nested loops with GetLength(dim) to fetch bounds.

int[,] gridData = {{1, 2, 3}, {4, 5, 6}};
for (int row = 0; row < gridData.GetLength(0); row++) { // GetLength(0) for number of rows
    for (int col = 0; col < gridData.GetLength(1); col++) { // GetLength(1) for number of columns
        Console.Write($"{gridData[row, col]} ");
    }
    Console.WriteLine(); // New line after each row
}

• Improvement tasks: printing row labels (names) stored separately; computing weekly totals per employee ⇒ sum across columns.

Pros & Cons vs Parallel Arrays

• Multi-D enforces correlation within one structure but restricts to single data type.

• Choice depends on need for heterogenous types vs integrity of linkage.

List

Essence

• Dynamically sized, type-safe sequence (generic).

• Declaration: List<TYPE> id; Creation: id = new List<TYPE>();.

// Required for List<T>
using System.Collections.Generic;

// ... inside a method or class ...
List<string> shoppingList = new List<string>(); // Declares and initializes an empty list of strings

Key Methods

• Add(element) appends.

shoppingList.Add("Milk");    // Adds "Milk" to the end of the list
shoppingList.Add("Bread");   // Adds "Bread"

• Remove(value) deletes first match; silent if not found.

shoppingList.Remove("Milk"); // Removes the first occurrence of "Milk"

• Count property for size/absence tests.

int itemCount = shoppingList.Count; // itemCount will be 1 if only "Bread" remains
if (shoppingList.Count == 0) Console.WriteLine("List is empty.");

• Additional: Sort, Reverse, ToArray(), Contains(element).

// Sort
List<int> unsortedNums = new List<int> {5, 1, 4, 2};
unsortedNums.Sort(); // unsortedNums becomes {1, 2, 4, 5}

// Reverse
List<string> namesList = new List<string> {"Alice", "Bob", "Charlie"};
namesList.Reverse(); // namesList becomes {"Charlie", "Bob", "Alice"}

// ToArray()
string[] namesArray = namesList.ToArray(); // Converts the List<string> to a string[]

// Contains(element)
bool hasBob = namesList.Contains("Bob"); // hasBob will be true
bool hasDavid = namesList.Contains("David"); // hasDavid will be false

Characteristics

• Same conceptual behaviour as arrays but without fixed capacity.

• Elements always appended to end by default; can insert at index with Insert (not shown on slides).

Dictionary

Concept

• Collection of unique keys mapping to values; implemented via hash table ⇒ O(1) average search.

• Similar benefits to parallel arrays (paired data) but enforced by structure.

Declaration & Creation

• Dictionary<KEY_TYPE, VALUE_TYPE> dict = new Dictionary<...>() { {key1,val1}, ... };

// Required for Dictionary<TKey, TValue>
using System.Collections.Generic;

// ... inside a method or class ...
// Declaration and inline initialization
Dictionary<string, int> employeeHours = new Dictionary<string, int> {
    {"Jake", 16},
    {"Maria", 20},
    {"Sam", 12}
};

• Alternately create empty then Add(key,value).

Dictionary<string, string> countryCapitals = new Dictionary<string, string>();
countryCapitals.Add("France", "Paris");
countryCapitals.Add("Germany", "Berlin");
// Attempting to add a duplicate key (e.g., "France") would throw an ArgumentException.

Access & Search

• Indexer: dict[key] returns value (throws if key missing).

int jakeHours = employeeHours["Jake"]; // jakeHours will be 16
// Attempting to access a missing key (e.g., employeeHours["No One"]) would throw a KeyNotFoundException.

• Safe pattern: ContainsKey(key) then access.

string searchEmployee = "Maria";
if (employeeHours.ContainsKey(searchEmployee)) {
    Console.WriteLine($"{searchEmployee} has worked {employeeHours[searchEmployee]} hours.");
} else {
    Console.WriteLine($"Employee {searchEmployee} not found.");
}

• Example program: prompt user for employee name; if present, output “{name} has worked {hours} hours”, else error.

Testing Scenarios

• Absence (empty dictionary), boundary (single element), normal (multiple), invalid look-ups.

Advantages / Disadvantages

• Fast lookup, more intuitive than numeric index.

• Keys must be unique; values need not be.

• Dynamic size similar to List.

Choosing the Right Collection & Loop

• Arrays: fixed size; high performance; good when size known & constant.

• List: variable size; simpler when collection grows/shrinks.

• Dictionary: key-value semantics; efficient look-up.

• Loop guidance:

  • Whole-collection read-only ⇒ foreach.

  • Modification / subset ⇒ for (or while).

  • Avoid do-while with possibly empty collections unless guarded.

Testing Collections

• Always include:

  • Absence tests (zero elements).

  • Boundary tests (length 1, max length, min/max values).

  • Normal cases (typical inputs, assorted orderings).

  • Special cases (sorted, reverse-sorted, duplicates).

• For dictionaries: verify both present & absent keys.

Key Take-Home Messages

• Master array fundamentals (declaration, creation, memory layout, indexing).

• Learn built-in Array methods (Copy, Sort, Reverse, BinarySearch).

• Understand limitations of fixed size vs dynamic collections.

• Recognise that loop selection affects readability, safety, and capability.

• Appreciate testing strategies for robustness.

• Reference learning resources for deeper exploration:

  • MS Docs: System.Array, System.Collections.Generic.

  • GeeksForGeeks, W3Schools articles on C# arrays & collections.