Suppose that a friend has implemented a deque, as defined in the previous exercise, using a singly linked list, but hasn’t given you the details, for example, of whether the links go forward or backward in the list or whether sentinel nodes are used. Nevertheless, show that one of the insertion or removal methods must take Ω(n) time, where n is the number of elements in the deque.

Data From Previous Exercise

Suppose you are given an array, A, containing n numbers in order. Describe in pseudocode an efficient algorithm for reversing the order of the numbers in A using a single for-loop that indexes through the cells of A, to insert each element into a stack, and then another for-loop that removes the elements from the stack and puts them back into A in reverse order. What is the running time of this algorithm?