Professor Gompers suspects that it might be possible to keep just one pointer in

Question

Professor Gompers
suspects that it might be possible to keep just one pointer in each set object,
rather than two (head and tail). Show that the professor’s suspicion is well
founded by describing how to represent each set by a linked list such that
each operation has the same running time as the operations described in this
section. Describe also how the operations work. Your scheme should allow
for the weighted-union heuristic, with the same effect as described in this
section. (Hint: Use the tail of a linked list as its set’s representative.)

Explanation / Answer

Dear user,

Assume that there are two lists A and B, and suppose that the representative of the new list will be the representative of A. Rather than appending B to the end of A, instead splice B into A right after the first element of A. We have to traverse B to update representative pointers anyway, so we can just make the last element of B point to the second element of A.

I hope this will helps to you

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

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