Compare arrays, linked lists, hash tables, trees

Respond to the following questions on computer-science fundamentals:

1. For common sorting algorithms (bubble sort, insertion sort, selection sort, merge sort, quicksort, heap sort), what are their best-case, average-case, and worst-case time complexities in Big-O terms?
2. Contrast arrays and linked lists. What are the time complexities for element access, insertion at the head, and insertion in the middle?
3. Walk through the complete process of inserting an element at the head of a dynamic array (such as a vector or ArrayList), including the steps taken when the array must expand.
4. Define a hash table. Explain the data structure underneath it and the ways collisions are resolved.
5. How do a hash table and a hash map differ, both conceptually and, where applicable, in common languages like Java?
6. What distinguishes a binary tree from a binary search tree (BST)?

Overview: Tests knowledge of core data structures and algorithmic complexity—arrays, linked lists, dynamic arrays, hash tables/maps, trees—and widely used sorting algorithms.