¿Por qué se inserta en medio de una lista enlazada O (1)?

Según el artículo de Wikipedia sobre listas enlazadas , insertar en medio de una lista enlazada se considera O (1). Creo que sería O (n). ¿No necesitaría ubicar el nodo que podría estar cerca del final de la lista?

¿Este análisis no tiene en cuenta el hallazgo de la operación del nodo (aunque es obligatorio) y solo la inserción en sí?

EDITAR :

Las listas enlazadas tienen varias ventajas sobre las matrices. La inserción de un elemento en un punto específico de una lista es una operación de tiempo constante, mientras que la inserción en una matriz puede requerir mover la mitad de los elementos, o más.

La afirmación anterior es un poco engañosa para mí. Corrígeme si me equivoco, pero creo que la conclusión debería ser:

Matrices:

• Encontrar el punto de inserción / eliminación O (1)
• Realización de la inserción / eliminación O (n)

Listas vinculadas:

• Encontrar el punto de inserción / eliminación O (n)
• Realización de la inserción / eliminación O (1)

Creo que la única vez que no tendrías que encontrar la posición es si mantienes algún tipo de puntero (como con la cabeza y la cola en algunos casos). Entonces, no podemos decir rotundamente que las listas vinculadas siempre superan a las matrices para las opciones de inserción / eliminación.

Tiene razón, el artículo considera "Indexación" como una operación separada. Entonces, la inserción es en sí misma O (1), pero llegar a ese nodo del medio es O (n).

La inserción en sí es O (1). El hallazgo de nodo es O (n).

No, cuando decide que desea insertar, se asume que ya está en medio de la iteración de la lista.

Las operaciones en Listas Vinculadas a menudo se realizan de tal manera que en realidad no se tratan como una "lista" genérica, sino como una colección de nodos; piense en el nodo en sí mismo como el iterador de su bucle principal. Entonces, mientras revisa la lista, nota que, como parte de su lógica comercial, es necesario agregar un nuevo nodo (o eliminar uno antiguo) y lo hace. Puede agregar 50 nodos en una sola iteración y cada uno de esos nodos es solo O (1) el tiempo para desvincular dos nodos adyacentes e insertar el nuevo.

Editar: Hombre, escribes un segundo párrafo y de repente, en lugar de ser el primero en responder, ¡eres el quinto y dices lo mismo que los primeros 4!

A los efectos de comparar con una matriz, que es lo que muestra ese gráfico, es O (1) porque no tiene que mover todos los elementos después del nuevo nodo.

Entonces sí, están asumiendo que ya tiene el puntero a ese nodo, o que obtener el puntero es trivial. En otras palabras, el problema se plantea: " dado el nodo en X , ¿cuál es el código para insertar después de este nodo?" Tienes que empezar en el punto de inserción.

La inserción en una lista vinculada es diferente a iterar a través de ella. No está ubicando el elemento, está restableciendo los indicadores para colocar el elemento allí. No importa si se va a insertar cerca del extremo frontal o cerca del final, la inserción aún implica la reasignación de punteros. Dependerá de cómo se implementó, por supuesto, pero esa es la fuerza de las listas: puede insertar fácilmente. Acceder a través de índice es donde brilla una matriz. Sin embargo, para una lista, normalmente será O (n) encontrar el enésimo elemento. Al menos eso es lo que recuerdo de la escuela.

Porque no implica ningún bucle.

Insertar es como:

• insertar elemento
• enlace al anterior
• enlace al siguiente
• hecho

este es un tiempo constante en cualquier caso.

En consecuencia, insertar n elementos uno tras otro es O (n).

¿Este análisis no tiene en cuenta el hallazgo de la operación del nodo (aunque es obligatorio) y solo la inserción en sí?

Lo tienes. La inserción en un punto dado supone que ya tiene un puntero sobre el elemento que desea insertar después:

InsertItem(item * newItem, item * afterItem)

Insertar es O (1) una vez que sepa dónde lo va a poner.

No, no tiene en cuenta la búsqueda. Pero si ya tiene un puntero a un elemento en el medio de la lista, insertar en ese punto es O (1).

Si tiene que buscarlo, tendrá que agregar el tiempo de búsqueda, que debería ser O (n).

El artículo trata sobre la comparación de matrices con listas. Encontrar la posición de inserción para matrices y listas es O (N), por lo que el artículo la ignora.

O (1) depende de ese hecho de que tiene un elemento donde insertará el nuevo elemento. (antes o después). Si no es así, es O (n) porque debes encontrar ese artículo.

Creo que es solo un caso de lo que eliges contar para la notación O (). En el caso de insertar la operación normal para contar es operaciones de copia. Con una matriz, insertar en el medio implica copiar todo lo que está por encima de la ubicación en la memoria. Con una lista vinculada, esto se convierte en establecer dos punteros. Debe encontrar la ubicación sin importar qué insertar.

Si tiene la referencia del nodo para insertar después de la operación es O (1) para una lista vinculada.
Para una matriz, sigue siendo O (n) ya que debe mover todos los nodos consecutivos.

Los casos más comunes probablemente se insertan al principio o al final de la lista (y es posible que los extremos de la lista no tarden en encontrarlos).

Contraste eso con insertar elementos al principio o al final de una matriz (lo que requiere cambiar el tamaño de la matriz si está al final, o cambiar el tamaño y mover todos los elementos si está al principio).