data structures (stack, queue, circular queue, tree, linked list)

Question 1

what order does the 3 tree traversal types traverse in

Answer 1

pre-order: root-left-right
in-order: left-root-right
post-order: left-right-root

Question 2

queue

Answer 2

• operations performed in FIFO (first in first out) order
• with methods enqueue & dequeue

Question 3

circular vs linear queue

Answer 3

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

Question 4

stack

Answer 4

• operations performed in LIFO (last in first out) order
• with methods push & pop

Question 5

whats a balanced tree?

Answer 5

tree with minimum possible height (eg using median of data as the root node)

Question 6

advantage of BST? (may be outdated)

Answer 6

• 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

Question 7

disadvantages of BST

Answer 7

• 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

Question 8

can i implement BST using hash table?

Answer 8

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

Question 9

purpose of traversing through linked list (with numbers & mathematical operations as node data)

Answer 9

to traverse through linked list, concatenating each node’s value to the next

Question 10

linked list

Answer 10

• 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

Question 11

static array > linked list (assume dynamic)

Answer 11

• 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

Question 12

linked list > static array

Answer 12

• 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

Question 13

how can queue & stack be implemented?

Answer 13

implemented using:
- array which wld use static allocation of memory
- linked list which wld use dynamic allocation of memory

Question 14

how is deletion of root node done?

Answer 14

• 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)

Question 15

how is insertion of new_node into ordered linked list done?

Answer 15

• 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