linked-list - programacion - listas simples estructura de datos
¿Por qué insertar en el medio de una lista enlazada O(1)? (14)
De acuerdo con el artículo de Wikipedia sobre listas vinculadas , la inserción en el medio de una lista vinculada se considera O (1). Yo pensaría que sería O (n). ¿No necesitarías ubicar el nodo que podría estar cerca del final de la lista?
¿Este análisis no explica 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:
Arrays:
- Encontrar el punto de inserción / eliminación O (1)
- Realizando la inserción / eliminación O (n)
Listas enlazadas:
- Encontrar el punto de inserción / eliminación O (n)
- Realizando 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 en el caso de la cabeza y la cola en algunos casos). Por lo tanto, no podemos decir rotundamente que las listas enlazadas siempre superan las matrices para las opciones de inserción / eliminación.
¿Este análisis no explica 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:
InsertItem(item * newItem, item * afterItem)
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, se realizan operaciones de copia. Con una matriz, insertar en el medio implica copiar todo lo que está 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.
El artículo trata sobre la comparación de 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.
Es probable que los casos más comunes se inserten al principio o al final de la lista (y los extremos de la lista pueden no tardar en encontrarlos).
Contraste eso con la inserción de elementos al principio o al final de una matriz (que requiere redimensionar la matriz si está al final, o cambiar el tamaño y mover todos los elementos si está al principio).
Insertar es O (1) una vez que sepa dónde lo va a colocar.
La inserción en sí es O (1). El hallazgo del nodo es O (n).
La inserción en una lista vinculada es diferente de iterar a través de ella. No está ubicando el artículo, está reiniciando punteros para colocar el artículo allí. No importa si se va a insertar cerca del extremo delantero o cerca del final, la inserción aún implica que los punteros sean reasignados. Dependerá de cómo se implementó, por supuesto, pero esa es la fuerza de las listas: puede insertar fácilmente. Acceder vía índice es donde brilla una matriz. Para una lista, sin embargo, normalmente será O (n) para encontrar el enésimo artículo. Al menos eso es lo que recuerdo de la escuela.
No, cuando decides que deseas insertar, se supone que ya estás en mitad de la iteración de la lista.
Las operaciones en las listas vinculadas a menudo se hacen 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í mismo como el iterador para su ciclo principal. Así que mientras revisa la lista, observa como parte de la lógica de su negocio que es necesario agregar un nuevo nodo (o eliminar uno antiguo) y lo hace. Puede agregar 50 nodos en una sola iteración.
Editar: Hombre, escribe un segundo párrafo y, de repente, en lugar de ser el primer respondedor, ¡eres el quinto diciendo lo mismo que los primeros 4!
No, no explica la búsqueda. Pero si ya tiene un puntero a un elemento en el medio de la lista, insertarlo en ese punto es O (1).
Si tiene que buscarlo, debe agregar el tiempo de búsqueda, que debe ser O (n).
O (1) depende de que usted tenga un artículo donde va a insertar el nuevo artículo. (antes o después). Si no lo hace, es O (n) porque debe encontrar ese artículo.
Para fines de comparación con una matriz, que es lo que muestra la tabla, 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, se establece el problema: " nodo dado en X , ¿cuál es el código para insertar después de este nodo?" Tienes que comenzar en el punto de inserción.
Porque no implica ningún bucle.
Insertar es como:
- insertar elemento
- enlace a la previa
- enlace a siguiente
- hecho
esto es tiempo constante en cualquier caso.
En consecuencia, insertar n elementos uno después del otro es O (n).
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 tiene que mover todos los nodos consecutivos.
Tiene razón, el artículo considera "Indexar" como una operación separada. Entonces la inserción es en sí misma O (1), pero llegar a ese nodo medio es O (n).