Implementar la cola con una lista vinculada; ¿Por qué sería malo insertar en la cabeza y quitar en la cola?

Question

En mi libro de texto, estructuras de datos y algoritmos en Java, el autor dice que al implementar una cola utilizando una lista vinculada, elige la parte delantera de la cola para estar a la cabeza de la lista, y la parte trasera de la cola para estar en la cola la lista. De esta manera, se quita de la cabeza e inserte en la cola.

Luego, el autor pregunta crípticamente: "¿Por qué sería malo insertar en la cabeza y quitar la cola?" sin proporcionar una respuesta.

No puedo ver cuál es realmente la diferencia. En efecto, la "cabeza" y la "cola" son solo nombres arbitrarios que definimos. ¿Qué sería tan malo si enqueue () agregamos una cabeza y creamos una referencia a la cabeza vieja, y para despegar () tomamos de la cola y movemos la cola?

¿Cuál es la respuesta a la pregunta del autor?

Answer 1

En una sola lista vinculada, cada elemento tiene un puntero al siguiente elemento. Si tiene un puntero adicional al elemento de la cola, le lleva un número constante de operaciones OG a agregar A la lista en la cola: obtenga el puntero de la cola, agregue un elemento después de la cola, coloque este nuevo elemento como cola nueva. Eliminar de la cabeza también requiere un número constante de operaciones: hacerle nuevo elemento nuevo, cabeza, apuntar a la cabeza antigua.

Sin embargo, eliminación De la cola exige un puntero al predecesor a la cola actual. Esto le lleva tantas operaciones como elementos, a saber, linealmente muchas.

Otra solución es usar una lista doblemente vinculada, luego puede elegir lo que quiera, pero usa el doble de memoria.

Answer 2

Eliminar de la cabeza e insertar en la cola son operaciones de tiempo constantes con una lista vinculada individualmente, suponiendo punteros de cabeza y cola. Insertar en la cola también es tiempo constante. Pero quitar de la cola significa mover el puntero de la cola hacia la cabeza, y dado que no tiene un puntero posterior, no puede hacerlo sin atravesar toda la lista para encontrar el elemento anterior a la cola. Esto hace que la inserción sea un tiempo lineal en lugar de una operación de tiempo constante y es por eso que es peor.