Data_Structures_Questions.md

For each of the methods associated with each data structure, classify it based on its worst-case runtime, using Big O notation.

Linked List

1. What is the runtime complexity of add_to_tail?

   a. What if our list implementation didn't have a reference to the tail of the list in its constructor? What would be the runtime of the add_to_tail method?

2. What is the runtime complexity of remove_head?

3. What is the runtime complexity of contains?

4. What is the runtime complexity of get_max?

Queue

1. What is the runtime complexity of enqueue?

2. What is the runtime complexity of dequeue?

3. What is the runtime complexity of len?

Binary Search Tree

1. What is the runtime complexity of insert?

2. What is the runtime complexity of contains?

3. What is the runtime complexity of get_max?

Heap

1. What is the runtime complexity of _bubble_up?

2. What is the runtime complexity of _sift_down?

3. What is the runtime complexity of insert?

4. What is the runtime complexity of delete?

5. What is the runtime complexity of get_max?

[Stretch Goal] Doubly Linked List

1. What is the runtime complexity of ListNode.insert_after?

2. What is the runtime complexity of ListNode.insert_before?

3. What is the runtime complexity of ListNode.delete?

4. What is the runtime complexity of DoublyLinkedList.add_to_head?

5. What is the runtime complexity of DoublyLinkedList.remove_from_head?

6. What is the runtime complexity of DoublyLinkedList.add_to_tail?

7. What is the runtime complexity of DoublyLinkedList.remove_from_tail?

8. What is the runtime complexity of DoublyLinkedList.move_to_front?

9. What is the runtime complexity of DoublyLinkedList.move_to_end?

10. What is the runtime complexity of DoublyLinkedList.delete?

    a. Compare the runtime of the doubly linked list's delete method with the worst-case runtime of the JS Array.splice method. Which method generally performs better?