4.2 - DATA STRUCTURES
Data Structures: A data structure is a format used to store, organise and manage data in a way that
allows efficient access and modification for the needs of the program.
Contents
Arrays....................................................................................................................................................2
Single-Dimensional Array...................................................................................................................2
Multi-Dimensional Array....................................................................................................................2
Fields, records and files.........................................................................................................................2
Abstract Data types/structures..............................................................................................................2
Queues...............................................................................................................................................2
Linear Queues................................................................................................................................3
Circular Queues.............................................................................................................................3
Priority Queues..............................................................................................................................4
Lists....................................................................................................................................................4
Stacks.................................................................................................................................................5
Overflow and Underflow...............................................................................................................5
Call Stacks......................................................................................................................................5
Hash tables........................................................................................................................................6
Dictionaries........................................................................................................................................7
Graphs...............................................................................................................................................7
Adjacency Matrix...........................................................................................................................8
Adjacency List................................................................................................................................9
Trees..................................................................................................................................................9
Rooted Trees................................................................................................................................10
Binary Trees.................................................................................................................................10
Vectors.............................................................................................................................................11
Visualisation of a Vector..............................................................................................................12
Convex combination of two vectors............................................................................................13
Dot or scalar product...................................................................................................................13
Static and Dynamic data structures.....................................................................................................15
1
, Arrays
Array: A data structure for storing a finite, ordered set of data of the same data type within a single
identifier.
Single-Dimensional Array
Single-Dimensional Array: An array where each data item can be located using a single
index.
Example = {“George”, “Sue”, “Mo”} 0 1 2
It can be visualised with the following table: “George” “Sue” “Mo”
Multi-Dimensional Array
Multi-Dimensional Array: An array where each data item is located using multiple indices.
Example = [{“Rachel”,1,0.5},{“Emma”,4,1.2},{“Bob”,9,0.9}]
0 1 2
It can be visualised with the following table: 0 “Rachel” 1 0.1
E.g., Example(1,2) would return 9 and Example(0,2) would 1 “Emma” 4 1.2
return “Bob” 2 “Bob” 9 0.9
Fields, records and files
Binary File: An organised collection of records where data is stored in binary.
Fields: A single item of data.
Records: A data structure that stores multiple fields, organised based on attributes, within a single
line of a file.
Text file: An organised collection of records where data is stored in human-readable characters.
Basically, information is stored by computers as a series of files. Each file is made up of records
which are composed of a number of fields.
Abstract Data types/structures
Abstract data types can easily be shown in graphical form, and it is not hard to understand
how to perform operations such as adding, deleting or counting elements in each structure.
An abstract data type (ADT) is a logical description of how the data is viewed and the
operations that can be performed on it, but how this is to be done is not necessarily known
to the user.
o This is an example of information hiding – by providing this level of abstraction we
are creating an encapsulation around the data, hiding the details of implementation
from the user.
Examples of this are: Queues, lists, stacks, hash tables, dictionaries, graphs, trees, and vectors.
Queues
A queue is a “First In First Out” (FIFO) data structure.
2
Data Structures: A data structure is a format used to store, organise and manage data in a way that
allows efficient access and modification for the needs of the program.
Contents
Arrays....................................................................................................................................................2
Single-Dimensional Array...................................................................................................................2
Multi-Dimensional Array....................................................................................................................2
Fields, records and files.........................................................................................................................2
Abstract Data types/structures..............................................................................................................2
Queues...............................................................................................................................................2
Linear Queues................................................................................................................................3
Circular Queues.............................................................................................................................3
Priority Queues..............................................................................................................................4
Lists....................................................................................................................................................4
Stacks.................................................................................................................................................5
Overflow and Underflow...............................................................................................................5
Call Stacks......................................................................................................................................5
Hash tables........................................................................................................................................6
Dictionaries........................................................................................................................................7
Graphs...............................................................................................................................................7
Adjacency Matrix...........................................................................................................................8
Adjacency List................................................................................................................................9
Trees..................................................................................................................................................9
Rooted Trees................................................................................................................................10
Binary Trees.................................................................................................................................10
Vectors.............................................................................................................................................11
Visualisation of a Vector..............................................................................................................12
Convex combination of two vectors............................................................................................13
Dot or scalar product...................................................................................................................13
Static and Dynamic data structures.....................................................................................................15
1
, Arrays
Array: A data structure for storing a finite, ordered set of data of the same data type within a single
identifier.
Single-Dimensional Array
Single-Dimensional Array: An array where each data item can be located using a single
index.
Example = {“George”, “Sue”, “Mo”} 0 1 2
It can be visualised with the following table: “George” “Sue” “Mo”
Multi-Dimensional Array
Multi-Dimensional Array: An array where each data item is located using multiple indices.
Example = [{“Rachel”,1,0.5},{“Emma”,4,1.2},{“Bob”,9,0.9}]
0 1 2
It can be visualised with the following table: 0 “Rachel” 1 0.1
E.g., Example(1,2) would return 9 and Example(0,2) would 1 “Emma” 4 1.2
return “Bob” 2 “Bob” 9 0.9
Fields, records and files
Binary File: An organised collection of records where data is stored in binary.
Fields: A single item of data.
Records: A data structure that stores multiple fields, organised based on attributes, within a single
line of a file.
Text file: An organised collection of records where data is stored in human-readable characters.
Basically, information is stored by computers as a series of files. Each file is made up of records
which are composed of a number of fields.
Abstract Data types/structures
Abstract data types can easily be shown in graphical form, and it is not hard to understand
how to perform operations such as adding, deleting or counting elements in each structure.
An abstract data type (ADT) is a logical description of how the data is viewed and the
operations that can be performed on it, but how this is to be done is not necessarily known
to the user.
o This is an example of information hiding – by providing this level of abstraction we
are creating an encapsulation around the data, hiding the details of implementation
from the user.
Examples of this are: Queues, lists, stacks, hash tables, dictionaries, graphs, trees, and vectors.
Queues
A queue is a “First In First Out” (FIFO) data structure.
2
