Skip to content

Latest commit

 

History

History
75 lines (38 loc) · 2.19 KB

Data_Structures_Questions.md

File metadata and controls

75 lines (38 loc) · 2.19 KB
Raw

Answer the following questions for each of the data structures you implemented as part of this project.

Stack

  1. What is the runtime complexity of push using a list?

  2. What is the runtime complexity of push using a linked list?

  3. What is the runtime complexity of pop using a list?

  4. What is the runtime complexity of pop using a linked list?

  5. What is the runtime complexity of len using a list?

  6. What is the runtime complexity of len using a linked list?

Queue

  1. What is the runtime complexity of enqueue using a list?

  2. What is the runtime complexity of enqueue using a linked list?

  3. What is the runtime complexity of dequeue using a list?

  4. What is the runtime complexity of dequeue using a linked list?

  5. What is the runtime complexity of len using a list?

  6. What is the runtime complexity of len using a linked list?

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?

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?

  4. What is the runtime complexity of for_each?

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?