Memory-Efficient Doubly-Linked-Lists Recall that a memory efficient doubly-linke
ID: 3822945 • Letter: M
Question
Memory-Efficient Doubly-Linked-Lists Recall that a memory efficient doubly-linked list implements the List interface by storing a sequence of blocks (arrays) each containing b ± l elements. What is the running-time of get(i) and set(i) in a memory-efficient doubly-linked list? What is the amortized (or average) running time of the add(i) operation in a memory-efficient doubly-linked list? In a memory-efficient doubly-linked list containing n elements, what is the maximum amount of space that is not devoted to storing data?Explanation / Answer
1) the complexity for thr get(i) and set(i) in the memory efficient linked list is o(i) where i is the postion where the element is to be stored or the position of the value to fetched.
2) the average complexity of the adding the element in the doubly linked list is o(n)
3) the structure of the doubly linked list is
class Node{
int data,
Node next;
Node Prev;
};