Complejidad del algoritmo insertando un elemento en una lista circular vinculada en la parte delantera

Question

En una lista circular vinculada, si se deben insertar un elemento en la parte delantera [justo antes del nodo apuntado por la cabeza], se puede hacer en o (1) (consulte la respuesta aquí)

Pero en un libro actualmente, lo tengo, se menciona que se hace en o (n) (el método habitual). También vi pocos PPT de conferencias, todos mencionan el método habitual de atravesar la lista y agregar un elemento.

Mi pregunta es :

1. En escenarios prácticos, ¿qué método se usa?

2. Estoy a punto de asistir a un examen, que consiste en MCQS, si se hace la pregunta anterior, ¿Marco O (N), ya que esa es la respuesta estándar?

Answer 1

El método utilizado en escenarios prácticos depende del escenario (y del programador). Hay varios problemas posibles que influyen en la elección de la implementación:

1. Si el algoritmo es conocido por el programador.
2. Facilidad de codificación (es más fácil si ya está implementado en alguna biblioteca que puede usar).
3. Velocidad: eso depende de cómo se use la estructura de datos.
4. Space Overhead tomado por la estructura de datos.

Un programador inteligente debe tener en cuenta todo esto e tratar de hacerse más conocedores de varios algoritmos y estructuras de datos.