1. Consider maintaining a collection of lists of items on which the following op

Question

1. Consider maintaining a collection of lists of items on which the following operations can be
performed:
(i) Given two lists L1 and L2, form their concatenation L (destroying L1 and L2 in the
process).
(ii) Given a list L and a positive integer k, split L into two lists L1 and L2, where L1 consists
of the rst k items of L, and L2 the rest (L is destroyed in the process).
(iii) Report the first item in given list L.
(iv) Create a new list with one item.
Describe data structures and algorithms supporting these operations so that operations (i){
(iii) can be performed in time O(log n) (where n is the length of L), and operation (iv) takes
constant time.

Explanation / Answer

void concatenate(list1, list2) { if( list1.tail == null ) list1.head = list2.head; else list1.tail.next = list2.head; if( list2.head != null ) list1.tail = list2.tail; }

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

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