4.2 data structures Flashcards
how do dynamic ds work
ds = data structure
allocate and deallocate memory from the heap
heap an area of memory used specifically for this purpose
differences between dynamic and static data structures
- static ds have a fixed size;
- dynamic ds only take up the amt of storage space required for the actual data;
- dynamic ds require pointers to the next item;
- static ds store data in consecutive memory locations;
advantages of dynamic data structures
- no wasted memory;
- no limit on number of items that can be added;
- resources only allocated as they are needed;
disadvantages of dynamic data structures
- additional memory needed for pointers;
- can result in memory leak;
- can take longer to access an item directly;
what is a dictionary
a collection of key-value pairs in which the value is accessed via the associated key;
circular queue advantage
- items in a linear queue are all shuffled forward when an item is DELETED;
- this means circular queues are more time efficient;
- free spaces can be reused
when to use a linear queue over a circular queue
when a queue is small in size
attribute of a circular queue
a pointer to the front;
what is a priority queue
system that aims to deal with tasks on FIFO basis, but after giving them a priority order
remove an item from a circular queue
method
- check the queue is empty;
- compare the value of the front pointer with the max size of the array;
- if equal, then front pointer becomes 1;
- otherwise, add 1 to the front pointer;
adding an item to a linear queue
method
- check that the queue is not already full;
- add 1 to the value of the rear pointer;
- then add the new item to the position indicated by the rear pointer;
adding an item to a priority queue
method
- starting with the item at the rear of the queue, move each item back one piece in the array;
- until you find an item with the same OR higher priority than the item to add;
- add the new item in the position before that item;
what is a tree
connected, undirected graph; with no cycles;
what is a rooted tree
- a tree with one vertex designated as the root;
- has a parent-child relationship between the nodes;
- root is the only node with no parent and all other nodes are descendants of the root;
what is a binary tree
- rooted tree;
- where each node has at most two child nodes;
common application of a binary tree
binary search tree;
pre-order traversal
follow the left of the node - go round and underneath tree, whenever line touches left of node, visit
in-order traversal
follow the bottom of the node - go round and underneath tree, whenever line touches bottom of node, visit
post-order traversal
follow the right of the node - go round and underneath tree, whenever line touches right of node, visit
stack frame components
- local variables;
- return address;
- parameters;
- register values;
peeking a stack
what does it do
returns the value of the top element without removing it
implemening repeat and undo operations with one stack
method
- stack is used to store the actions;
- each time an action is completed it is pushed onto the TOP of the stack;
- unless it is an undo action;
- when repeat action is used, the result of peek function is used to indicate the action to complete;
- when undo action is used, the top item is popped from the stack of actions;
reverse order of items in a queue with a single stack
method
- (until queue empty) repeatedly remove (the front item) from the queue and push it on to the stack
- (until stack empty) repeatedly pop items from the stack and add them to (the rear of) the queue
what does a front pointer do
points to the next item to remove
what does a rear pointer do
points to the last item added
overflow
trying to push onto a stack that is full
underflow
trying to pop from an empty stack
what is a hash table
a data structure that creates a mapping between keys and values;
why is a hash table a suitable choice to implement a dictionary?
allows direct access to the value being looked up;
adding a record to a hash table
method
- hash algorithm applied;
- to key value;
- result is location in table where the record should be stored;
- if location is not empty;
- then use next free location;
rehashing
method
- larger hash table is created;
- each value in the existing table is inserted into the new table;
- in a position determined by a new hashing algorithm;
when does a collision occur in a hash table
when two key values compute the same hash;
when is it not suitable to use a hash table?
- when searches need to be done based on multiple different properties of an item;
finding an item in a hash table
method
- apply hash function to the specified ID;
- this will give the position in the array where that item has been stored;
- if another item is in that position then use a method to check if a collision occurred when adding items to hash table
- if location is empty, then the item does not exist;
when to use an adjacency matrix over an adjacency list
- when graph/matrix is not sparse;
- when edges are frequently changed;
- when presence of specific edges needs to be tested frequently;
what is a weighted graph
a graph where each edge has a value associated with it
when to use an adjacency list over an adjacency matrix?
- when graph/matrix is sparse;
- when edges are rarely changed;
- when presence/absence of specific edges does not need to be tested;
what is a stack?
- a FIFO ds where new items are added to the top of the stack;
- and items are removed from the top of the stack;
uses of stacks in a computing system
- call stack
- back buttons in a web browser
- undo buttons in an editor
hashing algorithm
method
- an algorithm is applied to the primary key;
- to generate an address;
- where the data is stored;
improving the performance of a hash table
- increase the size of the table and rehash all entries;
- so that the load factor is reduced and there are fewer collisions;
effect of multiplying a vector by a scalar
the vector is scaled in size, but does not change direction
