1.4.2 - Data Structures

What is an array

An ordered finite set of elements in one type.

A 1D array is a linear array - the first element is considered to be at position 0

A 2D array can be visualised as a table or spreadsheet. To find an element in a 2D array the columns and rows must be traversed

A 3D array can be visualised as a multi-page spreadsheet which can effectively be thought as multiple 2D arrays

To print an array = print(3Darray[page,row,column]

Define a list

How do lists differ from arrays

A data structure consisting of a number of ordered items where the items can occur more than once.

Lists can contain more than one data type and items do not need to be stored in positions next to other items

What is a tuple

The same as an array except it is immutable - (It cannot be changed no items can be added or removed

Created using circle brackets instead of square

What is a linked list

A dynamic data structure used to hold an ordered sequence. Items (Known as nodes) do not have to be in contiguous locations.

Each node contains a data field alongside another address called a pointer. The data field holds the address of the node and the pointer holds the address of the next node in the list.

There is also 2 more pointers : one pointer indicates the start of the list and the other the next available space in the list

How is an item accessed in a linked list

The whole list needs to be traversed - each node will be visited and their data printed until it reaches the desired item or the end which is signified by the pointer = null.

Unlike an array an item cannot be directly accessed basically and linked lists use more memory as pointers must be stored as well

How is an item removed in a linked list

What are the implications of this

Pointers are updated to not point towards the node that is being removed so that when the list is traversed it is not accessed

However the node is never actually removed and so it ends up being a waste of memory as it is still technically in the list

What are the types of graphs

Directed graph - edges can only be traversed in one direction

Undirected graph - edges can be traversed in both directions

Weighted graph - A cost is attached to each edge

What is a stack

A LIFO data structure (Last in first out). Which means itemscan only be added to or removed from the top of the stack

A stack can be implemented as a static or a dynamic data structure

A stack has a pointer which points towards the top of the stack

Differences between a dynamic and a static stack

A dynamic stack will increase it’s size to be able to accommodate more items while a static stack will have a set size defined when it is created

This means although they both experience underflow errors only static stacks will have an overflow error

But static stacks are easier to implement and use memory more efficiently

How can a stack be manipulated

Using the following commands

isEmpty() - checks if stack is empty by checking value of top pointer

push(value) - Adds a value to the top of the stack

peek() - Returns the top value from the stack

pop() - Removes and returns the top item in the stack

size() - Returns the size of the stack

isFull() - checks if stack is full by comparing top pointer by stack size

What is a queue

FIFO data structure (First in first out) - items are ended to the end of the list and removed from the front

What are the types of queue

Linear queue

Circular queue

What is a linear queue

A data structure consisting of an array - starting from the front items are added to the next available space in the queue. Then items are removed from the the front of the queue

A linear queue uses 2 pointers - one points to the last element and the other points towards the front of the queue

However while relatively easy to implement linear queues are quite ineffective as when items are removed they leave an empty space which cannot be filled as items must be added to the end of the queue

What is a circular queue

While still FIFO a circular queue aims to solve the problem of the ineffective linear queue however it is harder to implement

Once the rear pointer is equal to the max size of the queue when another item is added it can loop back round to the front of the queue and store items there provided there is no item at the front of the queue

There are two pointers - the rear pointer (Last element in the queue) and the front pointer (element at the front of the queue)

What are the commands for a queue

enQueue(Value) - Adds a new item to the end of the queue then increments rear pointer

deQueue() - Removes item from front of the queue and then increments front point

isEmpty() - Checks if queue is empty by comparing rear and front pointer

isFull() - checks if queue is full by comparing back pointer and queue size in linear. In circular it checks by comparing the back pointer + 1 and then front pointer

What is a tree

A connected form of graph

With different nodes with different names

What are the types of nodes in a tree

Node - any item in the tree

Edge/ branch/ arc connects two nodes together

Root - A single node with no incoming nodes

Parent - a node with outgoing edges

Child - a node with incoming edges

Leaf - a node with no children

What is a binary tree

A type of tree where each node has a max of two children

Can be represented by storing each node with a left and a right pointer

How is a binary tree created

If the node is smaller than the current node is moves to the left if it is bigger it moves to the right of the node

How can a tree be traversed

Then explain each of them

Pre order - starting from the root - left subtree is fully explored then the right always attempting to traverse the left node first. Nodes are ‘explored’ whenever they are visited

Post order - Nodes are visited in the order left sub tree to right subtree starting from the smallest left node

In order - starting from the furthest left roots are explored left to right generating a perfect ascending order

What is a hash table

Problems

Uses

An array coupled with a hash function. The data which is inputted is converted into hash and outputted. The hash function will map the key to an index in the hash table

Each inputted is given an unique hash however there is a chance that two inputs are given the same hash value (A collision). A good hash function will have a low chance of collisions but if it does occur the item will be typically placed in the next location along - (Collision resolution)

Normally used for indexing as they provide a fast / constant access to data as there is a one to one relationship with the address they are stored at