A linked list may have one of several forms. It may be either singly linked or d
ID: 3672602 • Letter: A
Question
A linked list may have one of several forms. It may be either singly linked or doubly linked, it may be sorted or not, and it may be circular or not. If a list is singly linked, only a next pointer is present in each node; if doubly linked it has both a next and a prev pointer present in each node. If a list is sorted, the linear order of the list corresponds to the linear order of keys stored in elements of the list; the minimum element is at the head of the list, and the maximum element is at the tail. If the list is unsorted, the elements can appear in any order. Assume the pointer to the head of the list is Nil if the list is empty and points to the first node in the list otherwise. For each of the four types of lists, fill in the asymptotic worst-case run time for each dynamic set operation listed. Note that Delete() needs to find the element X to delete; it could use SEARCH() for this purpose.Explanation / Answer
Unsorted(singly) Sorted(singly) unsorted(doubly) sorted(doubly)
SEARCH O(n) O(n) O(n) O(n)
INSERT O(1) O(n) O(1) O(n)
DELETE O(n) O(n) O(n) O(n)
SUCCESSOR O(n) O(n) O(n) O(n)
PREDECESSOR O(n) O(n) O(n) O(n)
MINIMUM O(n) O(1) O(n) O(1)
MAXIMUM O(n) O(1) O(n) O(1)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.