5. Reverse a sequence container of n elements. For example, if a sequence contai

Question

5. Reverse a sequence container of n elements. For example, if a sequence container contains 3, 1, 2, and 5, where the rst element is 3 and the last is 5, the reverse of the container is 5, 2, 1, and 3, where the rst is 5 and the last is 3. Describe an O(n) time algorithm to reverse an Array, an O(n) time algorithm to reverse a Single Linked List, and an O(1) time algorithm to reverse a Double Linked List. For each of the abstract data type, can it be any faster? Please follow the denition of all sequence containers as described in class.

6. Given an array A storing n integers and another integer s, nd whether or not there exist two elements x and y in the array such that x + y = s. Assuming it is possible to sort n numbers in O(nlogn) time, describe an O(nlogn) time algorithm to solve the problem and write the pseudocode.

Explanation / Answer

Solution:

5 is solved, please repost 6.

5)

Reversing an array in O(n) time:

Reversing a singly linked list in O(n) time:

Reversing a Doubly linked list in O(1) time:

It is not possible to reverse a double linked in O(1) time unless you know the address of the last node. Because even the traversal to get to the last node will take O(n) time after that change of link is only thing required.

I hope this helps if you find any problem. Please comment below. Don't forget to give a thumbs up if you liked it. :)

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.