java

Explain why the insertion-sort algorithm has worst-case runtime cost of 0(n^2) to sort n items. Describe the algorithm to search for an item with given key, in a hash table that uses open addressing with double hashing. Consider a class MyList Implementation that keeps a doubly linked list with header and trailer sentinel nodes (referenced by instance variables of the list implementation called header and trailer). Assume that the Node class has the usual getter and setter methods. Suppose n is a Node within the list (not one of the sentinels). Write the sequence of Java statements that would be used within MyListlmplementation, in order to remove the Node n from the list. [You can use assignments to instance variables and you can call methods of the Node class, but do not call methods of the List ADT itself.] Write an explanation for a beginning programmer, to teach them the difference between the following two ways of determining the order between items: using a Comparator and a Comparable. An Iterator object is used in data structures, to allow the user to access the items in a collection one-by-one. Give instructions that teach someone how to define an Iterator for a collection based on linked nodes. In particular, you need to indicate any methods that the Iterator must have