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

Question

Según el artículo de Wikipedia sobre listas vinculadas , insertando en el medio de una lista vinculada se considera O (1). Creo que sería O (n). ¿No necesitaría localizar 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í misma?

EDITAR :

  

Las listas vinculadas 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 declaració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 el único momento en el 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). Por lo tanto, no podemos decir que las listas vinculadas siempre superan a las matrices para las opciones de inserción / eliminación.

Answer 1

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

Answer 2

La inserción en sí es O (1). La búsqueda de nodos es O (n).

Answer 3

No, cuando decide que desea insertar, se supone que ya está en medio de iterar por la lista.

Las operaciones en las listas enlazadas a menudo se realizan de tal manera que no se tratan realmente como una "lista" genérica, sino como una colección de nodos: piense en el nodo en sí como el iterador de su bucle principal. Entonces, mientras revisa la lista, nota como parte de su lógica de negocios que necesita agregar un nuevo nodo (o eliminar uno viejo) y lo hace. Puede agregar 50 nodos en una sola iteración y cada uno de esos nodos es solo O (1) el momento de 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 que dice lo mismo que los primeros 4!

Answer 4

Para comparar con una matriz, que es lo que muestra el 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 tienes el puntero a ese nodo, o que obtener el puntero es trivial. En otras palabras, el problema se plantea: " nodo dado en X , ¿cuál es el código para insertar después de este nodo? & Quot; Puedes comenzar en el punto de inserción.

Answer 5

La inserción en una lista vinculada es diferente de iterar a través de ella. No está localizando el elemento, está restableciendo punteros 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 fortaleza de las listas: puede insertarlas fácilmente. Accediendo a través del í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.

Answer 6

Porque no implica ningún bucle.

Insertar es como:

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

este es tiempo constante en cualquier caso.

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

Answer 7

  

¿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í misma?

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

InsertItem(item * newItem, item * afterItem)

Answer 8

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

Answer 9

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

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

Answer 10

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

Answer 11

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

Answer 12

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 son las operaciones de copia. Con una matriz, insertar en el medio implica copiar todo lo que está arriba 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.

Answer 13

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.

Answer 14

Los casos más comunes probablemente se están insertando al principio o al final de la lista (y los extremos de la lista pueden tardar en encontrar).

Compare 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).