data structures - mis - ¿Por qué se borra en una sola lista vinculada O(1)?

eliminar lista de recordatorios iphone

Question

No entiendo por qué la eliminación al final de una única lista enlazada va en O (1), como dice el artículo de Wikipedia .

Una única lista enlazada está formada por nodos. Un nodo contiene algún tipo de datos y una referencia al siguiente nodo. La referencia del último nodo en la lista enlazada es nula.

--------------    --------------           --------------
| data | ref | -> | data | ref | -> ... -> | data | ref |
--------------    --------------           --------------

De hecho, puedo eliminar el último nodo en O (1). Pero en ese caso, no establece la referencia del último nodo, el anterior, en nulo, ya que aún contiene la referencia al último nodo eliminado. Así que me preguntaba si descuidan eso en el análisis del tiempo de ejecución. ¿O está de acuerdo en que no tiene que cambiar eso ya que la referencia, bueno, simplemente no apunta a nada, y eso se ve como nulo?

Porque si no se descuida, argumentaría que eliminar es O (n). Ya que tiene que recorrer toda la lista para llegar al último nodo y establecer su referencia también en nulo. Sólo en una lista de doble enlace sería realmente O (1).

-editar- Tal vez este punto de vista dé un poco más de claridad. Pero veo que "la eliminación de un nodo" elimina con éxito el propio nodo y establece la referencia anterior en nulo.

Answer 1

La adición / eliminación de CUALQUIER nodo en CUALQUIER ubicación es O (1). El código simplemente juega con costo fijo (cálculos de algunos punteros y malloc / frees) para agregar / eliminar el nodo. Este costo aritmético es fijo para cualquier caso específico.

Sin embargo, el costo para alcanzar (Indexación) el nodo deseado es O (n).

El artículo simplemente enumera la adición / eliminación en varias subcategorías (agregando en medio, principio, final) para mostrar que el costo de agregar en medio difiere de agregar en principio / final (pero los costos respectivos aún están fijos).

Answer 2

No estoy seguro de ver en el artículo de Wikipedia en el que dice que es posible eliminar la última entrada de una lista enlazada individualmente en O (1), pero que la información es incorrecta en la mayoría de los casos. Dado cualquier nodo individual en una lista enlazada, siempre es posible eliminar el nodo después de él en O (1) tiempo volviendo a cablear la lista alrededor de ese nuevo nodo. Por consiguiente, si le dieron un puntero al penúltimo nodo en una lista vinculada, entonces podría eliminar el último elemento de la lista en O (1) vez.

Sin embargo, si no tenía ningún puntero adicional en la lista que no fuera un puntero de cabeza, no podría eliminar el último elemento de la lista sin escanear hasta el final de la lista, lo que requeriría (n) tiempo, como usted ha notado Es absolutamente correcto que solo eliminar el último nodo sin cambiar primero los punteros en él sería una idea muy mala, ya que si hiciera esto, la lista existente contendría un puntero a un objeto desasignado.

Más generalmente, el costo de hacer una inserción o eliminación en una lista de enlaces individuales es O (1), suponiendo que tenga un puntero al nodo justo antes del que desea insertar o eliminar. Sin embargo, es posible que tenga que hacer un trabajo adicional (hasta Θ (n)) para encontrar ese nodo.

¡Espero que esto ayude!

Answer 3

O (1) simplemente significa "costo constante". No significa 1 operación. Significa "a lo más C" las operaciones con C siendo fija sin importar que otros parámetros cambien (como el tamaño de lista) De hecho, en el mundo a veces confuso de big-Oh: O (1) == O (22).

Por el contrario, eliminar toda la lista tiene un costo O (n), porque el costo cambia con el tamaño (n) de la lista.

Answer 4

Para referencias futuras, debo decir que después de algunas investigaciones encontré que ninguno de los argumentos proporcionados en respuesta a esta pregunta es relevante. La respuesta es que simplemente decidimos que la parte superior de la pila sea la cabecera de la lista vinculada (en lugar de la cola). Esto introducirá un ligero cambio en la rutina de empuje, pero luego el pop y el empujón permanecerán o (1).

Answer 5

Por ejemplo, puede tener un puntero al elemento antes del último ("segundo desde el final") y al eliminar: 1. Eliminar * al lado de este elemento "el segundo desde el final". 2. Establezca este "segundo desde el final" * junto a NULL

Answer 6

Sí, puede hacer esto en O (1) tiempo incluso si no mantiene un puntero al "elemento anterior".

Digamos que tienes esta lista, donde "cabeza" y "cola" son punteros estáticos, y "Fin" es un nodo marcado como un final. Puede usar "next == NULL" como de costumbre, pero en este caso debe ignorar el valor:

head -> 1 -> 2 -> 3 -> 4 -> 5 -> End <- tail

Ahora, se le asigna un puntero al nodo 3, pero no a su nodo anterior. Tienes los punteros de cabeza y cola también. Aquí hay algo de código de Python-ish, asumiendo una clase SingleLinkedList.

class SingleLinkedList:

    # ... other methods

    def del_node(self, node):  # We "trust" that we''re only ever given nodes that are in this list.
        if node is self.head:
            # Simple case of deleting the start
            self.head = node.next
            # Free up ''node'', which is automatic in python
        elif node.next is self.tail
            # Simple case of deleting the end. This node becomes the sentinel
            node.value = None
            node.next = None
            # Free up ''self.tail''
            self.tail = node
        else:
            # Other cases, we move the head''s value here, and then act
            # as if we''re deleting the head.
            node.value = self.head.value
            self.head = self.head.next
            new_head = self.head.next
            # Free up ''self.head''
            self.head = new_head

Por desgracia, esto reordena la lista y mueve los valores, lo que puede o no estar bien para su aplicación.

Answer 7

Si está incluyendo el costo de reparar el nodo colgante, aún puede hacerlo en O (1) con el uso del nodo centinela para el fin (también descrito en esa página).

Su lista "vacía" comienza con un solo centinela

Head -> [Sentinel]

Agrega algunas cosas

Head -> 1 -> 2 -> 3 -> [Sentinel] 

Ahora elimine la cola (3) marcando el nodo que era 3 como no válido, y luego eliminando el enlace al centinela anterior, y liberando la memoria para ello:

Head -> 1 -> 2 -> 3 -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel] -> [Sentinel] 
Head -> 1 -> 2 -> [Sentinel]

Answer 8

Si le asigna un puntero al nodo que desea eliminar en una sola lista vinculada, puede eliminar este nodo en un tiempo constante simplemente copiando el siguiente nodo en el nodo que desea eliminar.

M pointer to node to delete
M.data=M.next.data
M.next=M.next.next

De lo contrario, si necesita buscar el nodo, no puede hacerlo mejor que O (n)