Comparing data structures
- compare static or dynamic (and why this is applicable)
- compare contiguous memory locations or non-contiguous memory locations (and why this is applicable)
- compare how and how quickly items are accessed (and why this is applicable)
Binary tree searches
- write comparison
- write result (go left, go right)
- repeat
Data structure definitions
- is static or is dynamic
- how is data held (2 points)
Adding Nodes Linked Lists
- new item is placed in address at next free
- next free is incremented
- penultimate node’s pointer is adjusted to point to new item’s pointer
- new item’s pointer is set to null to indicate that it is at the end of the list
Statistic data structure definition
- size is fixed at creation
- size can’t change during processing
Dynamic data structure definition
- size can change as needed
- during processing
Adjacency List over Matrix
- graph is sparse
- edges are rarely changed
- prescence/abscence of specific edges don’t need to be noted
Tree Properties
- connected
- undirected
- with no cycles
How a value is stored in a hash table
- hashing algorithm is applied to the key
- result is the address in which the value is stored
- in the event of a collision (different keys generating the same address)
- the value is placed in the next address
Purpose of rehashing
- large number of possible addresses in a hash table are filled
- this makes searching and management inefficient
Rehashing Steps
- larger hash table is created
- each value in the existing table added to the new table using a hashing algorithm
how are collisions resolved
item has the same address as _, add one to the address until a free space is found
stack for back button
-A (data structure) that operates on a first in last out basis
(1)
-When going back a page you want to go back to the last
page visited/when displaying the history we want to start
with the most recent first (1)
dynamic data structure - advantages
No wasted memory;
Can grow as more data is added to the data structure // no limit on number of
items that can be added (except due to hardware limitations);
Resources only allocated as they are needed (with static data structures they are
allocated at creation even if not needed until later);
dynamic data structure - disadvantages
Additional memory needed for pointers;
Can result in memory leak (if memory that is no longer needed is not returned to
the heap);
Can take longer to access an item directly (for data structures that allow this);
describing adding to (static) queue
Check that the queue is not already ful (rear = max)l;
(if it isn’t) then add 1 to the value of the rear pointer;
then add the new item to the position indicated by the rear pointer;
describing removing from (static) queue
check that the queue is not empty (front = -1)
add 1 to the value of the front/start pointer
return the value at the position indicated by the front pointer - 1
adding item priority queue
Starting with the item at the rear of the queue move each item back one place in the array;
Until you (reach the start of the queue or) find an item with the same or higher priority than
the item to add;
NE. same priority
NE. higher priority
Add the new item in the position before that item
