Memory-Efficient Doubly-Linked-Lists Recall that a memory efficient doubly-linke

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;

};

Related Questions

Navigate

• Browse (All)
• Browse M
• Subjects

---

---

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