data structures (stack, queue, circular queue, tree, linked list) Flashcards
what order does the 3 tree traversal types traverse in
pre-order: root-left-right
in-order: left-root-right
post-order: left-right-root
queue
- operations performed in FIFO (first in first out) order
- with methods enqueue & dequeue
circular vs linear queue
circular: tail of queue joins to the head of queue when queue is full
linear: no such wraparound
circular: fixed size (won’t exceed memory capacity)
linear: grows/shrinks in size as items are enqueued/dequeued
circular: faster than linear queue of same size
stack
- operations performed in LIFO (last in first out) order
- with methods push & pop
whats a balanced tree?
tree with minimum possible height (eg using median of data as the root node)
advantage of BST? (may be outdated)
- BST can maintain data in sorted order :. easier to iterate through
(may be outdated)
- enables use of binary search on data structure that is guaranteed to remain sorted
- adding elements into BST has a time complexity of O(log n), vs append-and-sort operations for an array which hv time complexity of O(n log n) using merge sort
- mostly-sorted arrays are worst-case scenario for quick sort, resulting in O(n2) time complexity
disadvantages of BST
- as arrangement of nodes not sorted, nodes of BST cnnt be accessed by index
- BST may bcm unbalanced in course of usage & require balancing to maintain optimal perf
can i implement BST using hash table?
no.
BST iterates over vals (in sorted order) bc nodes fllw a strict sorting rule/arranged acc to specific rules
AND hash table cnnt bc it doesnt rec keys in order
purpose of traversing through linked list (with numbers & mathematical operations as node data)
to traverse through linked list, concatenating each node’s value to the next
linked list
- linear collection of data elements whose order is not given by their physical placement in memory
- it makes use of pointers to connect one element to another, regardless of their location in memory
- the joined collection of nodes forms a sequence
static array > linked list (assume dynamic)
- more efficient, bc array has no overhead unlike linked list which incurs extra overhead due to memory allocation during runtime, such that array is faster/uses less time consumption
- more efficient access, array has O(1) efficiency, constant time access to data based on its index compared to linked list which has O(n) time complexity due to the need to traverse through the linked list to access data
linked list > static array
- more efficient insertion/removal, bc linked list has O(1) efficiency when inserting/removing data as only the pointer needs to be modified compared to an array which has O(n) time complexity when inserting/removing data
- more efficient memory use, linked list only uses as much memory as necessary compared to array which might not use all memory that’s allocated
how can queue & stack be implemented?
implemented using:
- array which wld use static allocation of memory
- linked list which wld use dynamic allocation of memory
how is deletion of root node done?
- root index/pointer doesnt change :. shld replace the data inside the root index with the new root index
- new root index should be either the next smaller/larger data (eg. 1,2,3,4,5 root 3 deleted :. either 2/4 is the new root)
how is insertion of new_node into ordered linked list done?
- starting from the head node, walk the linked list
- compare each node to the new_node, if the (comparison factor eg. time,data) of the node is more/less than the (abs factor of new_node, eg. 9am)
- new_node is inserted by linking the pointer of the previous node to the new_node and linking the pointer of the new_node to the next node.
^^more/less depends on how linked list is ordered –> ascending/descending
