Section IlI - Lists 29. When inserting a new data value into an Unsorted Linked

Question

Section IlI - Lists 29. When inserting a new data value into an Unsorted Linked List, where is the most efficient position to add the new data value? A) After the last element currently stored in the container B) Before the first element currently stored in the container C) In between two elements currently stored in the container D) None of the answers provided 30. What is the complexity of the inserting a data value into a Sorted Array-Based List? A) 0) C) O(logN) B) 0(N) D) 0(N2) E) None of the answers provided 31. What is the complexity of the constructor operation for a Sorted Array-Based List? A) 1) B) O(N C) O(log2N) D) O(N2 E) None of the answers provided 32. What is the complexity of the destructor operation for an Unsorted Linked List? A) 0(1) B) O(N) C) 0(log2 N) D) O(N2) E) None of the answers provided

Explanation / Answer

29.

As our linked list is unsorted, we don't need to find the proper position in the sequence of data values for the new data.

So now if we add the new data at end of linked list, then we have to traverse the list once. So takes O(n) time.let say we have n elements in our linked list.

But if we add the new element before the first element, then we only need to update two pointers. So takes constant time. O(1)

hence adding before the first element is more efficient.

30)

we can apply binary search methodology for dividing the array and then to find the position of the new element to be added. that takes O(log N) time.

But for insertion we have to shift the existing data values to make the position blank, which may be N in worst case(i.e if we find the position for new element is 1).

hence time complexity will be O(N)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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