You\'d like to maintain a sorted sequence of integers. So you need an insert(e)

Question

You'd like to maintain a sorted sequence of integers. So you need an insert(e) method that will insert the new element e at the correct position in the current sorted sequence. To do this involves two parts: 1) locating the correct position in sequence and 2) inserting the element into the sequence. Using big-Oh notation, how long will each part take if you implement the sorted sequence class with a linked list? What if you implement with an array (or rather, a portion of an array)?

Linked list

Array

Locate position

insert

Also, suppose you expect that insertions into the middle of the list will be very rare. Most insertions will be quite close to the end of the list. Does this affect your decision about whether to use a linked list or array in your implementation?

Linked list

Array

Locate position

insert

Explanation / Answer

Locate position.

For linkedlist we need at max the whole list scan. Therefore O(n).

For array we can use binary search if the array is sorted. Therefore O(logn).

For insertion.

For linkedlist we need to just create a node and change the links at that position. Therefore O(1) = O(1)

For array we need to shift all the elements on the right of the element to be inserted. There can be a maximum of n shifts. Therefore O(n).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

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