Structured Data Types

A Structured Data Type can hold a collection of data values.  This collection will generally consist of primitive data types.  Examples of this would include strings, records, arrays and tables.   These data types are the building blocks of data structures, as we will see later. A brief overview of these data types is given below – we’ll look at each of them in more detail shortly.

A String is a data type that can be used to store a sequence of characters. It is quite distinct from the character data type which can store only a single character. Strings are frequently delimited by double quotes, for example:

Greeting = "Hello World";

Each character would be stored in a separate memory location. This could be represented graphically as follows:

Hello String
Most programming languages provide a variety of string operations, including joining strings (concatenation), selecting part of a string (substring) and calculating the length of a string.

A Record is a data type that allows a number of data items, often of different primitive types, to be grouped together under a common name. For example, a Customer record might be used to store custno, forename and surname:

class Customer {
int custno;
String forename;
String surname;
}

An Array is a data type which allows data items of any type to be stored in adjacent memory locations, addressable by an index number. They can have one or more dimensions. For example, a one-dimensional array of integers, used to store the temperature recorded each day for a week, might be declared as follows:

int[] tempArray = new int[7]; // declares a 1D-array of 7 integers

This could be shown graphically as follows:

1D Array

Note that the index numbers are traditionally shown as starting from zero. The first element could be assigned a value as follows:

tempArray[0] = 15;

A two-dimensional array of integers, used to store the temperature recorded each day for four weeks, might be declared as follows:

int[] tempArray = new int[7][4]; // declares a 2D-array of 7x4 integers

This could be shown graphically as follows:

2D Array

The first element in the first row could be assigned a value as follows:

tempArray[0][0] = 15;

A one-dimensional array is sometimes referred to as a vector and a two-dimensional array as a matrix.

A Table is a data structure in which a set of data elements (values) is organised using vertical columns, identified by their name, and horizontal rows. The place where a row and a column intersect is known as a cell. Each row is identified by the values appearing in a particular subset of columns containing a unique index key. For example, we could create a table of student records:

Student Table

One particularly useful type of table is the hash table, a data structure used to implement an associative array which can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, where the correct value can be found. Hash tables are often used where the number of keys that actually exist is lower than the number that could potentially exist. For example, a six digit number could provide 999,999 unique keys, but perhaps only a tenth of that number are actually used. It would be very wasteful in this case to use a data structure that allocated space for all possible keys.

Ideally the hash function should assign each key to a unique bucket, but this is seldom possible, so most hash table designs assume that hash collisions—different keys that are assigned by the hash function to the same bucket—will occur and must be handled in some way. Hash tables are often found to be more efficient than search trees or any other table lookup structure, so they are widely used in many types of computer software.

Next: String