Assuming the most efficient implementation of a Singly Linked List Queue, what i

Question

Assuming the most efficient implementation of a SinglyLinked List Queue, what is the cost of the enqueue () operation? Express your answer in Big Oh notatio n as it relates to the input size.

Assuming the most efficient implementation of a SinglyLinked List Queue, what is the cost of the dequeue () operation? Express your answer in Big Oh notation as it relates to the input size.

Assuming the most efficient implementation of SinglyLinked List Stack, what is the cost of the push() operation? Express your answer in BIG Oh notation as it relates to the input size.

Assuming the most efficient implementation of a SinglyLinked List Stack, what is the cost of the pop() operation? Express your answer in Big Oh notation as it relates to the input size. Remove and return the top element from the stack.

Explanation / Answer

(a ) Cost of enqueue operation is O(1). This is because to add a node to the queue we just shift head to the new node and the new node is made to point to the previous head. Which is constant number of operations thus Cost of enqueue operation is O(1).

(b ) Cost of dequeue operation is also O(n). To dequeue we need to traverse the whole linked list to find the last element and remove the last element by making the previous node point to NULL

(c ) Cost of push operation is O(1). We just add a node and shift head to new node. Explaination similar to (a)

(d) Cost of pop operation is O(1). we just need to make the head point to the next element of the first node. This is constant number of operations. thus cost of pop is O(1).

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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