1.4.2 Data Structures Flashcards
Arrays
An ordered, finite set of elements of a single type
You can make an array of tuples
Index of arrays
0-based
Find a value with arrayname[index]
arrayname[row,column] for 2d
Multi-dimensional arrays
You can have any number of dimensions
Tuples
An ordered set of values, can have elements of mixed type and it is immutable (elements cannot change)
Records
Composed of a fixed number of fields of different data types
Access a value with the name of the record
Dynamic data structure
They can change size when required
Static data structure
They cannot change size
Abstract Data Type
A logical description of how we view the data and possible operations
Where does the rear of the queue start at?
-1
isFull() pseudocode
function isFull() if size == maxSize: return True else: return False end if end function
isEmpty() pseudocode
function isEmpty() if size == 0; return True: else: return False end if end function
enQueue() pseudocode
function enQueue() if size < maxSize: rear ++ rear = rear MOD maxSize Q[rear] = item size ++ else: print (queue is full) end if end function
deQueue() pseudocode
function deQueue() if size == 0: item = null print (queue is empty) else: item = Q[front] front = (front + 1) MOD maxSize size -- end if return item end function
Priority Queue
Items are ordered in a queue first based on their priority and then based on FIFO, items move backward to allow a higher priority item to join.
Hash Table
A data structure where keys are mapped to index values, used where faster searching is needed e.g. police records
Collisions/synonyms and how to deal with them
When an algorithm generates the same address for different primary keys
Methods include putting the value in the next free location or incrementing how far you skip by
Searching in a hash table
Apply the hash function to the key and first check that position, if not increment by 1 and check each
If the original position is empty or you cycle back the value isn’t in the table
Mid-square hashing algorithm
Square the number, extract some portion of the resulting digits (likely the middle), then mod by the size of the table
Folding hashing algorithm
Divide the item into equal sized pieces (excluding maybe the last piece, sum them and carry out the mod with the size of the table
Hashing alphanumeric data
Take the ASCII of each character, sum them and mod with the size
Hash table deletion
When a value is deleted, a placeholder is used to represent that a value has not been deleted.
Lists
A dynamic data type containing a number of ordered items that can be repeated. The elements are stored non-contiguously on the heap and can be of different types
Linked list
A dynamic abstract data structure which is implemented as an array and pointers
What is a node composed of linked list?
The data and a pointer to the next node
Linked list pointers
A start pointer identifies the first element in a list, a nextfree pointer highlights the next free space, the last node has null
Stack
A collection of elements that are retrieved on a last-in first-out basis
Stack variables
Top and maxSize
Top starts at -1
How to reverse elements?
Push them all onto a stack and then pop them off
Stack isFull()
function isFull() if (top + 1) == maxSize: return True else: return False end if end function
Stack isEmpty()
function isEmpty() if top == -1: return True else: return False end if end function
Stack push()
procedure push(newItem) if (top + 1) == maxSize print (stack is full) else: top ++ stack[top] = newItem end if end procedure
Stack pop
function pop() if top == -1: print (stack is empty) item = null else: item = stack[top] top -- end if return item end function
Graph
A set of vertices connected by edges or arcs
Adjacency Matrix of a weighted graph
Put the weight of the connecting edge and leave boxes blank instead of writing 0s
Adjacency matrix advantages and disadvantages
+ convenient to work with, easy to add edges
- wastes a lot of memory space if nodes have few edges
Adjacency list
A list of nodes pointing to their adjacent nodes
For weighted it has {node:weight}
Tree
A connected, undirected graph with no cycles
Root
The node at the top of the tree with no parents
Child
A node below a parent node in a tree
Parent
A node above one or more children
Subtree
A part of a tree which itself is a tree
Leaf
A node in a tree with no children
Binary Tree
A rooted tree in which each node has a maximum of two children, each node has a left and a right pointer (-1 if there is no child on that side)
Building a binary tree
Start from the root each time and trace to the left if the value is smaller than the current node and to the right if it is larger
Pre-order searching
Visit the root then follow the left subtree then the right
In-order searching
Follow the left subtree then visit the root then follow the right
Post-order searching
Traverse the left subtree then the right then visit the root node
Deleting a leaf node
Just remove the node
Deleting a node with one child
The child replaces the deleted parent
Deleting a node with two children
Repeatedly add 1 to the value of the node until you find the value of another node, which will replace the deleted node
Binary tree uses
Mainly used for searching as you often have to rebuild the tree after deletion
Breadth-first traversal
Traverses the root then the children of the root left to right then their children left to right
Depth first traversal
Starts at the bottom left and at each leaf it will move up to the latest decision point and go right where it hasn’t been done before
Record declaration
Name = record DataType FieldName DataType FieldName … End record
Acessing a record
recordName.fieldName
Adding a value to the end of a list
listName.append(value)
Finding the first index of a value in a list
listName.index(value)
List remove and return from a position
listName.pop(index)
Removing the first instance of a value from a list
listName.remove(value)
Initialising a tuple
tupleName = (“value1”, “value2”, …)
Accessed like an array
Stack peek()
Returns the top element if the stack isn’t empty
