Se dice que la complejidad de la operación de eliminación y adición de LinkedList es de O(1) . y en el caso de ArrayList es de O(n) .
Cálculo para ArrayList de tamaño "M": si quiero eliminar el elemento en la posición N, entonces puedo ir directamente a la posición N usando el índice de una sola vez (no tengo que atravesar hasta el índice N) y luego puedo eliminar el elemento, hasta este punto, la complejidad es O (1), entonces tendré que cambiar el resto de los elementos (cambios MN) para que mi complejidad sea lineal, es decir, O (M-N + 1). y, por lo tanto, la eliminación o inserción al final me dará el mejor rendimiento (como N ~ M) y la eliminación o inserción al principio será peor (como N ~ 1).
Ahora el LisnkedList de tamaño "M": como no podemos alcanzar directamente el elemento Nth en LinkedList, para acceder al elemento Nth tenemos que atravesar N elementos, por lo que la búsqueda en LinkedList es más costosa que ArrayList ... pero Eliminar y se dice que las operaciones de adición son de O (1) en el caso de LinkedList ya que, en LinkedList, el cambio no está involucrado, pero hay una operación transversal involucrada, ¿verdad? por lo que la complejidad debe ser de orden O(n), donde el peor rendimiento estará en el nodo de cola y el mejor rendimiento estará en el nodo de cabeza.
¿Alguien podría explicarme por qué no consideramos el costo transversal al calcular la complejidad de la operación de eliminación de LinkedList?
Entonces quiero entender cómo funciona en el paquete java.util. y si quiero implementar lo mismo en C o C ++, ¿cómo lograría el O (1) para la eliminación e inserción aleatorias en LinkedList?
Se dice que las operaciones de eliminar y agregar son de O (1) en el caso de
LinkedListya que, enLinkedList, el cambio no está involucrado, pero hay una operación transversal involucrada, ¿verdad?
Agregar a cualquiera de los extremos de una lista vinculada no requiere un recorrido, siempre que mantenga una referencia a ambos extremos de la lista. Esto es lo que hace Java para sus métodos add y addFirst / addLast .
Lo mismo ocurre con los métodos remove y removeFirst / removeLast sin parámetros: operan en los extremos de la lista.
Las operaciones remove(int) y remove(Object) , por otro lado, no son O(1). Requieren recorrido, por lo que identificó correctamente sus costos como O(n).
La complejidad de eliminar se considera que ya tiene el puntero en la posición correcta del elemento que desea eliminar...
No se considera el costo que tomó para encontrarlo
Information on this topic is now available on Wikipedia at: Search data structure +----------------------+----------+------------+----------+--------------+ | | Insert | Delete | Search | Space Usage | +----------------------+----------+------------+----------+--------------+ | Unsorted array | O(1) | O(1) | O(n) | O(n) | | Value-indexed array | O(1) | O(1) | O(1) | O(n) | | Sorted array | O(n) | O(n) | O(log n) | O(n) | | Unsorted linked list | O(1)* | O(1)* | O(n) | O(n) | | Sorted linked list | O(n)* | O(1)* | O(n) | O(n) | | Balanced binary tree | O(log n) | O(log n) | O(log n) | O(n) | | Heap | O(log n) | O(log n)** | O(n) | O(n) | | Hash table | O(1) | O(1) | O(1) | O(n) | +----------------------+----------+------------+----------+--------------+ * The cost to add or delete an element into a known location in the list (ie if you have an iterator to the location) is O(1). If you don't know the location, then you need to traverse the list to the location of deletion/insertion, which takes O(n) time. ** The deletion cost is O(log n) for the minimum or maximum, O(n) for an arbitrary element.Sí, tiene razón si considera dos operaciones (indexar e insertar) de una sola vez. No es cierto en este caso porque cuando estás insertando un nodo en medio de una lista enlazada, se asume que ya estás en la dirección donde tienes que insertar el nodo.
La complejidad temporal de acceder al nodo es O(n), mientras que solo insertar un nodo es O(1).
La inserción en el encabezado requiere que agregue el elemento y actualice el puntero del encabezado.
newnode->next = head; head = newnode;La inserción en la cola requiere que mantenga un puntero en el elemento de la cola, agregue el elemento en la cola y actualice el puntero de la cola.
tail->next = newnode; tail = newnode;Eliminar el elemento de encabezado requiere actualizar el encabezado y eliminar el elemento de encabezado anterior.
temp = head; head = head->next; delete temp; /* or free(temp); */Todo lo anterior son operaciones triviales y no dependen de la cantidad de elementos en la lista enlazada. Por lo tanto, son O(1)
Sin embargo, eliminar el elemento de cola sería una operación O(n) porque, aunque podría tener un puntero de cola, aún necesitaría el penúltimo nodo que se configuraría como el nuevo nodo de cola (actualizando el puntero de cola y configurando el siguiente miembro del nodo a NULL). Para ello, debe recorrer toda la lista enlazada.
penultimate_el = find_penultimate_el(head); /* this is O(n) operation */ delete tail; /* or free(tail) */ tail = penultimate_el; tail->next = NULL;