Matrices y listas enlazadas

Nov 06 2022
Algoritmos y estructuras de datos de cero a héroe
A veces es necesario almacenar una lista de elementos en la memoria. Suponga que está escribiendo una aplicación para administrar sus gastos.

A veces es necesario almacenar una lista de elementos en la memoria. Suponga que está escribiendo una aplicación para administrar sus gastos. Deberá almacenar los gastos como una lista en la memoria.

¿Deberías usar una matriz o una lista enlazada? Primero almacenemos los gastos en una matriz, porque es más fácil de entender. El uso de una matriz significa que todos sus gastos se almacenan de forma contigua (uno al lado del otro) en la memoria.

Ahora suponga que desea agregar un cuarto gasto. Pero el siguiente cajón está ocupado.

Es como salir con tus amigos y encontrar un lugar para sentarte, pero otro amigo se te une y no hay lugar para ellos. Tienes que moverte a un nuevo lugar donde quepan todos. En este caso, debe pedirle a su computadora una porción diferente de memoria que pueda cubrir cuatro gastos. Entonces necesitas mover todos tus gastos allí.

Y esto se convertirá en un bucle tan pronto como más amigos se unan a ti, pero seguro que siempre puedes agregar espacios adicionales por si acaso. Esta es una buena solución, pero debe tener en cuenta un par de inconvenientes:

  • Es posible que no necesite las ranuras adicionales que solicitó, y entonces esa memoria se desperdiciará.
  • Puede agregar más de 10 artículos a su lista de gastos y tener que mudarse de todos modos.

listas enlazadas

Una lista enlazada es una colección lineal de elementos de datos cuyo orden no viene dado por su ubicación física en la memoria. En cambio, cada elemento apunta al siguiente.

Con listas vinculadas, sus elementos pueden estar en cualquier lugar de la memoria.

Acceso Secuencial vs Aleatorio

El acceso secuencial significa que el costo de acceder al quinto elemento es 5 veces el costo de acceder al primer elemento, o al menos que hay un costo creciente asociado con la posición de un elemento en el conjunto. Esto se debe a que para acceder al quinto elemento del conjunto, primero debe realizar una operación para encontrar los elementos primero, segundo, tercero y cuarto, por lo que acceder al quinto elemento requiere cinco operaciones.

El acceso aleatorio significa que acceder a cualquier elemento del conjunto tiene el mismo costo que cualquier otro elemento del conjunto. Encontrar el quinto elemento de un conjunto sigue siendo una sola operación.

Matriz vs lista enlazada

En una matriz conocemos la dirección de cada elemento de la matriz. Como podemos ver en la imagen de arriba, tenemos una matriz con 5 unidades de memoria y esta matriz contiene 3 elementos, ya que los elementos se almacenan en ubicaciones de memoria contiguas (los elementos en una matriz están numerados y esta numeración comienza desde 0) sabemos dónde comienza y donde termina.

La posición de un elemento se denomina índice, por lo que en lugar de decir "8 está en la posición 1", la terminología correcta es "8 está en el índice 1".

Las matrices son excelentes si desea leer elementos aleatorios, ya que puede buscar cualquier elemento en su matriz al instante.

En una lista enlazada, cada elemento almacena la dirección del siguiente elemento de la lista. Un montón de direcciones de memoria aleatorias están vinculadas entre sí.

Es como una búsqueda del tesoro. Vas a la primera dirección y dice: "El siguiente elemento se puede encontrar en la dirección 008". Así que vas a la dirección 008 y dice: "El siguiente elemento se puede encontrar en la dirección 002" y así sucesivamente.

Agregar un elemento a una lista vinculada es fácil: lo coloca en cualquier lugar de la memoria y almacena la dirección con el siguiente elemento anterior.

Con listas vinculadas, nunca tendrá que mover sus artículos. También te evitas otro problema.

Digamos que vas a una película popular con cuatro de tus amigos. Los cinco están tratando de encontrar un lugar para sentarse, pero el cine está lleno. No hay cinco asientos juntos.

Bueno, a veces esto sucede con las matrices. Digamos que está tratando de encontrar 40,000 ranuras para una matriz. Su memoria tiene 40 000 ranuras, pero no tiene 40 000 ranuras juntas. ¡No puedes conseguir espacio para tu matriz!

Una lista enlazada es como decir “Separémonos y veamos la película”. Si hay espacio en la memoria, tiene espacio para su lista enlazada.

Si las listas enlazadas son mucho mejores en las inserciones, ¿para qué sirven las matrices?

arreglos

Las matrices son mejores que las listas vinculadas cuando intentamos acceder a nuestros elementos en la lista.

Suponga que desea leer el penúltimo elemento de una lista enlazada. No puedes simplemente leerlo, porque no sabes en qué dirección está.

Tienes que ir al elemento n.º 1 para obtener la dirección del elemento n.º 2 y así sucesivamente, hasta llegar al penúltimo elemento.

Las listas vinculadas son excelentes si va a leer todos los elementos de uno en uno. Pero si vas a seguir dando vueltas, las listas enlazadas son terribles.

Las matrices son diferentes. Conoce la dirección de cada elemento de su matriz, por lo que puede acceder a cualquier elemento de inmediato.

Insertar en medio de una lista

Suponga que desea que su lista de gastos funcione más como un calendario. Anteriormente, estaba agregando cosas al final de la lista.

Ahora desea agregarlos en el orden en que deben hacerse.

¿Qué es mejor si desea insertar elementos en el medio: matrices o listas vinculadas? Con la lista enlazada, es tan fácil como cambiar a qué apunta el elemento anterior.

Pero para las matrices, debe desplazar el resto de los elementos hacia abajo.

Y si no hay espacio, es posible que deba copiar todo en una nueva ubicación. Las listas son mejores si desea insertar elementos en el medio.

Eliminaciones

¿Qué sucede si desea eliminar un elemento? Nuevamente, las listas enlazadas son mejores, porque solo necesita cambiar a qué apunta el elemento anterior. Con las matrices, todo debe moverse hacia arriba cuando elimina un elemento.

Tiempos de ejecución para operaciones comunes en matrices y listas:

Las inserciones y eliminaciones son O (1) tiempo porque normalmente tendrá que realizar un seguimiento del primer y último elemento en una lista vinculada, por lo que solo necesitaría O (1) para agregar o eliminar.

¿Cuáles se usan más: arreglos o listas enlazadas? Obviamente, depende del caso de uso. Pero las matrices tienen mucho uso porque permiten el acceso aleatorio.

EJERCICIOS

Suponga que está creando una aplicación para un supermercado para tomar pedidos de los clientes. Su aplicación necesita almacenar una lista de pedidos. los clientes continúan agregando pedidos a esta lista, y los empleados quitan pedidos de la lista y los hacen. Es una cola de pedidos: los clientes agregan pedidos al final de la cola y el empleado toma el primer pedido de la cola y lo prepara.

¿Usaría una matriz o una lista enlazada para implementar esta cola? (Sugerencia: las listas enlazadas son buenas para inserciones/eliminaciones, y las matrices son buenas para el acceso aleatorio. ¿Cuál vas a hacer aquí?).

próximo

Las matrices y la lista enlazada también se utilizan para implementar otras estructuras de datos.

⬅️ Cómo funciona la memoria | Tabla de contenido | Pilas ➡️

© Copyright 2021 - 2022 | unogogo.com | All Rights Reserved