Welcome to Data Structures & Collections
Welcome to one of the most fundamental chapters in your CCEA AS Software Systems Development course! Whether you are storing high scores in a game, tracking customer bookings, or reading student records from a file, software needs organized ways to hold information in memory. That is exactly what a data structure is: a specialized format for organizing, processing, retrieving, and storing data.
Don't worry if programming memory concepts sound a bit abstract right now. We will break every concept down into small, step-by-step pieces with everyday analogies and practical coding logic. Let's get started!
---1. Primitive vs. Reference Types
Before looking at complex collections, we need to understand how programming languages store basic data items in computer memory.
Primitive (Value) Types
A primitive type (also called a value type) holds the actual data value directly in its allocated memory space.
Common examples: int (whole numbers), double or float (decimal numbers), char (single characters), and bool (true or false values).
Everyday Analogy: Think of a primitive variable like carrying cash in your wallet. The physical money is stored right there with you.
Reference Types
A reference type does not hold the actual data directly within the variable. Instead, it stores a memory address (a reference or pointer) that points to where the actual data or object is stored in heap memory.
Common examples: Class instances (objects), string values, and arrays.
Everyday Analogy: Think of a reference variable like a coat check ticket or a locker key. The ticket itself isn't your coat; it simply tells the attendant the exact location where your coat is stored.
Key Takeaway: Primitive types store the actual value, while reference types store an address pointing to the location of the object in memory.
---2. One-Dimensional (1D) Arrays
What is a 1D Array?
A one-dimensional array is a fixed-size, sequential collection of elements of the same data type stored in contiguous (side-by-side) memory locations.
Key Characteristics:
• Fixed Size: Once you declare an array's size (e.g., holding 5 items), that size cannot grow or shrink during execution.
• Homogeneous Elements: Every element inside the array must share the same data type (e.g., all integers or all strings).
• Zero-Based Indexing: Position numbering always starts at index \(0\). The last valid index is always \(\text{Length} - 1\).
• Direct Random Access: You can access any element instantly if you know its index position in \(O(1)\) constant time complexity.
Array Operations & Traversal
To inspect or modify elements, we traverse the array using loops:
1. Standard For Loop: Best when you need to know or use the numerical index position:
for (int i = 0; i < numbers.Length; i++)
Inside the loop, numbers[i] retrieves the element at position \(i\).
2. For Each Loop: Best when you simply want to read every item from start to finish without tracking the index:
foreach (int item in numbers)
3. Sequential Search: Checking each element one by one from index \(0\) up to the end to find a matching target value.
Examiner Warning: Off-by-One Errors
A very common exam mistake is the Off-by-One error. If an array has a length of \(5\), its valid indices are \(0, 1, 2, 3,\) and \(4\).
Writing a loop condition like i <= numbers.Length will attempt to read index \(5\), triggering a run-time IndexOutOfRangeException. Always ensure your boundary condition uses < numbers.Length or <= numbers.Length - 1.
Key Takeaway: Arrays provide blazing-fast \(O(1)\) direct access via zero-based indices, but their size is completely static once declared.
---3. Two-Dimensional (2D) Arrays & Matrices
What is a 2D Array?
A two-dimensional array organizes data into a grid or table consisting of rows and columns. It is ideal for timetables, seating charts, game boards, or tabular spreadsheets.
Indexing Convention:
Elements are referenced by specifying both their row and column: grid[row, column].
• The first dimension represents the Row index (horizontal lines).
• The second dimension represents the Column index (vertical lines).
Nested Loop Traversal
To process a 2D array, we use nested loops (a loop inside another loop):
• The outer loop steps through each row.
• The inner loop steps through each column within that row.
Example Pattern:
Outer Loop: for (int r = 0; r < totalRows; r++)
Inner Loop: for (int c = 0; c < totalCols; c++)
Accessing grid[r, c] allows you to display matrix values, compute total sums, or calculate averages row by row.
Key Takeaway: Always follow the standard [row, col] order when traversing matrices. Swapping them accidentally will read data in the wrong orientation.
---4. Arrays of Objects
Working with Class Instances in Arrays
In Object-Oriented Development, you often need to store a collection of custom objects, such as an array of Student or BankAccount instances.
Creating an array of objects is a two-step process that you must understand for the exam:
Step 1: Instantiate the Array Reference
Student[] classList = new Student[30];
This creates an array capable of holding 30 references. However, all 30 slots are initially empty (they hold null).
Step 2: Instantiate Each Individual Object
You must create each object before using its methods or properties:
classList[0] = new Student("Alice", 101);
Examiner Warning: The NullReferenceException Trap
If you perform Step 1 and immediately try to access a property such as classList[0].GetName() without executing Step 2, your program will crash with a NullReferenceException. Creating the array creates the slots; you must still create the objects that go into those slots!
Key Takeaway: An array of objects creates an array of empty references. Every object inside must be explicitly instantiated with new before use.
---5. Static vs. Dynamic Data Structures
Comparing Static and Dynamic Approaches
Choosing the correct data structure requires understanding the difference between static and dynamic memory allocation:
1. Static Data Structures (e.g., Arrays):
• Fixed Size: The size is fixed at declaration/compile-time.
• Memory Footprint: Remains constant throughout execution.
• Advantages: Direct, rapid access to any element using its numerical index; predictable memory allocation.
• Disadvantages: Risk of overflow if you run out of allocated space; risk of underutilization (wasted memory) if you allocate far more spaces than you use.
2. Dynamic Data Structures (e.g., Dynamic Lists):
• Flexible Size: Can grow and shrink dynamically at runtime as items are added or removed.
• Memory Footprint: Expands or contracts on demand.
• Advantages: No need to know the total number of elements in advance; efficient use of memory space.
• Disadvantages: Involves additional memory overhead for managing underlying references and resizing operations.
Core Operations on Dynamic Lists
• Add(item): Appends a new element to the end of the collection.
• Insert(index, item): Places an element into a specific index position, shifting subsequent elements.
• Remove(item): Searches for and deletes a specific element.
• Contains(item): Returns true or false depending on whether the item exists in the collection.
• Count: Property that returns the current number of elements contained in the list.
Key Takeaway: Use static arrays when the data size is known and fixed. Use dynamic lists when the data volume changes unpredictably during runtime.
---6. Representation of Data & File Persistence
How Data is Represented Internally
Computers store all data structures as binary (0s and 1s). In AS 1, you should understand the standard representation formats:
• Integers: Whole numbers stored as binary values. Negative numbers are represented using the Two's Complement system (which inverts the binary bits and adds 1).
• Characters & Strings: Stored using standardized character sets:
- ASCII: Uses 7 or 8 bits to represent basic English characters, numbers, and control codes.
- Unicode: A universal multi-byte encoding standard (such as UTF-8 or UTF-16) that supports characters, symbols, and alphabets from all world languages.
Data Persistence: Reading Delimited Files into Data Structures
Data stored in RAM is volatile (it disappears when the application closes). To preserve data, we read from and write to sequential text files.
The Delimited File Pattern:
Text files often store records as comma-separated values (CSV) or character-delimited strings:
"Alice,101,88.5"
Loading File Data into Collections (Step-by-Step):
1. Open & Read: Open the sequential file and read each line as a raw string.
2. Split / Tokenize: Break the line apart at each delimiter (such as a comma) into an array of string tokens.
3. Parse: Convert the string tokens into appropriate primitive types (e.g., converting "101" to an integer and "88.5" to a double).
4. Instantiate & Store: Create a new object instance using the parsed values and store that object into your array or dynamic list.
Key Takeaway: File reading converts flat text strings from disk into strongly-typed objects and collections inside program memory.
---7. Quick Review & Common Pitfalls Checklist
Essential Concepts Summary
• Primitive Types: Store values directly.
• Reference Types: Store memory addresses pointing to objects or arrays.
• 1D Arrays: Static, zero-indexed (\(0\) to \(\text{Length} - 1\)), fixed-size, homogeneous collections with \(O(1)\) direct access.
• 2D Arrays: Row and column grids accessed as [row, col] using nested loops.
• Object Arrays: Require instantiating both the array container and each individual object.
• Dynamic Lists: Expand and shrink at runtime using Add(), Insert(), and Remove().
Top 4 Exam Pitfalls to Avoid
1. Index Out of Range: Forgetting that an array of length \(N\) ends at index \(N - 1\).
2. Null Reference on Object Arrays: Forgetting to instantiate individual objects inside an array before calling their methods.
3. Static vs. Dynamic Confusion: Stating that a standard array can "automatically resize" itself.
4. Inverted 2D Indexing: Writing [col, row] instead of [row, col] when iterating over rows and columns.