Array vs Lista Enlazada – Diferencia entre Array y Lista Enlazada

¿Te has preguntado alguna vez cómo se almacenan los datos en la memoria del ordenador? No se puede simplemente lanzar los datos en la memoria sin hacer una estructura adecuada para los datos.

Para proporcionar una estructura organizada para los datos que se almacenan dentro de la memoria del ordenador para que podamos utilizar y gestionar los datos almacenados de la manera más eficiente posible, utilizamos las Estructuras de Datos.

Todos los lenguajes de programación proporcionan estructuras de datos fundamentales como int, char, float, etc. para almacenar los valores de tipo primitivo. Pero con el uso de tipos de datos definidos por el usuario podemos crear la estructura de datos que necesitemos. Es como crear nuestra casa con ladrillos, podemos hacer cualquier tipo de estructura que queramos.

Aquí en este artículo veremos dos tipos de datos definidos por el usuario más utilizados: Arrays y Listas Enlazadas, Diferencia entre Array y Listas Enlazadas y su implementación.

Array

El tipo más simple de estructura de datos es Array que se utiliza para almacenar conjunto de datos similares en bloques continuos de memoria bajo un encabezado común o nombre de variable. Su simplicidad conlleva algunas barreras como la necesidad de un bloque continuo de memoria y si la memoria libre no está disponible en un bloque contiguo se vuelve ineficiente el uso de arrays.

Representación de Arrays

Representación de Arrays (Fuente)

La indexación de los arrays comienza con 0, y se puede acceder a cada elemento del array utilizando su índice. La operación en el array es muy rápida ya que se puede acceder a cualquier elemento directamente usando la indexación del array. El nombre del array es la dirección base del mismo y se puede acceder a todos los demás elementos utilizando la dirección base porque la memoria asignada al array es consecutiva.

Lista Enlazada

Por otro lado, una estructura de datos simple pero muy útil que no necesita bloques contiguos de memoria es la Lista Enlazada. Se utilizan en situaciones en las que se necesita asignar memoria dinámicamente, es decir, durante el tiempo de ejecución de un programa. Se puede visualizar como un tren en el que tenemos un motor (cabeza) y todos los vagones (nodos) están vinculados a la máquina del tren, ya sea directa o indirectamente a través de otros vagones.

Representación de la lista enlazada

Representación de la lista enlazada (Fuente)

La lista enlazada es un tipo de datos definido por el usuario en el que todos los nodos de la lista están vinculados utilizando punteros. Para acceder a cualquier nodo de la lista, debemos recorrer la lista linealmente a diferencia de la matriz donde podemos acceder directamente a los elementos.

Array vs Lista Enlazada – Diferencia entre Array y Lista Enlazada

Parámetros Array Lista Enlazada
Definición Es una colección de elementos que tienen el mismo tipo de datos con un nombre común. Es una colección ordenada de elementos que están conectados por enlaces o punteros.
Tamaño Fijo, una vez declarado no puede ser cambiado. Variable, puede ser cambiado durante el tiempo de ejecución.
Asignación de memoria Requiere bloques contiguos de memoria. Se puede asignar memoria al azar.
Acceso Directo o de acceso aleatorio, es decir, Especificar el índice o subíndice de la matriz. Acceso secuencial, es decir, Recorrer desde el primer nodo de la lista por el puntero.
Inserción y Borrado Relativamente lento, ya que para insertar o borrar cualquier elemento, es necesario desplazar otros elementos para ocupar el espacio vacío o hacer espacio. Más rápido, fácil y eficiente ya que sólo se requiere enlazar o desenlazar un nodo.
Búsqueda Búsqueda binaria y búsqueda lineal Búsqueda lineal
Espacio extra No se requiere espacio extra. Para enlazar nodos de la lista, se utilizan punteros que requieren espacio extra.
Utilización de la memoria Ineficiente Eficiente
Tipos Puede ser unidimensional, bidimensional o multidimensional. Puede ser una lista enlazada simple, doble o circular.

Implementación de arrays en C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

#include<iostream>
using namespace std;
int main()
{
int arr; // declarar un array de enteros de tamaño 5
arr=5; // asignar valores a los elementos del array
arr=4; // observa que la indexación del array comienza en 0 y termina en el tamaño-1
arr=3;
arr=2;
arr=1;
for(int=0;i<5;i++)
cout<<arr<<«; // imprimir los elementos del array
return 0;
}

Salida

5 4 3 2 1

Implementación de listas enlazadas en C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#include<iostream>
using namespace std;
/* Creación de una estructura definida por el usuario para almacenar datos en la lista enlazada */
struct Node
{
int data;
struct Node *next; // puntero a los nodos de enlace de la lista
};
struct Node* head = NULL; // Inicialmente no hay ningún elemento en la lista, por lo que head apunta a ninguna parte
/* función para insertar y enlazar nodos a la lista */
void insert(int new_data)
{
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node)); // asignando memoria dinámicamente
nuevo_nodo->datos = nuevos_datos;
nuevo_nodo->siguiente = cabeza;
cabeza = nuevo_nodo;
} ¡
/* función para mostrar los datos de la lista */
void display()
{
struct Node* ptr;
ptr = head;
while (ptr != NULL)
{
cout<< ptr->data <<» «;
ptr = ptr->next;
}
}
int main()
{
insert(5); // insertando datos en la lista
insert(1);
insert(4);
insert(6);
insert(7);
cout<<«La lista enlazada es: «;
display();
return 0;
}

Salida

La lista enlazada es: 7 6 4 1 5

Tutorial de vídeo

Leave a Reply

Deja una respuesta

Tu dirección de correo electrónico no será publicada.