Linked List inserción tiempo de ejecución confusión

Question

He intentado confirmar el tiempo de ejecución para la inserción de Linked List y parece que hay dos respuestas diferentes.

Para insertar un elemento al final de una lista vinculada, creo que tomaría O (n) ya que tiene que atravesar el final de la lista para acceder a la cola. ¿Pero algunas de las respuestas que he visto dicen O (1)? ¿Están asumiendo que todas las listas vinculadas implementan un puntero a la cola? Si es así, ¿es eso una suposición aceptable?

En segundo lugar, algunos lugares también sugieren que la inserción de un elemento en el medio de una lista vinculada es O (1), lo cual me causa confusión debido al mismo razonamiento de poligonal a la mitad de la lista para insertarlo.

¿Podría aclarar alguien? Gracias.

Answer 1

La inserción en una lista vinculada es O (1) si tiene un puntero al nodo donde desea insertar el elemento. Encontrar este nodo puede ser O (n) según lo que desee hacer.

Si mantiene un puntero a la cola de la lista, entonces no necesita buscarlo y luego la inserción es O (1).

Y no, no todas las implementaciones de listas vinculadas tienen un puntero al final de la lista.

Ejemplo

Suponga que tiene una lista vacía a la que se agrega un solo nodo, x. Luego agrega nodos n a la lista antes y después de x. Todavía puede insertar un solo nodo después de x simplemente actualizando su puntero next (y el nuevo nodo), independientemente de cuántos nodos haya en la lista.

Answer 2

Las modificaciones a lista enlazada implican dos operaciones:

1. localizar el nodo a añadir el nuevo nodo a
2. realidad añadiendo el nodo, cambiando los punteros a nodos

En lista enlazada, la segunda operación es una operación O(1), por lo que es una cuestión del costo de las primeras operaciones.

Al agregar al último nodo, las implementaciones ingenuas de la lista vinculada darían como resultado O(n) tiempo de iteración. Sin embargo, las buenas bibliotecas de listas enlazadas representarían los usos más comunes, y el caso especial accedería al último nodo. Esta optimización daría como resultado la recuperación O(1) del último elemento, lo que da como resultado el tiempo total de inserción O(1) para finalizar.

En cuanto a la mitad, su análisis es correcto en que la localización del nodo también tomaría O(n). Sin embargo, algunas bibliotecas exponen un método que tomaría un puntero al lugar donde debe insertarse el nuevo nodo en lugar del índice (por ejemplo, C++list). Esto elimina el costo lineal, lo que resulta en O(1).

Mientras que la inserción en el medio generalmente se considera operación O(n), en algunos casos se puede optimizar a O(1).Esto es lo opuesto a la lista de arreglos, donde la operación de inserción misma (la segunda operación) es O(n), ya que todos los elementos en ubicaciones más altas deben ser reubicados. Esta operación no puede ser optimizada.

Para la inserción Una implementación ingenua de una lista vinculada daría como resultado O(n) tiempo de inserción. Sin embargo, los buenos escritores de bibliotecas de listas enlazadas se optimizarían para los casos comunes, por lo que mantendrían una referencia a los últimos elementos (o tendrían una implementación circular de listas enlazadas), lo que daría como resultado un tiempo de inserción O(1).

En cuanto a la inserción en el medio. Algunas bibliotecas como la de C++, tienen una ubicación sugerida para la inserción. Tomarían un puntero al nodo de la lista, donde se agregará el nuevo. Dichas inserciones costarían O(1). No creo que puedas alcanzar O(1) por número de índice.

Esto se opone a una lista de matriz, donde la inserción en el centro fuerza el reordenamiento de todos los elementos superiores, por lo que tiene que ser una operación O(n).

Answer 3

Per the Java LinkedList source code, Java logra el O (1) para LinkedList operaciones cola dando a la entrada header un enlace al elemento de cola a través de header.previous. Por lo tanto, si desea el último elemento, la clase siempre puede devolver header.previous, lo que permite un tiempo constante.

Supongo que muchos otros lenguajes usan la misma estrategia básica.

Answer 4

Obviamente, probablemente haya mirado la entrada de la wikipedia http://en.wikipedia.org/wiki/Linked_list. Veo la tabla donde están especificando que tanto la inserción como la eliminación desde el final y en el medio de la lista tienen un rendimiento de O (1) pero no explican cómo determinaron eso.

Hay algunas respuestas interesantes a una pregunta similar aquí en stackoverflow en Why is inserting in the middle of a linked list O(1)?. El póster original de esa pregunta editó su publicación e hizo hincapié en que cree que cuando se dice que la inserción/eliminación es O (1) están hablando de la operación de inserción real y no de dónde insertarla. Eso tiene sentido, pero no he visto eso formalmente establecido en ninguno de los artículos que he encontrado en este momento.

Answer 5

Si no muta los nodos de su lista (simplemente) vinculada, necesita O (n) tiempo para insertar en una posición arbitraria en la lista (porque necesita copiar todos los nodos desde el principio del lista para la posición del nuevo elemento. Es O (1) para una lista mutable si ya tiene un puntero al nodo donde desea insertar un elemento, y O (n) si tiene que buscarlo. En ambos casos, solo necesita O (1) tiempo para insertar un elemento al principio de la lista. Si a menudo necesita insertar un elemento en el medio de la lista (caso O (n)), debe usar otra información estructura

Answer 6

Creo que una de las razones de su confusión es el hecho de que usted está pensando como si hubiera una lista de enlaces ideales/canónicos, que tiene o no tiene no tener ciertos punteros de cabeza/cola. La realidad es que cualquier estructura de datos lineal (es decir, no ramificada) que acceda a elementos pasando por punteros de elementos anteriores es básicamente una lista vinculada. Ya sea que guardes los punteros en los elementos primero, último, k-ésimo, depende totalmente de ti. Entonces, si necesita una lista donde frecuentemente necesita insertar/eliminar elementos en la 10ma posición, simplemente puede implementar uno que tenga un puntero adicional al 9 ° elemento y hacerlo en O (1) vez.

Otra cosa es que al iterar sobre los elementos de una lista enlazada, puede insertar un nuevo elemento justo después del elemento actual (y justo antes si es una lista de doble enlace) en O (1), porque ya tengo un puntero a eso.

Answer 7

Como señala @Kaleb Brasee, insertar en la cola en Java es O (1) porque Java usa una lista doblemente enlazada como su implementación LinkedList. Creo que esta es una opción bastante común para muchas implementaciones de SDK. Por ejemplo, la implementación de STL list está doblemente vinculada (source).