Suppose we have a sorted linked list that contains n integers, and we want to in

Question

Suppose we have a sorted linked list that contains n integers, and we want to insert an element into that list in sorted order. How is that operation's runtime affected by whether or not we maintain a tail pointer (as opposed to only maintaining a head pointer)? Select all that apply. If we maintain a tail pointer, the best-case big-oh runtime for this sorted insertion becomes much better. If we maintain a tail pointer, the best-case big-oh runtime for this sorted insertion remains unaffected. If we maintain a tail pointer, the worst-case big-oh runtime for this sorted insertion becomes much worse. If we maintain a tail pointer, the worst-case big-oh runtime for this sorted insertion becomes much better. If we maintain a tail pointer, the best-case big-oh runtime for this sorted insertion becomes much worse.

Explanation / Answer

Dear Student,

General Linked List has a single 'head' pointer which points to the first element of the linked list. It is not like an array where we can assign an element to any position by just giving the index eg. Arr[i] assigns an element to the ith position of array Arr in O(1).For inserting an element at a specific position in a linked list you have to first traverse the list till that position and then you can add the element.So the worst case for insertion in linked list would be when you need to traverse the whole list to its end to add the element.

In the problem given, the linked list is sorted. Let's say it is sorted in ascending order. That means the highest element stays at the end of the list. So the worst case scenario would be when the new element arriving is greater than the biggest element in the linked list since then we have to traverse the whole list to add that element at the end ie. O(n) (where n is the no. of elements in the linked list). Now, if we add a tail pointer to it, then the tail pointer will stay at the end of the linked list.Now if we want to add something at the end or near to it(larger elements), we can use tail pointer and if we want to add something near to the beginning(smaller elements), then we use head pointer. So, in this scenario the worst case would be when an element has to be added in the middle of linked list, not the end. So the complexity reduces to half ie. O(n/2).

So, the answer to this question would be:

If we maintain a tail pointer, the worst-case big-oh runtime for this sorted insertion becomes much better.

Thank You

For further queries, please feel free to ask. I would be glad to help :-)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

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