Complejidad del tiempo de lista vinculada
Lista vinculada individualmente
El siguiente diagrama muestra una lista individual de tres elementos:
Cada elemento tiene dos partes. La primera parte tiene los datos. La segunda parte tiene un puntero que apunta al siguiente elemento. El segundo y tercer elemento son similares a los primeros. El último elemento tiene un puntero nulo. Con la lista vinculada individualmente, el recorrido solo puede ir en una dirección: la dirección hacia adelante.
Los elementos de una lista vinculada no están abordados por referencias (subíndices en corchetes), todo es igual. Los iteradores acceden a ellos (punteros). En el caso de la lista vinculada individualmente, el iterador debe comenzar desde el principio y moverse del elemento por elemento, para llegar al elemento previsto.
Lista doblemente vinculada
El siguiente diagrama muestra una lista doblemente vinculada de tres elementos:
Aquí, cada elemento tiene tres partes. La primera parte tiene un puntero que apunta al elemento anterior. La segunda parte tiene los datos. La tercera parte tiene un puntero que apunta al siguiente elemento. La primera parte del primer elemento tiene un puntero que apunta a NULL. La tercera parte del último elemento tiene un puntero que apunta a NULL. Con la lista doblemente vinculada, el recorrido puede ir en cualquier dirección: la dirección hacia adelante o la dirección inversa.
Los elementos de una lista vinculada no están abordados por referencias (subíndices en soportes cuadrados). Los iteradores acceden a ellos (punteros). En el caso de una lista doblemente vinculada, el iterador puede moverse en cualquier dirección, pero tiene que comenzar en cualquier extremo. El movimiento no puede comenzar oficialmente desde la lista.
El objetivo de este artículo es determinar qué se conoce como la complejidad del tiempo para la lista vinculada.
Complejidad del tiempo en general
La complejidad del tiempo es el tiempo de ejecución relativo de algún código. La complejidad del tiempo también puede verse como el número de operaciones principales del código.
Tiempo constante
Se dice que una operación principal, como Insertar o Eliminar, tiene una complejidad de tiempo de tiempo constante porque la acción puede verse como una vez que ocurre una vez. Está escrito como:
O (1)
donde 1 significa tiempo o acción constante que ocurre una vez. Esto usa la notación Big-O que comienza con O en mayúsculas seguidas de paréntesis. Dentro de la paréntesis es el número de operaciones principales para la tarea.
Tiempo lineal
Leer una matriz desde el principio: un elemento después del otro que busca un elemento en particular, se conoce como una búsqueda lineal.
El elemento buscado se puede encontrar en algún lugar en el medio y la búsqueda se detendría. Esta sigue siendo una búsqueda lineal. La complejidad del tiempo para la búsqueda lineal se escribe como:
En)
donde n es el número máximo posible de operaciones.
Operaciones principales de la lista vinculada
buscando
Para una lista vinculada individualmente, para moverse de un elemento al siguiente, el código debe usar el puntero del elemento actual, que apunta al siguiente elemento. Este no es el caso con las matrices. Para una lista doblemente vinculada, para moverse de un elemento al siguiente, el código debe usar el puntero del elemento actual que apunta al siguiente elemento. Este no es el caso con las matrices. Para una lista doblemente vinculada, para moverse de un elemento al anterior, el código debe usar el puntero del elemento actual que apunta al elemento anterior. Este no es el caso con las matrices.
Supresión
Cuando se elimina un elemento actual, el puntero del elemento anterior que le estaba apuntando a él debe hacerse para señalar el siguiente elemento. Luego, el puntero del siguiente elemento que apuntaba a él debe hacerse para señalar el elemento anterior.
Inserción
Cuando se inserta el elemento actual, el puntero del elemento anterior que apunta al siguiente elemento debe hacerse para señalar el elemento actual. El puntero del siguiente elemento que apuntaba al elemento anterior debe hacerse para señalar el elemento actual.
Se debe hacer que el puntero delantero del elemento actual apunte al nuevo elemento siguiente. El puntero posterior del elemento actual debe hacerse para señalar el nuevo elemento anterior.
Complejidad del tiempo para la lista vinculada
Cuando se habla de complejidad del tiempo para una lista vinculada, es la complejidad del tiempo para la búsqueda, inserción y eliminación de lo que se habla de. No es la complejidad del tiempo para construir la lista vinculada de la que se habla. La complejidad del tiempo para construir una lista vinculada es un problema diferente.
buscando
Para que una lista vinculada individualmente se busque un elemento particular (datos), el código de búsqueda debe escanear el elemento de la lista por elemento desde el principio. Para que una lista doblemente vinculada se busque un elemento en particular, el código de búsqueda debe escanear el elemento de la lista por elemento desde el principio. O escanear la lista, elemento por elemento, desde el final. La complejidad del tiempo de búsqueda para una lista vinculada (individual o doblemente) es:
En)
donde n es el número de elementos en la lista. No importa si se encontró el elemento, en algún lugar dentro de la lista.
Inserción
La inserción se considera una operación principal. Para insertar un elemento en una lista vinculada, la búsqueda debe realizarse, para llegar al puesto, para inserción. La complejidad del tiempo para la búsqueda es o (n). La complejidad del tiempo para la acción de insertar es o (1). Entonces, la complejidad del tiempo para la inserción en una lista vinculada es O (n + 1). Para simplificar, la complejidad del tiempo para la inserción de un elemento, en una lista vinculada, se escribe como:
En)
Supresión
La eliminación se considera como una operación principal. Para eliminar un elemento en una lista vinculada, la búsqueda debe realizarse para llegar al puesto de eliminación. La complejidad del tiempo para la búsqueda es o (n). La complejidad del tiempo para la acción de eliminar es o (1). Entonces, la complejidad del tiempo para la eliminación en una lista vinculada es O (n + 1). Para simplificar, la complejidad del tiempo para la eliminación de un elemento, fuera de una lista vinculada, se escribe como:
En)
Construyendo una lista vinculada en C
Para construir una lista doblemente vinculada en C, use el objeto struct. El primer miembro de datos debe tener un puntero que apunte a la estructura anterior. El tercer miembro de datos debe tener un puntero que apunte a la siguiente estructura. El miembro de los datos intermedios debe tener los datos. El primer miembro de datos de la primera estructura debe apuntar a NULL. El tercer miembro de datos de la última estructura también debe apuntar a NULL.
En el caso de la lista vinculada individualmente, omita el primer miembro de datos.
Conclusión
La complejidad del tiempo para buscar una lista vinculada es:
En)
Para simplificar, la complejidad del tiempo para insertar un elemento en una lista vinculada es:
En)
y no o (1).
Para simplificar, la complejidad del tiempo para la eliminación de un elemento, fuera de una lista vinculada, es:
En)
y no o (1).