data structures

[ 1.4.2 ]

what is an array?

what is an array?

an ordered, finite set of elements of a single type

what is a one-dimensional array?

a linear array

what is a two-dimensional array?

• it can be visualised as a table/spreadsheet

• when searching an array, first go down the rows and then across the columns

what is a three-dimensional array?

• it can be visualised as a multi-page spreadsheet

• an element is represented by: myArray[x][y][z]

  • x = array number,  y = row number,  z = column number

what is a list?

• a data structure that consists of a number of ordered items

• items can occur more than once

• data is stored in non-contiguous locations

• can contain items of different data types

what is the function of the list operation isEmpty() ?

checks if the list is empty

what is the function of the list operation append(value) ?

adds a new value to the end of the list

what is the function of the list operation remove(value) ?

removes the value the first time it occurs in the list

what is the function of the list operation search(value) ?

searches for a value in the list

what is the function of the list operation length() ?

returns the length of the list

what is the function of the list operation index(value) ?

returns the position of the item

what is the function of the list operation insert(position, value) ?

inserts a value at a given position

what is the function of the list operation pop() ?

returns and removes the last item in the list

what is the function of the list operation pop(position) ?

returns and removes the item at the given position

what is a record?

• more commonly referred to as a row in a file

• a record is made up of fields, and is widely used in databases

• each field in a record can be identified by recordName.fieldName

• when a record is created, the program must declare the data type for each field

what is a tuple?

• an ordered set of values of any data type

• immutable and static, meaning it cannot be changed

• initialised with regular brackets rather than square brackets

what is a queue?

• a first in first out (FIFO) data structure

• items are added to the end and are removed from the front of the queue

• uses two pointers (head and tail)

• used in printers, keyboards and simulators

what is a linear queue?

• items are added into the next available space, starting from the front

• items are removed from the front of the queue

• uses two pointers: pointing to the front/back of the queue

• uses space inefficiently, as positions from which data has been removed cannot be reused

what is a circular queue?

• a queue that uses a rear pointer

• it loops back to the front of the queue and utilises empty space at the front, if it’s available

• harder to implement that a linear queue

what is the function of the queue operation enQueue(value) ?

adds a new item to the end of the queue

what is the function of the queue operation deQueue() ?

removes and returns the item from the front of the queue

what is the function of the queue operation isEmpty() ?

checks if the queue is empty

what is the function of the queue operation isFull() ?

checks if the queue is full

what is a linked list?

• a dynamic data structure used to hold an ordered sequence

• items do not have to be in contiguous data locations

• each item is called a node, and contains a data field and a link (pointer field)

• a linked list must also store a start index/pointer, to identify the beginning of the list

what is held in the data field of an item in a linked list?

contains the actual data associated with the list

what is held in the pointer field of an item in a linked list?

contains the address of the next item in the list

steps to traverse a linked list.

• go to the first position, indicated by the start pointer

• from the first position, read the next pointer value

• follow this pointer to the next value, and continue until you reach the desired item

what is a stack?

• a last in first out (LIFO) data structure

• items can only be popped/pushed from the top of the stack

• used to reverse actions, (eg. back buttons/undo buttons)

• can be implemented as a static or dynamic structure

• uses one pointer (head pointer)

what is a tree?

a connected graph, with a root and child nodes

what is an edge?

an edge connects two nodes together (also called a branch/arc)

what is a node?

an item in a tree/graph

what is a root?

a node with no incoming edges

what is a child node?

a node with incoming edges

what is a parent node?

a node with outgoing edges

what is a subtree?

a part of a tree consisting of a parent and children

what is a leaf?

a node with no children

what are the two ways to traverse a tree?

trees can be traversed by a depth-first search (DFS) or a breadth-first search (BFS)

what is a graph?

• a set of vertices/nodes connected by edges/arcs

• implemented using an adjacency matrix or an adjacency list

what is a directed graph?

a graph where edges are assigned a direction

what is a undirected graph?

a graph where edges can be traversed in both directions

what is a weighted graph?

a graph where each arc has a cost attached to it

what is a hash table?

• a data structure which holds key-value pairs

• they are used in situations where a lot of data needs to be stored with constant access times

  • e.g in caches and databases

• a good hashing algorithm should…

  • be calculated quickly

  • have a low rate of collisions

  • use as little memory as possible

what is a hashing function?

a function applied to an item to determine a hash value (a unique index in the hash table)

what is a collision and how are they handled?

• collisions occur if two keys produce the same hash value

• in this situation the item is usually placed in the next available location (open addressing)

• to find the item later, the hashing function delivers a start position, from which a linear search can be applied (linear probing)

what is the drawback of open addressing and how can it be handled?

• open addressing can result in clustering, where several positions are filled around common collision values

• can be handled by using…

  • a 2D hash table

  • an overflow table for hash values where collisions have occurred

what is a binary search tree?

• a type of tree where each node has a maximum of two child nodes

• stores information in a way that is easy to search through

• commonly represented by storing each node with a left pointer and a right pointer

what are the three types of depth-first search?

• pre-order

• in-order

• post-order

how do you traverse a binary search tree using breadth-first search?

• first visit the top level/root node

• then search all the nodes at the next depth level down

• continue until you have searched all the leaf nodes of the tree

how do you traverse a binary search tree using pre-order traversal?

• it follows the order:

  • root node → left subtree → right subtree

• using the outline method, nodes are traversed in the order in which you pass them on the left

how do you traverse a binary search tree using in-order traversal?

• follows the order:

  • left subtree → root node → right subtree

• using the outline method, nodes are traversed in the order in which you pass under them

• useful for traversing the nodes in sequential order by size

how do you traverse a binary search tree using post-order traversal?

• follows the order

  • left subtree → right subtree → root node

• using the outline method, nodes are traversed in the order in which they are passed on the right

how is backtracking used in a depth-first traversal?

when a leaf node is reached, the traversal backtracks to the leaf’s parent node // to the last node with unvisited children