Adding a new element to an ordered collection (like an indexed list) can be thou

Question

Adding a new element to an ordered collection (like an indexed list) can be thought of as a two-part process 1) Find the right spot, then (2) physically add the element If a chain of linked nodes is used as the underlying data structure for the collection, the right spot is identified by a reference to a node in the chain. Assuming the reference to the right spot has already been found what is the worst-case time complexity of then physically adding the element to the chain of linked nodes? A. O(1) B. O(log N) C. O(N) D. O(N^2)

Explanation / Answer

Suppose we have chain of elemnets


3-->4-->6-->1-->7

1. We want to enter 10 after 6
2. We identified the elements position to enter after 6

We can do it in O(1) time because

Let newNode be 10

newNode(10)->next = (6)Node->next;
(6)Node->next = newNode(10)

So, A is the answer O(1)

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

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