1.4 Data Types, Data Structures and Algorithms

Array

Holds an ordered list of elements of the same data type

Mutable

How can a 2D array be visualised?

A table with rows and columns

Record

Collection of related fields (variables)

Each field can have a different data type

Used in databases

Lists

Mutable

Can have multiple data types

Non-contiguous (not ordered in memory)

Tuples

Immutable

Can have multiple data types

Ordered

Linked lists

Each element is called a node

Each node has an index, data and a pointer

Nodes are not ordered

Pointers determine where the next node is from the start node

Circular linked list

When the last node points to the first node instead of null

Continuous loop

Round Robin

3 types of graph

• Undirected graph - edges can be traversed in any direction

• Directed graph - edges can only be traversed in one direction

• Weighted graph - edges have a cost (e.g. distance or time)

How can computers process graphs?

• Adjacency matrixes - tables with 1s and 0s

• Adjacency lists - lists all nodes connected to a node

Stacks

LIFO

Items can only be added and removed from the top of the stack

POP

PEEK
PUSH

Stack overflow

Error when trying to push a new item onto a full stack

Queues

FIFO

Items are removed from the front of the queue

Circular queues

End of a queue wraps back to the front of the queue

Solves problem of wasted space when items are removed in a linear queue

Front pointer + end pointer

Tree

A hierarchal undirected graph that has a root node, parents and children

Represents folders, family trees and organisations’ hierarchy

Binary tree

A type of tree that can only have two children nodes under each parent normally called: Left child and Right child

Hash table

Implements a dictionary structure

Uses a hash function to calculate an index in an array for data

Uses a key (data) then applies the function to find the numerical hash (index) for it

Collisions

When 2 keys hash to the same index

Collision handling methods:

• Open addressing - data is placed in the next available index

• Chaining - an overflow array is used to store the data, a linked list is used

Breadth-first search

Uses a queue structure (FIFO)

Traversed horizontally

Starts at root node and looks at children 1 step away

Enqueues any connecting nodes and changes current node when the node is added to the final list

Depth-first search

Uses a stack structure (LIFO)

Nodes are popped and pushed as graph is traversed vertically

Push every connected node to the current node on the stack

Pop the stack and add the removed item into the final list