Hardware

Decidir si usar una matriz o una lista enlazada

Una de las decisiones de diseño de aplicaciones más importantes implica qué estructura de datos usar. Las matrices y las listas enlazadas se encuentran entre las estructuras de datos más comunes y cada una es adecuada para diferentes situaciones.

Tanto las matrices como las listas enlazadas están diseñadas para almacenar múltiples elementos, generalmente del mismo tipo.de acuerdo a enciclopedia de escritorio de computadora, una matriz es una disposición ordenada de elementos de datos, a los que se accede por su índice de referencia. Una lista enlazada es un conjunto de elementos, cada elemento contiene un puntero al elemento siguiente.

Este artículo explorará las características de cada estructura para ayudarlo a determinar qué estructura es la mejor para su aplicación.

dimensionamiento
Las matrices pueden ser unidimensionales o multidimensionales, según sus requisitos. Por ejemplo, puede usar una matriz unidimensional para almacenar los puntajes de las pruebas de todos los estudiantes en una clase. Las matrices multidimensionales son mejores para almacenar todos los puntajes de las pruebas de todos los estudiantes a lo largo del semestre. Figura A proporcionar un ejemplo de una matriz unidimensional, y Figura B Muestra una matriz multidimensional.

Figura A
Decidir si usar una matriz o una lista enlazada
matriz unidimensional
Figura B
1661196672 39 Decidir si usar una matriz o una lista enlazada
Matrices multidimensionales

En la Figura B, los puntajes se pueden promediar por prueba (cruce), estudiante (rechazo) o clase (conjunto completo), mientras se mantiene cada puntaje único.

En comparación con las matrices, las listas enlazadas son inherentemente unidimensionales.Pueden ser listas enlazadas individualmente como Figura Cdonde el recorrido de la lista solo se puede hacer en una dirección, o una lista doblemente enlazada, como en Figura Ddonde cada elemento apunta al elemento anterior y siguiente de la lista.

Figura C
1661196673 562 Decidir si usar una matriz o una lista enlazada
lista única
Figura D
1661196673 887 Decidir si usar una matriz o una lista enlazada
Lista doblemente enlazada

asignación de memoria
En la mayoría de los casos, las matrices son estáticas y su tamaño se define en el momento de la creación. Además, la memoria asignada para la matriz es contigua. Por lo tanto, se suelen utilizar cuando se conoce el número máximo de elementos en el momento del diseño. La desventaja de este enfoque es que los arreglos grandes requieren mucha memoria, que puede dejarse sin usar, especialmente aquellos diseñados para la mayor cantidad de elementos, que generalmente no se acercan a su capacidad. En algunas plataformas, como algunos dispositivos portátiles con sistemas operativos más antiguos, las limitaciones de memoria pueden limitar el tamaño de la matriz que puede usar.

LEER  El nuevo iPad de Apple: características que los usuarios empresariales adorarán

Por otro lado, las listas enlazadas suelen ser dinámicas. Pueden crecer y reducirse según sea necesario en tiempo de ejecución. Debido a esta propiedad, las listas enlazadas son más atractivas cuando se desconoce el número de elementos. Además, la memoria de lista enlazada se asigna elemento por elemento, por lo que rara vez es contigua. La desventaja de poder manejar el no determinismo es que agregar y eliminar elementos de una lista vinculada requiere más gastos generales que solo asignar valores a elementos de matriz preasignados. Sin embargo, el único límite de la cantidad de memoria que se puede asignar para una lista vinculada es el tamaño del montón de memoria que utiliza la aplicación.

elemento de acceso
Se accede a los elementos de una matriz por su índice. Entonces, si sabe qué elemento recuperar, el acceso a los datos se vuelve fácil y rápido. Si no conoce el índice del elemento que desea, pero ordena los elementos en función de algún valor clave, puede realizar un algoritmo de búsqueda eficiente para ubicar un elemento específico. Estos algoritmos permiten solo un número mínimo de comparaciones para localizar elementos únicos. También hay varios algoritmos establecidos y eficientes para clasificar y fusionar matrices. Sin embargo, las matrices son ineficientes cuando el orden de los elementos puede cambiar. Mantener una matriz ordenada al quitar o insertar elementos puede requerir la transferencia de cada elemento de la matriz.

Las listas enlazadas generalmente se recorren elemento por elemento hasta que se encuentra una coincidencia. Debido a que no se garantiza que la memoria de una lista enlazada sea contigua, este tipo de recorrido de lista enlazada es la única forma de buscar en la lista enlazada (sin implicar el uso de otras estructuras de datos como índices). El beneficio de la memoria no contigua es que reordenar la lista solo implica operar el encadenamiento. Insertar o eliminar elementos solo requiere modificar algunos punteros. No hay necesidad de transmitir datos reales en absoluto.

romper las reglas
Lo mejor de ambos mundos se puede lograr utilizando construcciones específicas del lenguaje. En 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 que los punteros se usen como matrices, pero cuando se requiere cambiar el tamaño, reasignar() La función asigna un nuevo bloque de memoria y transfiere todos los elementos existentes a la nueva ubicación. Esta técnica permite el redimensionamiento dinámico de arreglos mientras mantiene la memoria contigua y los índices de los elementos.

Para Java, la clase de lista vinculada proporcionada proporciona una lista vinculada indexada que admite todos los métodos de lista estándar (superior, siguiente, anterior, etc.), así como operaciones de indexación.Este índice(), obtener()y poner() Los métodos permiten un acceso similar a una matriz a los elementos de la lista.Además, Java proporciona una lista de arreglo Una clase que representa una implementación de matriz redimensionable de la clase List. Ambas clases admiten métodos que devuelven matrices reales de sus representaciones de lista.

Los lenguajes de programación continúan volviéndose más avanzados, con menos distinción entre los diversos tipos de implementaciones de datos, a medida que sus estructuras se expanden para abarcar las fortalezas y corregir las deficiencias del modelo estándar. Sin embargo, siempre es importante recordar el origen de estas estructuras y cómo se utilizan en las nuevas clases. Aunque estas implementaciones más nuevas ocultan los detalles al programador, la sobrecarga computacional y los recursos necesarios no han cambiado.

Toma una decision
Si sus datos se representan mejor usando una estructura multidimensional, o si la cantidad de elementos se conoce de antemano y será consistente, entonces las matrices son mejores. Las listas vinculadas son más eficientes si sus datos se representan fácilmente en una dimensión y se desconoce el número de elementos o se espera que cambie con frecuencia a lo largo de la ejecución del programa.

Si sus datos se buscarán y accederán con frecuencia, pero rara vez se modificarán, esta matriz proporciona la menor sobrecarga para la operación prevista. La versatilidad de una lista enlazada es aún más beneficiosa si espera que los elementos se agreguen o resten regularmente, especialmente si necesita mantener un orden ordenado.

En última instancia, sus necesidades operativas y de datos determinarán qué estructura es la mejor para su aplicación.

LEER  Hola PC "reales", ¿adiós técnicos de soporte?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *

Botón volver arriba