In this problem a linked list L is searched from both ends for a key k. If k is
ID: 3772526 • Letter: I
Question
In this problem a linked list L is searched from both ends for a key k. If k is in the list, a pointer to the node containing k should be returned. Otherwise, NIL should be returned. The list L is doubly-linked and has both head and tail pointers. Is the pseudocode correct? If not, fix it and justify your answer. Also, state the best and worst-case input scenarios for the fixed code if any changes were necessary.
DoubleSearch(L, k) if headL]-NIL then return NIL start head[L] end tail[L] while start end and key(start-k and kefendzk na an do start next[start] end prev[end] if key[start]-k then return start if key[end] - k then return end return NILExplanation / Answer
The given procedure is
1
2
3
4
5
6
7
8
9
10
11
12
The given DoubleSearch(L,k) is not correct. It works perfectly, only if the length of the list is odd. But fails, when the key is not in the list and length of the list is even. Thus, the modification is necessary at line 5.
If the list is of odd length, even though the key is not exist in the list, then the while breaks when start=end at middle element.
But the loop at 5 raises error, because start=end is not encountered at the end. Finally start becomes NIL and end also becomes NIL. Since start=end, While breaks.
Then, Key [NIL] at line 8 raises an exception.
To overcome this problem, add one more Boolean expression.
The modified Code:
1
2
3
4
5
6
7
8
9
10
11
12
Running time complexity:
In the best case, key is stored in head or tail.
It takes O(1) time.
In the worst case, key is not exist in the list or the key is the middle of the list.
Since two elements are searching each time, It takes O(n/2) time. Where , n is the number of nodes in the double linked list.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.