# 4.2 Fundamentals of data structures

## 4.2.1 Data structures and abstract data types

### 4.2.1.1 Data structures

Content

Be familiar with the concept of data structures.

It may be helpful to set the concept of a data structure in various contexts that students may already be familiar with. It may also be helpful to suggest/demonstrate how data structures could be used in a practical setting.

### 4.2.1.2 Single- and multi-dimensional arrays (or equivalent)

Content

Use arrays (or equivalent) in the design of solutions to simple problems.

A one-dimensional array is a useful way of representing a vector. A two-dimensional array is a useful way of representing a matrix. More generally, an n-dimensional array is a set of elements with the same data type that are indexed by a tuple of n integers, where a tuple is an ordered list of elements.

### 4.2.1.3 Fields, records and files

Content

Be able to read/write from/to a text file.

Be able to read/write data from/to a binary (non-text) file.

### 4.2.1.4 Abstract data types/data structures

Content

Be familiar with the concept and uses of a:

• queue
• stack
• graph
• tree
• hash table
• dictionary
• vector.

Be able to use these abstract data types and their equivalent data structures in simple contexts.

Students should also be familiar with methods for representing them when a programming language does not support these structures as built-in types.

Be able to distinguish between static and dynamic structures and compare their uses, as well as explaining the advantages and disadvantages of each.

Describe the creation and maintenance of data within:

• queues (linear, circular, priority)
• stacks
• hash tables.

## 4.2.2 Queues

### 4.2.2.1 Queues

Content

Be able to describe and apply the following to linear queues, circular queues and priority queues:

• remove an item
• test for an empty queue
• test for a full queue.

## 4.2.3 Stacks

### 4.2.3.1 Stacks

Content

Be able to describe and apply the following operations:

• push
• pop
• peek or top
• test for empty stack
• test for stack full.

Peek or top returns the value of the top element without removing it.

## 4.2.4 Graphs

### 4.2.4.1 Graphs

Content

Be aware of a graph as a data structure used to represent more complex relationships.

Be familiar with typical uses for graphs.

Be able to explain the terms:

• graph
• weighted graph
• vertex/node
• edge/arc
• undirected graph
• directed graph.

Know how an adjacency matrix and an adjacency list may be used to represent a graph.

Be able to compare the use of adjacency matrices and adjacency lists.

## 4.2.5 Trees

### 4.2.5.1 Trees (including binary trees)

Content

Know that a tree is a connected, undirected graph with no cycles.

Note that a tree does not have to have a root.

Know that a rooted tree is a tree in which one vertex has been designated as the root. A rooted tree has parent-child relationships between nodes. The root is the only node with no parent and all other nodes are descendants of the root.

Know that a binary tree is a rooted tree in which each node has at most two children.

A common application of a binary tree is as a binary search tree.

Be familiar with typical uses for rooted trees.

## 4.2.6 Hash tables

### 4.2.6.1 Hash tables

Content

Be familiar with the concept of a hash table and its uses.

A hash table is a data structure that creates a mapping between keys and values.

Be able to apply simple hashing algorithms.

Know what is meant by a collision and how collisions are handled using rehashing.

A collision occurs when two key values compute the same hash.

## 4.2.7 Dictionaries

### 4.2.7.1 Dictionaries

Content

Be familiar with the concept of a dictionary.

A collection of key-value pairs in which the value is accessed via the associated key.

Be familiar with simple applications of dictionaries, for example information retrieval, and have experience of using a dictionary data structure in a programming language.

Information retrieval:

For example, the document 'The green, green grass grows' would be represented by the dictionary:

{‘grass’ : 1, ‘green’ : 2, ‘grows’ : 1, ‘the’ : 1} ignoring letter case.

## 4.2.8 Vectors

### 4.2.8.1 Vectors

Content

Be familiar with the concept of a vector and the following notations for specifying a vector:

• [2.0, 3.14159, -1.0, 2.718281828]
• 4-vector over ℝ written as ℝ4
• function interpretation
• 0 ↦ 2.0
• 1 ↦ 3.14159
• 2 ↦ -1.0
• 3 ↦ 2.718281828
• ↦ means maps to

That all the entries must be drawn from the same field, eg ℝ.

A vector can be represented as a list of numbers, as a function and as a way of representing a geometric point in space.

A dictionary is a useful way of representing a vector if a vector is viewed as a function.

f : S →

the set S = {0,1,2,3} and the co-domain, ℝ, the set of Reals

For example, in Python the 4-vector example could be represented as a dictionary as follows:

{0:2.0, 1:3.14159, 2:-1.0, 3:2.718281828}

Dictionary representation of a vector.

See above.

List representation of a vector.

For example, in Python, a 2-vector over ℝ would be written as [2.0,3.0].

1-D array representation of a vector.

For example in VB.Net, a 4-vector over ℝ would be written as Dim example(3) As Single.

Visualising a vector as an arrow.

For example a 2-vector [2.0, 3.0] over ℝ can be represented by an arrow with its tail at the origin and its head at (2.0, 3.0).

Know that vector addition achieves translation and scalar-vector multiplication achieves scaling.

Convex combination of two vectors, u and v.

Is an expression of the form αu + βv where α, β ≥ 0 and α + β = 1

Dot or scalar product of two vectors.

The dot product of two vectors, u and v,

u = [u1, …., un ] and v = [v1, ….., vn ] is

uv = u1v1 + u2v2 + …… + unvn

Applications of dot product.

Finding the angle between two vectors.