Problem 3 (20%) Given n elements stored in a singly linked list. In addition, the address...

Transcribed Image Text:

Problem 3 (20%) Given n elements stored in a singly linked list. In addition, the address of the i-th element is provided. Briefly explain how to implement the following operations efficiently and analyze the running time. (Express your running time in notation.) 1. Add a new element between the i-th and the (i+1)-th element. 2. Add a new element between the (i-1)-th and the i-th element, assuming that the address of the i-th element cannot be changed. 3. Repeat problem 3-2, but allow the address of the i-th element change. 4. Repeat problem 3-2 when the elements are stored in a doubly-linked list. Problem 3 (20%) Given n elements stored in a singly linked list. In addition, the address of the i-th element is provided. Briefly explain how to implement the following operations efficiently and analyze the running time. (Express your running time in notation.) 1. Add a new element between the i-th and the (i+1)-th element. 2. Add a new element between the (i-1)-th and the i-th element, assuming that the address of the i-th element cannot be changed. 3. Repeat problem 3-2, but allow the address of the i-th element change. 4. Repeat problem 3-2 when the elements are stored in a doubly-linked list.

Answer rating: 100% (QA)

Lets address each of the operations and analyze their efficiency in terms of running time 1 Add a new element between the ith and the i1th element in ... View the full answer