5.1: Data Structures & File Design
Exam Board:
Eduqas / WJEC
Specification:
2020 +
What is a Data Structure?
A data structure is a way of efficiently organising data. There are two general forms of data structures:
Static Data Structures
The size of a static data structure cannot change e.g. if a data structure has 20 elements, no additional elements can be added or removed.
The values of the data elements can be changed, but memory size is fixed when allocated at compile time.
Because a static data structure holds a certain number of data elements they are easier to program because the size of the structure and the number of elements never change.
An array is an example of a static data structure.
Examples:
A static data structure could be an array of teams in the Premier League. The data elements will change each year when teams are relegated and promoted but there will always be 20 teams.
Dynamic Data Structures
The size of a dynamic data structure can change as the program is being run, it is possible to add or remove data elements.
Dynamic data structures make the most efficient use of memory but are more difficult to program, as you have to check the size of the data structure and the location of the data items each time you use the data.
​
A list is an example of a dynamic data structure.
A dynamic data structure could be a list of all teams in the Premier League that won their last match. Data elements (teams) will be added or removed across the season.
Types of Data Structures
List
A list is a dynamic data structure that has the data elements stored in the order they were originally added to memory.
​
Every data structure starts at 0, not 1. Lists store data elements in the order they were added, so the first doctor is 0 and the most recent doctor is 12.
An example list of the main Doctor Who actors
Array
An array is a static data structure that can hold a fixed number of data elements. Each data element must be of the same data type i.e. real, integer, string.
The elements in an array are identified by a number that indicates their position in the array. This number is known as the index. The first element in an array always has an index of 0.
​
You should know how to write pseudo code that manipulates arrays to traverse, add, remove and search data. The following steps uses Python as an example.
Traversing an Array
To traverse ('move through') an array a for loop can be used to display each data element in order.
'Inserting' a value
In an array the size is fixed so you cannot insert new values, but you can change the value of elements that already exist. Overwriting the fourth element (Daphne) with a new value (Laura) will change it from Daphne to Laura.
Example code for traversing:
Example code for inserting:
Output:
Output:
'Deleting' a value
In an array the size is fixed so you cannot delete values, but you can overwrite them as blank. Overwriting the second element (Shaggy) with a blank space makes it appear deleted.
Example code for deleting:
Output:
Searching an Array
For large arrays a for loop is needed to search through each element for a specific value. This example checks each name to see if it is equal to Velma.
Example code for searching:
Output:
Two-Dimensional Array
Often the data we want to process comes in the form of a table. The data in a two dimensional array must still all be of the same data type, but can have multiple rows and columns.
​
The two-dimensional array to the right shows the characters from Scooby Doo along with their associated colour and their species.
​
Each value in the array is represented by an index still, but now the index has two values. For example [3] [0] is 'Daphne'. We measure row first, then column.
Searching a two-dimensional array:
To print a specific data element you can just use the index number like Daphne above. To search for a specific value you will need two for loops, one for the row and another for the values of each row.
The example to the right is looking for the value of 'Velma' and when it is round it prints the associated data from the whole row.
Example code for printing:
Output:
Example code for searching:
Output:
Records
Unlike arrays, records can store data of different data types.
Each record is made up of information about one person or thing.
Each piece of information in the record is called a field (each row name).
​
Records should have a key field - this is unique data that identifies each record. For example Student ID is a good key field for a record on students as no two students can have the same Student ID.
​
Data files are made up of records with the same structure. It would be most efficient for the fields in a record to be stored next to each other so that the data can be read into the record data structure in memory for processing by the CPU.
In an exam you may be asked to state and design a data structure for a given scenario.
​
If the data structure can hold values of the same data type you should draw an array, usually a 2D array for multiple rows and columns.
​
Remember that a record is required to store values of different data types.
Example questions:
"A video gamer has recorded their three lap times in four Mario Kart courses."
"State and design the most suitable data structure for this data."
​
A two-dimensional array is most suitable because only one data type (real) is stored.
"A vet surgery stores data on all dogs and cats including the animal's name, age (in years), weight (in kg) and whether or not it has been vaccinated."
​
"State and design the most suitable data structure for this data for four animals."
​
A record is most suitable because the data structure requires different data types.
Questo's Questions
5.1 - Data Structures:
​
1. Give two differences between static and dynamic data structures. [4]
2. Describe the differences between a list, array and record. [3]
3. A one-dimensional array looks like this: TigerBreeds("Sumatran","Indian","Malayan,"Amur")
​
Write the code to:
-
a. Print the element with the index of 3. [2]
-
b. Change Indian to South China. [2]
-
c. Remove the Amur element. [2]
-
d. Search through the array for 'Malayan'. [2]
​
4. State and design the most suitable data structure for these scenarios:
-
a. For each book in a bookshop, the staff need to record the title, author, number of pages and whether or not it is a signed copy. Include data for three books. [3]
-
b. Four dieters are recording how many kilograms they have lost each month for 5 months. [4]
​
5. Design a file that stores the first initial, surname, age and hair colour of each member of a family. [8]
Designing Data Structures
Data is stored in files when it needs to be kept after the program has stopped running.
​
To learn how to write code for file handling (e.g. opening, writing to, reading from and closing files) in Python click here.
​
Designing a file requires more than just the field name (e.g. Name) and data values (e.g. Rebecca). The data type (e.g. string) and any validation checks (e.g. format check) should also be considered.
​
Below is an example file design for a bakery.
Designing Files
