You are writing a program to hold nodes (structures) for some events. For which

Question

You are writing a program to hold nodes (structures) for some events. For which operation(s) is a linked list more efficient than an array? Circle all that apply Deleting a node Finding the total size of the data structure Inserting a new node, in order by a specific key Finding the kth item in the list Finding the kth item in the list Finding a node with a specific key We are working on a FIFO queue. Below, a letter means 'add this letter to the queue' and an asterisk means 'get a letter from the queue'. Give the sequence of values returned by the get operations when this sequence of operations is performed on an initially empty queue. Repeat the question, but this time using a Priority queue, where 'A' has highest priority, then B. etc.

Explanation / Answer

2) a) Deletion is more efficient and easy in LL than in array as the storage is consective in array as only value of pointer is needed to change in LL.

b) Finding total size is easy in LL as the memory of array is fixed, we must know upper limit it in advance.

c) Inserting an element in an array is more expensive than in LL as the room should be created for every insertion

d) In array the element can be assced randomly but in LL it is sequential. So its easy in array.

e) Same as both requires O(n) in worst case.

3) Queue: X L A

Queue: L A as * came

  Queue: A as * came

  Queue: A Z M V O

  Queue: Z M V O as * came

  Queue: Z M V O U

  Queue: M V O U as * came

  Queue: M V O U T S

  Queue: V O U T S as* came

  Queue: O U T S as* came

With Priority Queue

PQ:X, PQ: L X PQ: A L X PQ: L X PQ: X PQ: X Z PQ: M X Z PQ: M V X Z PQ: M O V X Z PQ: O V X Z PQ: O U V X Z PQ: U V X Z PQ: T U V X Z PQ: S T U V X Z PQ: T U V X Z PQ: U V X Z

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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