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
