Data Structures

HSC SDD has two basic Data Structures that you need to know

Arrays (1D) are sequences of elements/data that are
- all of the same type
  - HSC primitive types are: Integers, Floating Points, Booleans, Characters, Strings
- of a fixed length (number of elements) - even if not all elements are in use
- indexed by the integers 0, 1, 2, 3... (or sometimes 1, 2, 3, ...)
Records are combinations of data associated with one thing. E.g.,
- medical records or driving records
- A person's contact details contains: FirstName, LastName, Phone #, email, etc...

The data types above can either be the primitive data types (In HSC these are Integers, Floating Point Numbers, Booleans, Characters and Strings) or other data structures.

This means you can build data structures that combine other data structures, in particular

Combinations of Arrays and Records
- An array of arrays is a 2D array - and so on for 3D, 4D, .... nD arrays
- Arrays of Records are an important example
  - E.g., A Contact List is an array of Contact records

The data structures you choose are a design choice in response to your understanding of the problem your solving. The understanding is documented using Data Dictionaries.

Software is Input-Processing-Storage-Output of data. To do so cleanly & efficiently requires appropriate Data Structures and Algorithms.
Alternatively: Software is about solving problems for users. To do so requires using Design Thinking to get a good user experience (UX)
The choice of data structures is an important one and there are a lot of structures that a good developer should know. See Wikipedia: List of Data Structures

Arrays

HSC Pseudocode

DIM Names (5) as String

Names(0) = "Tessa"

Names(1) = "Tester"

Names(2) = "Trieste"

Note 1: Arrays in HSC pseudocode can be indexed starting at 0 or 1 - you need to pay attention to the usage and context.
Note 2: DIM comes from (Visual) Basic and is short for dimension - it is the VB way of declaring variables and allocating memory. Why it is in the HSC standard? Maybe because of a dark history that can not be erased from the curriculum memory, or something.

DIM Score (5) as Integer

Score(0) = 5

Score(1) = 6

Score(2) = 5

Score(3) = 7

Score(4) = 6

Total = 0

FOR i = 0 to 5 STEP 1

  Total = Total + Score(i)

NEXT i

Display Total // 30

Arrays in Java

String[] names = new String[5];

names[0] = "Tessa";

names[1] = "Tester";

names[2] = "Trieste";

Numeric arrays are initialised to contain 0s, String (and other object) arrays are initialised to contain nulls. E.g., running the above code in JShell yields

Can also declare and initialize arrays using array literals:

int[] score = {5, 7, 5, 7, 6};

int total = 0;

for (int i = 0; i < score.length; i++) {

    total = total + score[i];

System.out.println("Total = " + total); //30

2D & 3D Arrays

Multidimensional arrays can be thought of as arrays of arrays (of arrays...), i.e., nested arrays. They can then be iterated over using nested for loops.

HSC Pseudocode

BEGIN timesTable(numRows, numCols)

  DIM table (numCols, numRows) as integer

  // initialize array

  FOR col = 1 to numCols

     FOR row = 1 to numRows

         table(col, row) = col*row

     NEXT row

  NEXT col

END timesTable

To avoid confusion of rows vs columns, HSC exam questions will usually clarify which index is which / how to access particular elements.

2D Array Example in Java

public static void temperatureDemo() {

        // Syntax for a 1D array: Type[length]

        // Syntax for 2D array: Type[# rows][# of columns]

        // This is the SAME order as the indices for a matrix in mathematics

        double[][] temp = new double[4][6];

        temp[0] = new double[] {38, 37, 36, 34, 33, 31};

        temp[1] = new double[] {38, 37, 35, 31, 29, 30};

        temp[2] = new double[] {36, 34, 33, 30, 27, 29};

        temp[3] = new double[] {35, 33, 31, 29, 28, 28};

        // Find average temp & Print out the array

        // Need nested loops

        double total = 0;

        for (int i = 0; i < temp.length; i++) {

            for (int j = 0; j < temp[0].length; j++) {

                total = total + temp[i][j];

                System.out.print(temp[i][j] + ", ");

            System.out.println(); // new line for a new row

        // print average of entire plate

        System.out.format("Average temperature is: %.2f \n",

                   total/(temp.length*temp[0].length));

Indexing a 2D array in Java

The best way to think about 2D arrays in Java is as an Array of Arrays, so in the Java example above the array ends up as

temp = [[38, 37, 36, 34, 33, 31],   // 0 : 1st row

        [38, 37, 35, 31, 29, 30],   // 1 : 2nd row

        [36, 34, 33, 30, 27, 29],   // 2 : 3rd row

        [35, 33, 31, 29, 28, 28]]   // 3 : 4th row

//Cols   0   1   2   3   4   5

So running temp[0] would return the first row, temp[2] would return the 3rd row, etc... To get an element from the 2D array you first get the row and then the element in that row. So, to extract the value of 27, you need the row 2 and column 4: temp[2][4].

Records

HSC-style Pseudocode

Before using a record it is a good idea to clearly define it. The Course Specifications use a Visual Basic style DIM (dimensioning) to define new records and arrays.

DIM RECORD Contact

  nickName as String (20)

  fullName as String (50)

  email as String (50)

  age as Integer

END RECORD

DIM jason as Contact

jason.nickName = "JSON"

jason.fullName = "Jason Johansen"

jason.email = "jj@mail.org.sg"

jason.age = 17

Records in Java

The standard way of implementing these in Java is by defining a new class to store the data - a limited use of object orientated programming.

Example A class that defines simple contact information

public class Contact { // NB good Java practice would encapsulate these fields public String nickName; public String fullName; public String email; public int age; // Constructor to make new contacts public Contact(String nick, String full, String _email, int _age) { nickName = nick; // Required to be non-empty fullName = full; email = _email; age = _age; } }

Use of the class

public class ContactExample { public static void main(String[] args) { Contact jason = new Contact("JSON", "Jason Johansen", "jj@mail.org.sg", 17); System.out.println(jason.nickName); // Prints JSON }}

Arrays of Records

HSC-style Pseudocode

Using the Contact record type from above, define an array of 100 Contacts.

DIM contactList(100) as TYPE Contact

contacts(0).nickName = "JSON"

contacts(0).fullName = "Jason Johansen"

contacts(0).email = "jj@mail.org.sg"

contacts(0).age = 17

// add more contacts

// print non-empty nickname: email pairs

FOR i = 1 to 100

  IF contacts(i).nickName IS NOT EMPTY THEN

    DISPLAY contacts(i).nickName ": "

            contacts(i).email

  END IF

NEXT i

Array of Records in Java

Using the Contact class from above, can make a contact list. Just make an array of contacts

Example

public class ContactList { public static void main(String[] args) { Contact[] contacts = new Contact[100]; // can store up to 100 contacts - set the first 2 // Use the constructor to make new contacts contacts[0] = new Contact("JSON", "Jason Johansen", "jj@mail.org.sg", 17); contacts[1] = new Contact("XML", "Xavier Miles", "xml@mail.org.sg", 16);
// Prints list of non-empty nickname: email pairs for (int i = 0; i < contacts.length; i++) { if (contacts[i] != null && contacts[i].nickName.length() > 0) { System.out.println(contacts[i].nickName + ": " + contacts[i].email); } }
// Alternative loop & logic for printing for (Contact c : contacts) { if (c == null || c.nickName.length() == 0) {continue;} System.out.println(c.nickName + ": " + c.email); } }}

Some slight extension material

Classes that are not pure records/data

Your data class in Java can have methods to compare (equals) or convert to a String representation (toString). These methods can play nicely with things like the built in Sort, Search and Arrays.toString methods.

Here is a simplified Contact class to play with

public class Contact { public String fullName; public String nickName; public String email; // Constructor to make new contacts public Contact(String full, String nick, String email){ this.fullName = full; this.nickName = nick; this.email = email; // "this" refers to the current contact object }
// Example: "John Adams ('lil John): POTUS2@us.gov" public String toString() { return String.format("%s (%s): %s", fullName, nickName, email); }
// Contacts are "equal" if fullName & email are equal public boolean equals(Contact other) { if (!email.equalsIgnoreCase(other.email)) { return false; } else if (!fullName.equalsIgnoreCase(other.fullName)) { return false; } else { return true; } }}

Populating an array of records

public class ContactManager {
// Globally accessible contact list for this class static Contact[] contacts = new Contact[10]; public static void main(String[] args) { // Populate the contact list from a string String mockFile = "Ms A, a, a@e.mail \n" + "Mr B, b, b@e.mail \n" + "Prof X, x, prof@x.men"; Scanner sc = new Scanner(mockFile);; int i = 0; while (sc.hasNextLine()) { String[] cData = sc.nextLine().split(","); contacts[i] = new Contact(cData[0].trim(), cData[1].trim(), cData[2].trim()); i = i + 1; } // Output the contact list and test some equality System.out.println(Arrays.toString(contacts)); System.out.println(contacts[0].equals(contacts[1])); }}

using an ArrayList instead of an Array

ArrayList is a Dynamic Array that allows you to not have to worry about how long the array will be ahead of time - it is a more flexible data structure.

Note the use of .add and .get methods for the ArrayList.

public class ContactManager {
// Globally accessible contact list for this class static ArrayList<Contact> contacts = new ArrayList<Contact>(); public static void main(String[] args) { // Populate the contact list from a string String mockFile = "Ms A, a, a@e.mail \n" + "Mr B, b, b@e.mail \n" + "Prof X, x, prof@x.men"; Scanner sc = new Scanner(mockFile); int i = 0; while (sc.hasNextLine()) { String[] cData = sc.nextLine().split(","); Contact c = new Contact(cData[0].trim(), cData[1].trim(), cData[2].trim()); contacts.add(c); i = i + 1; } System.out.println(contacts.toString()); System.out.println( contacts.get(0).equals(contacts.get(1))); }}

Report abuse