He escrito un tutorial completo sobre Colas que cubren diferentes implementaciones usando Array, Listas vinculadas y Arreglo de redimensionamiento.
Para resumir, para matrices y listas vinculadas:
Tiempo → Con la Lista enlazada, las operaciones ( poner en cola, poner en cola y vacío ) toman tiempo constante; O (1) , pero todavía no es tan eficiente debido a la declaración del objeto y al manejo de enlaces. Mientras que con las matrices, acceder a las matrices es mucho más rápido; Se necesita O (1) .
- ¿Por qué las listas enlazadas son más convenientes que las matrices en el dominio de la computación simbólica?
- Cómo implementar un algoritmo técnico en papel desde cero en C ++ o MATLAB
- ¿Cuánto cálculo se requiere para comprender algoritmos y redes de computadoras?
- ¿Cómo clasifica Quora las preguntas? ¿Qué algoritmos usan?
- ¿Es la calificación de revisión un factor en el algoritmo de 'Yelp Sort' de Yelp?
Memoria → Listas vinculadas requiere más memoria debido al tamaño de los objetos de nodo (consulte la figura a continuación). Mientras que con las matrices requiere menos espacio de memoria.
Supongo que en el caso de la matriz, debe pasar el tamaño de la matriz al constructor. En muchas situaciones, no podemos saber qué tan grande es, y esto viola la idea de la pila y la cola, que dice que debería poder crecer y reducirse en cualquier tamaño.
Para cambiar el tamaño de la matriz:
Tiempo → El peor de los casos es O (N) para insertar y eliminar, porque es posible que necesitemos cambiar el tamaño de la matriz. El caso amortizado y el mejor caso es O (1) para ambas operaciones. El caso promedio toma un tiempo constante para insertar (al final) y eliminar el último elemento.
Compromisos: Lista enlazada vs matriz de cambio de tamaño
No voy a incluir la matriz con tamaño fijo en la comparación, como ya se mencionó que viola la idea tanto para las pilas como para las colas.
Lista vinculada → Garantiza que cada operación llevará un tiempo constante en el peor de los casos. Pero utiliza tiempo y espacio extra para lidiar con la creación de objetos y enlaces.
Matrices redimensionadas → Cada operación requiere O (1) tiempo amortizado y se necesita menos espacio.
La conclusión es: si desea asegurarse de que cada operación llevará un tiempo constante, utilice la lista vinculada.
Sin embargo, si solo le importa la cantidad de tiempo total, use la matriz de cambio de tamaño, porque aunque puede ser más lenta cuando hay operaciones de cambio de tamaño, pero el tiempo total será menor, porque las operaciones individuales son rápidas.
¡Espero eso ayude!
