4, (20 pts) Give a (n)-time algorithm LIST-SPLIT that splits a doubly-linked lis
ID: 3595193 • Letter: 4
Question
4, (20 pts) Give a (n)-time algorithm LIST-SPLIT that splits a doubly-linked list L at a given node x. The algorithm should return the head of the resulting list that con- tains the part of the list L after node r. The procedure should also modify L so that it ends at the node x after the split. Your algorithm should use only the default attribute head L and available operations for standard doubly-linked lists including LIST-SEARCH, LIST-INSERT and LIST-DELETE. In addition, you should not create/copy nodes in your algorithm, but just read and modify relevant pointers if needed. Make sure your algorithm has reasonably sufficient error checking to handle cases such as x null and the case that is not in L. Explain why your algorithm runs in (n) time. LIST-SPLIT(L, x)Explanation / Answer
LIST-SPLIT:
Input: Double pointer of head node // to update the list after split
Value of node (x) where list will be splitted
Output: Original list splitted
Return of second half head
Begin:
Define a pointer tmp of type node
Define a pointer ptr of type node
ptr <- *head
Start while ptr not NULL
if ptr-> data equals x
tmp<- ptr->next //assign ptr next to tmp pointer
ptr->next <- NULL // break the list
tmp-> prev <- NULL
return tmp // here original list is splitter and head of second part is returned
end if
ptr<- ptr-> next
end while
print node not found
return NULL
END
Time complexity is O(n) because in worst case while loop will run exactly n times if no match found
Where n is the input size
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.