data structures

static data structure

section of memory is allocated at declaration

dynamic data structures

can change the amount of memory allocated after declaring the variable

advantages of dynamic data structures

no wasted memory, no limit to the number of items that can be added, resources allocated as they are needed

disadvantages of dynamic data strucutres

additional memory needed for pointers, can result in memory leak, can take longer to access an item directly

define array

a data structure for storing a finite, ordered set of data of the same data type within a single identifier

how does an array work

allocated a sequential run of memory locations, pointer to the first element

adding item to linear queue

check queue isn’t full, add 1 to the rear pointer, add item to position indicated by rear pointer

remove element from linear queue

check queue isn’t empty, add 1 to head pointer

add item to circular queue

check the queue is not already full, compare the value of the rear pointer with the max size of the array, if equal then rear pointer becomes zero, otherwise, add one to the rear pointer, insert new item in position indicated by rear pointer

dequeue circular queue

check queue is not empty, if empty deal with underflow error. if not, dequeue the front item in the queue. if head pointer = max length, set to 0. increment head pointer

how priority queue decides where new item should be added

check if the item indicated by the rear pointer has a higher priority than the previous item, if it does, swap with the previous item and then compare with the one before it. if it does not have a higher priority, increment pointer

priority queue

items are assigned a priority, items with the highest priority are dequeued before low priority items, if they have the same priority, first in first out

advantage of circular queue

avoids wasted space and prevents unnecessary shifting

test for empty stack

top of stack = bottom of stack

test for full stack

top of stack = limit

how can a stack be used to reverse the order of items in a queue

dequeue each value from the queue, starting at the beginning and add them to the stack. pop the values from teh stack and add them back to the queue

advantage and disadvantage of adjacency matrix

stores every possible edge between nodes, even those that doen’’t exist, almost half of the matrix is repeated data so memory insufficient. allows a specific edge to be queried very quickly as it can be looked up by its row and column so time efficient

adjacency list advantages and disadvantages

only stores edges that exist in the graph so memory efficient. slow to query as each item in a list must be searched sequentially until the desired edge is found so time inefficient

define tree

a tree is a connected, undirected graph with no cycles

rooted tree

a tree with a root node from which all other nodes stem

binary tree

a rooted tree in which each parent node has no more than two child nodes

leaf

a node with no children

collision

when two ore more different keys hash to the same hash value

open addressing

going to the next open address

closed hashing

don’t go over codomain, limit to how far out value can be

steps of adding record to a hash table

hash function is applied to the key value and stored in a memory location corresponding its hash value. if another value is already at that location,m it will be stored in the next location. there is a limit to the number of incementations to the memory location

how can vectors be represented

list of numbers, function, point in space, dictionary, 1d array, an arrow

define dictionary

a collection of key value pairs

application of dictionary

dictionary-based compression

state two advantages of using RPN instread of infix notation to represent an expression

simpler for a computer to evaluate. simper to code algorithm. do not need brackets. operators appear in the order required for computation. no need to backtrack when evaluating

how can a single stack be used to evaluate an RPN expression

starting at the LHS of the expression, push operands to the stack, each time an operator is reached, pop two values off the stack and apply the operator to them. push result to the stack. when the end of the expression is reached the top item of the stack is the result.

how to add item to priority queue

starting with the item at the rear of the queue move each item back one place in the array until you reach et he start of the queue or find an item with the same or higher priority than the item to add. add the new item in the position before that item