Las listas vinculadas son preferibles a las matrices cuando:
a) necesita inserciones / eliminaciones en tiempo constante de la lista (como en la computación en tiempo real donde la previsibilidad del tiempo es absolutamente crítica)
b) no sabe cuántos elementos habrá en la lista. Con las matrices, es posible que deba volver a declarar y copiar memoria si la matriz crece demasiado
- Como desarrollador de software, ¿cómo obtengo la misma energía y entusiasmo que una vez tuve durante mi licenciatura?
- Cómo pasar del desarrollador de software al gerente de producto
- ¿Los probadores de software normalmente ofrecen el mismo salario que los desarrolladores de software por parte de las compañías de software?
- ¿Django se presta a diferentes tipos de proyectos que Rails?
- ¿Qué sugeriría que un ingeniero de software mediocre debería hacer para ser un experto en algo (tecnología, plataforma o lenguaje)?
c) no necesita acceso aleatorio a ningún elemento
d) desea poder insertar elementos en el medio de la lista (como una cola de prioridad)
Las matrices son preferibles cuando:
a) necesita acceso indexado / aleatorio a los elementos
b) conoce el número de elementos en la matriz con anticipación para que pueda asignar la cantidad correcta de memoria para la matriz
c) necesita velocidad cuando recorre todos los elementos en secuencia. Puede usar las matemáticas del puntero en la matriz para acceder a cada elemento, mientras que debe buscar el nodo en función del puntero para cada elemento en la lista vinculada, lo que puede provocar fallas en la página que pueden dar lugar a resultados de rendimiento.
d) la memoria es una preocupación. Las matrices llenas ocupan menos memoria que las listas vinculadas. Cada elemento de la matriz es solo los datos. Cada nodo de la lista vinculada requiere los datos, así como uno (o más) punteros a los otros elementos en la lista vinculada.
Las listas de matrices (como las de .Net) le brindan los beneficios de las matrices, pero asignan recursos dinámicamente para que no tenga que preocuparse demasiado por el tamaño de la lista y pueda eliminar elementos en cualquier índice sin ningún esfuerzo o recuperación. barajando elementos alrededor. En cuanto al rendimiento, las listas de matrices son más lentas que las matrices sin procesar.
Una de las decisiones de diseño de aplicaciones más importantes involucra qué estructura de datos usar. Las matrices y las listas vinculadas se encuentran entre las estructuras de datos más comunes, y cada una es aplicable en diferentes situaciones.
Las matrices y las listas vinculadas están diseñadas para almacenar múltiples elementos, la mayoría de las veces del mismo tipo. Según la Computer Desktop Encyclopedia , una matriz es una disposición ordenada de elementos de datos a los que se accede mediante sus índices de referencia. Una lista vinculada es un grupo de elementos, cada uno de los cuales contiene un puntero que apunta al siguiente elemento.
Este artículo explorará las características de cada estructura para ayudarlo a determinar cuál es el mejor para su aplicación.
Dimensionamiento
Las matrices pueden ser unidimensionales o multidimensionales, según sus requisitos. Por ejemplo, podría usar una matriz unidimensional para almacenar los puntajes de todos los estudiantes en una clase para una prueba. Una matriz multidimensional sería mejor para almacenar los puntajes de todos los estudiantes para todas las pruebas durante el semestre. La Figura A proporciona un ejemplo de una matriz unidimensional, y la Figura B muestra una matriz multidimensional.
Figura A
Matriz unidimensional
Figura B
Matriz multidimensional
En la Figura B, los puntajes pueden promediarse por prueba (cruzada), por estudiante (abajo) o por clase (conjunto completo), mientras se mantiene cada puntaje único.
A diferencia de las matrices, las listas vinculadas son, por su propia naturaleza, unidimensionales. Pueden ser listas individualmente vinculadas, como se muestra en la Figura C , donde el recorrido de la lista se puede hacer en una sola dirección, o listas doblemente vinculadas, como en la Figura D , donde cada elemento apunta tanto al elemento anterior como al siguiente. en la lista.
Figura C
Lista vinculada individualmente
Figura D
Lista doblemente vinculada
Asignación de memoria
Muy a menudo, las matrices son estáticas, con su tamaño definido en la creación. Además, la memoria asignada para las matrices es contigua. Por lo tanto, se usan típicamente cuando se conoce el número máximo de elementos en tiempo de diseño. El inconveniente de este enfoque es que las matrices grandes requieren grandes cantidades de memoria, que pueden no utilizarse, especialmente aquellas diseñadas para un número máximo de elementos que a menudo no se acercarán a su capacidad. Y en algunas plataformas, como ciertos dispositivos portátiles que usan sistemas operativos más antiguos, las restricciones de memoria podrían limitar el tamaño de los arreglos que puede usar.
Por otro lado, las listas vinculadas suelen ser dinámicas. Pueden crecer y encogerse según sea necesario en tiempo de ejecución. Debido a este rasgo, las listas vinculadas son más atractivas cuando se desconoce el número de elementos. Además, la memoria de la lista vinculada se asigna elemento por elemento y, por lo tanto, rara vez es contigua. La desventaja de poder lidiar con la incertidumbre es que agregar y eliminar elementos a listas vinculadas requiere más sobrecarga que simplemente asignar valores a elementos de matriz preasignados. Pero los únicos límites sobre la cantidad de memoria que se puede asignar a una lista vinculada están impuestos por el tamaño del montón de memoria utilizado por la aplicación.
Acceso a elementos
Se accede a los elementos dentro de las matrices por sus índices. Por lo tanto, el acceso a los datos es fácil y rápido si sabe qué elemento recuperar. Si no conoce el índice del elemento necesario, pero los elementos se ordenan según un valor clave, puede realizar algoritmos de búsqueda altamente eficientes para localizar elementos específicos. Estos algoritmos permiten solo un número mínimo de comparaciones para ubicar un elemento único. También hay varios algoritmos establecidos y eficientes para ordenar y fusionar matrices. Sin embargo, las matrices son ineficientes cuando es probable que cambie el orden de sus elementos. Mantener una matriz ordenada tras la eliminación o inserción de elementos podría requerir la transferencia de cada elemento de la matriz.
Las listas vinculadas generalmente se recorren elemento por elemento hasta que se encuentre una coincidencia. Debido a que no se garantiza que la memoria para las listas vinculadas sea contigua, este recorrido de la lista es el único método para buscar en la lista (sin involucrar el uso de otras estructuras de datos como índices). La ventaja de la memoria no contigua es que reordenar la lista simplemente implica manipular los enlaces. La inserción o eliminación de un elemento requiere solo un par de modificaciones de puntero. La transferencia de los datos reales no es necesaria en absoluto.
Rompiendo las reglas
El uso de construcciones específicas del lenguaje puede permitir lo mejor de ambos mundos. Con C, los punteros a variables u objetos se pueden usar como matrices del tipo correspondiente si apuntan al primer elemento de una matriz asignada. Esto permite utilizar un puntero como matriz, pero cuando es necesario cambiar el tamaño, la función realloc () asigna un nuevo bloque de memoria y transfiere todos los elementos existentes a la nueva ubicación. Esta técnica permite cambiar el tamaño dinámico de una matriz mientras se mantiene la memoria contigua y la indexación de elementos.
Con Java, la clase de lista enlazada proporcionada ofrece una lista enlazada indexada que admite todos los métodos de lista estándar (superior, siguiente, anterior, etc.), así como la operación indexada. Los métodos indexOf () , get () y set () permiten el acceso de tipo matriz a los elementos de la lista. Además, Java proporciona una clase ArrayList que representa una implementación de matriz de tamaño variable de la clase de lista. Ambas clases admiten métodos para devolver matrices verdaderas de sus representaciones de lista.
Los lenguajes de programación continúan siendo más avanzados, y hay menos distinción entre los diversos tipos de implementaciones de datos a medida que sus estructuras se expanden para incluir las fortalezas y corregir las deficiencias encontradas en los modelos estándar. Sin embargo, siempre será importante recordar dónde se originaron estas estructuras y cómo todavía se usan dentro de las clases más nuevas. Aunque estas implementaciones más nuevas ocultan los detalles del programador, la sobrecarga computacional y los recursos necesarios no cambian.
Tomar la decisión
Si sus datos se representan mejor utilizando una estructura multidimensional, o si se conoce de antemano el número de elementos y seguirá siendo coherente, lo mejor es una matriz. Si sus datos se representan fácilmente en una dimensión, y se desconoce el número de elementos o se espera que cambie a menudo a lo largo de la operación de su programa, una lista vinculada es más eficiente.
Si se buscarán y accederán a sus datos con frecuencia, pero cambiarán con poca frecuencia, la matriz ofrece la menor sobrecarga para sus operaciones esperadas. Si espera agregar o restar elementos regularmente, especialmente si necesita mantener un orden ordenado, la versatilidad de la lista vinculada será de mayor beneficio