PUERTA | PUERTA CS 2018 | Pregunta 11

Una cola se implementa utilizando una lista no circular enlazada individualmente. La cola tiene un puntero de cabeza y un puntero de cola, como se muestra en la figura. Sea n el número de Nodes en la cola. Permita que ‘enqueue’ se implemente insertando un nuevo Node en la cabeza, y ‘dequeue’ se implemente eliminando un Node de la cola.

Which one of the following is the time complexity of the most time-efficient implementation of ‘enqueue’ and ‘dequeue, respectively, for this data structure?
(A) Θ(1), Θ(1)
(B) Θ(1), Θ(n)
(C) Θ(n), Θ(1)
(D) Θ(n), Θ(n)

Answer: (B)
Explanation: For Enqueue operation, performs in constant amount of time (i.e., Θ(1)), because it modifies only two pointers, i.e.,

Create a Node P.
P-->Data = Data
P-->Next = Head
Head = P

Para la operación Dequeue, necesitamos la dirección del penúltimo Node de la lista enlazada única para hacer NULL de su próximo puntero. Dado que no podemos acceder a su Node anterior en una lista enlazada individualmente, necesitamos recorrer toda la lista enlazada para obtener el penúltimo Node de la lista enlazada, es decir,

temp = head;
 While( temp-Next-->Next != NULL){
        temp = temp-Next;
        }
temp-->next = NULL;
Tail = temp;

Dado que estamos atravesando todo el enlace para cada Dequeue, la complejidad del tiempo será Θ(n).

La opción (B) es correcta.

Cuestionario de esta pregunta