5. (15 points) Reverse a sequence container of n elements. For example, if a seq
ID: 3881630 • Letter: 5
Question
5. (15 points) Reverse a sequence container of n elements. For example, if a sequence container contains 3, 1, 2, and 5, where the first element is 3 and the last is 5, the reverse of the container is 5, 2, 1, and 3, where the first 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 definition of all sequence containers as described in class.Explanation / Answer
The algorithm to reverse an Array in O(n) time is :
function ReverseAnArray(A) {
var l = A.length;
var halfL = Math.floor(l/2);
for (var j=0; j<halfL; j++) {
var temp = A[j];
A[j] = A[l-1-j];
A[l-1-j] = temp;
}
return A;
}
The iterative algorithm swaps the elements of array j and l-1-j for a zero index of array , it takes the O(n) time and O(1) space .
The algorithm to reverse a singly linked list is :
Algorithm :
Begin:
If (h != NULL) then
pNode h
head h.next
cNode h
pNode.next NULL
While (h != NULL) do
h h.next
cNode.next pNode
pNode cNode
cNode h
End while
h pNode
End if
End
The hed node of the list is provided as input to the algorithm , the pointers pNode and cNode refer to the previous and current nodes in the list , at first pNode pointer points to the head h , The algorithm runs in O(n) time complexity .
The algorithm to reverse a doubly linked list is :
Algorithm:
Begin:
cNode head;
While (cNode != NULL) do
temp cNode.next;
cNode.next cNode.pNode;
cNode.pNode temp;
cNode temp;
End while
temp head;
head tail;
tail temp;
End
The head and tail pointers are swapped and The run time of the algorithm is O(1) .
The algorithm to reverse an arary cannot be faster than O(n) , but by susing the wrapper class the array can be reversed by using its indexes . The singly linked list can only be fastly reversed by using O(n) run time either by recursive or iterative approach and the doubly linked list can be fastly reversed by using O(1) run time by swapping head and tail pointers .
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.