Listas Estáticas

Una aproximación a las estructuras de datos, con enfoque en las listas. Definición e implementación de listas estáticas dentro del lenguaje C.

Estructuras de datos.

Dentro de las estructuras de datos, podemos distinguir dos grandes grupos: las estructuras lineales y las no lineales. Las primeras reciben su nombre porque los datos están conectados únicamente con el elemento siguiente (y/o anterior), lo que hace que su tamaño crezca de forma lineal. Las segundas, en cambio, pueden formar relaciones con más de un único elemento, lo que permite un crecimiento no lineal.
También podemos clasificarlas según su implementación base: ya sea con arreglos o con nodos. Un arreglo es estático, por lo que las estructuras implementadas con ellos tienen poca (o nula) flexibilidad, ya que poseen un tamaño inicial bien definido y, por tanto, un espacio en memoria fijo. En cambio, las estructuras basadas en nodos son mucho más flexibles, pues pueden reservar o liberar espacio en tiempo de ejecución. Por ello, haremos la distinción entre estructuras estáticas y dinámicas, respectivamente.

Tabla 1: Diferencias entre estructuras lineales y no lineales.
Característica	Lineales	No lineales
Tienen relación directa con más de un sucesor	No	Sí
Tienen relación directa con más de un predecesor	No	Solo grafos
El espacio en memoria crece de forma lineal	Sí	No
Ordenada	Sí	No necesariamente
Ejemplos	Listas, pilas, colas, conjuntos, tablas hash (con resolución de colisiones por reubicación)	Grafos, árboles, tablas hash (co n resolución de colisiones por listas enlazadas)

Listas Estáticas.

Una lista en programación es una estructura de datos lineal y ordenada que almacena una secuencia de elementos. Cada elemento ocupa una posición determinada (índice) y puede ser accedido, modificado o eliminado según su ubicación. Una lista estática es una lista cuya implementación se basa en arreglos. Esta implementación ofrece ventajas como un acceso rápido y eficiente a los elementos, y resulta sencilla de entender e implementar para los desarrolladores principiantes. Sin embargo, también presenta desventajas importantes, como su escasa flexibilidad. Además, mantener la coherencia en el orden de los elementos puede requerir reordenamientos frecuentes, lo cual impacta el rendimiento cuando se realizan muchas inserciones o eliminaciones.

En las listas es común definir métodos que abstraen comportamientos frecuentes, como insertar, recuperar, modificar o eliminar elementos. Dependiendo del tipo de implementación deseada, estos métodos pueden adaptarse a diferentes necesidades. Por ejemplo, si se alcanza el tamaño máximo de la lista, se podría reubicar su contenido incrementando su capacidad en un valor determinado, o mantener siempre un tamaño fijo y reutilizar los espacios liberados. Esto dependerá del enfoque del programador. En este caso, nuestra lista estática mantendrá siempre un tamaño fijo, por lo que al eliminar un elemento, ese espacio podrá ser reutilizado manualmente.

Listas Estáticas Desordenadas

Para este y los artículos posteriores crearemos siempre nuestra estructura a través de un typedef y antes de implementar sus métodos concretos, agregaremos nuestros métodos generales 'new' y 'delete' que servirán a modo de constructor y destructor respectivamente. De esta forma podemos abstraer nuestros métodos y poder instanciar tantas listas como queramos en las situaciones que necesitemos.

#include <stdio.h>
#include<stdbool.h>
#include <stdlib.h>

typedef struct _static_list {
	int *array;
	size_t capacity, size;
} StaticList;

StaticList *new_static_list(size_t);
void delete_static_list(StaticList*);

int main(int argc, char *argv[]) {
	StaticList *list = new_static_list(10);
	delete_static_list(list);

	return 0;
}

StaticList *new_static_list(size_t capacity) {
	StaticList *list = (StaticList*) malloc( sizeof(StaticList) );
	if(!list) {
		fprintf(stderr, "Error al reservar memoria para la lista estatica.
");
		exit(EXIT_FAILURE);
	}

	list->array = (int*) malloc( capacity * sizeof(int) );
	if(!list->array) {
		fprintf(stderr, "Error al reservar memoria para el arreglo de la lista estatica.");
		exit(EXIT_FAILURE);
	}

	list->capacity = capacity;
	list->size = 0;

	return list;
}

void delete_static_list(StaticList *list) {
	for(int i = 0; i < list->size; i++) {
		list->array[i] = 0;
	}
	free(list->array);
	list->array = NULL;
	list->capacity = 0;
	list->size = 0;
	free(list);
}

Con estos métodos implementados, podemos ahora sí realizar la implementación de nuestros métodos, tomando en consideración el caso más extremo de la lista, es decir una lista desordenada, donde podemos insertar datos al inicio, final o cualquier posición dentro de la misma que deseemos, igual eliminaciones. Así mismo consideraremos algunos métodos auxiliares que serán de uso común en otros métodos.

Métodos auxiliares

Estos métodos son fundamentales para interactuar de forma segura y eficiente con nuestra lista. No solo se reutilizan en diferentes funciones, sino que también proporcionan validaciones y accesos directos a datos importantes. Aquí encontramos:

Is Void: valida si la lista no contiene ningún elemento.
Is Full: verifica si la lista alcanzó su capacidad máxima.
Get: recupera un elemento específico según su índice.
Get First Index: busca el primer índice donde aparece un valor determinado.
Get Last Index: busca el último índice donde aparece un valor determinado; junto con Get y Get First Index, conforma los métodos de búsqueda.
Count: cuenta todas las apariciones de un valor, útil para obtener métricas como la moda.

bool static_list_is_void(StaticList list) {
	return !list.size;
}

bool static_list_is_full(StaticList list) {
	return list.size == list.capacity;
}

int static_list_get(StaticList list, size_t index) {
	if(index < 0) {
		return ERROR_VALUE;
	}
	return list.array[index];
}

int static_list_get_first_index(StaticList list, int value) {
	if(static_list_is_void(list)) {
		return -1;
	}

	int index = -1;
	for(int i = 0; i < list.size; i++) {
		if(list.array[i] == value) {
			index = i;
			break;
		}
	}

	return index;
}

int static_list_get_last_index(StaticList list, int value) {
	if(static_list_is_void(list)) {
		return -1;
	}

	int index = -1;
	for(int i = list.size - 1; i >= 0; i--) {
		if(list.array[i] == value) {
			index = i;
			break;
		}
	}

	return index;
}

size_t static_list_count(StaticList list, int value) {
	if(static_list_is_void(list)) {
		return 0;
	}

	int count = 0;
	for(int i = 0; i < list.size; i++) {
		if(list.array[i] == value) {
			count++;
		}
	}

	return count;
}

Inserción.

Para insertar elementos en la lista, utilizamos un enfoque inspirado en el algoritmo de ordenamiento por inserción: desplazamos los elementos una posición hacia adelante para abrir espacio, excepto cuando insertamos al final. Como trabajamos con listas estáticas, no se realiza reubicación ni ampliación de memoria. Si la capacidad máxima se alcanza, se devuelve un error. Los métodos definidos son:

Push: inserta al final de la lista.
Shift: inserta al inicio, desplazando todos los elementos una posición adelante.
After: inserta después de la última aparición de una referencia dada; si no se encuentra, retorna error.
Before: inserta antes de la primera aparición de una referencia dada.

bool static_list_push(StaticList *list, int value) {
	if(static_list_is_full(*list)) {
		return false;
	}

	list->array[list->size] = value;
	list->size++;

	return true;
}

bool static_list_shift(StaticList *list, int value) {
	if(static_list_is_full(*list)) {
		return false;
	}

	for(int i = list->size; i >= 0; i--) {
		list->array[i + 1] = list->array[i];
	}

	list->array[0] = value;
	list->size++;

	return true;
}

bool static_list_insert_after(StaticList *list, int value, int reference) {
	if(static_list_is_full(*list)) {
		return false;
	}

	int index = static_list_get_last_index(*list, reference);
	if(index == -1) {
		return false;
	}

	for(int i = index + 2; i < list->size; i++) {
		list->array[i] = list->array[i - 1];
	}
	list->array[index + 1] = value;
	list->size++;

	return true;
}

bool static_list_insert_before(StaticList *list, int value, int reference) {
	if(static_list_is_full(*list)) {
		return false;
	}

	int index = static_list_get_first_index(*list, reference);
	if(index == -1) {
		return false;
	}

	for(int i = list->size; i > index; i--) {
		list->array[i] = list->array[i - 1];
	}
	list->array[ index > 0 ? index : 0 ] = value;
	list->size++;

	return true;
}

Eliminación.

Las operaciones de eliminación siguen una lógica simétrica a la de inserción. Existen versiones equivalentes para eliminar al inicio, al final o en relación con un valor de referencia. Estos son:

Pop: elimina el último elemento.
Unshift: elimina el primer elemento, desplazando los demás una posición atrás.
Remove Last: elimina la última aparición de un valor específico.
Remove First: elimina la primera aparición de un valor específico.
Remove All: elimina todas las apariciones de un valor y devuelve cuántas se eliminaron.

int static_list_pull(StaticList *list) {
	if(static_list_is_void(*list)) {
		return ERROR_VALUE;
	}

	list->size--;
	int value = list->array[list->size];

	return value;
}

int static_list_unshift(StaticList *list) {
	if(static_list_is_void(*list)) {
		return ERROR_VALUE;
	}

	int value = list->array[0];
	--list->size;
	for(int i = 0; i < list->size; i++) {
		list->array[i] = list->array[i + 1];
	}
	list->array[list->size] = 0;

	return value;
}

int static_list_remove_first(StaticList *list, int value) {
	if(static_list_is_void(*list)) {
		return ERROR_VALUE;
	}

	int index = static_list_get_first_index(*list, value);
	if(index == -1) {
		return ERROR_VALUE;
	}

	int result = list->array[index];
	list->size--;
	for(int i = index; i < list->size; i++) {
		list->array[i] = list->array[i + 1];
	}
	list->array[list->size] = 0;

	return result;
}

int static_list_remove_last(StaticList *list, int value) {
	if(static_list_is_void(*list)) {
		return ERROR_VALUE;
	}

	int index = static_list_get_last_index(*list, value);
	if(index == -1) {
		return ERROR_VALUE;
	}

	int result = list->array[index];
	list->size--;
	for(int i = index; i < list->size; i++) {
		list->array[i] = list->array[i + 1];
	}
	list->array[list->size] = 0;

	return result;
}

int static_list_remove_all(StaticList *list, int value) {
	if(static_list_is_void(*list)) {
		return ERROR_VALUE;
	}

	int count = 0;
	while(static_list_remove_first(list, value) != ERROR_VALUE) {
		count++;
	}
	return count;
}

Eficiencia.

Al estar basadas en arreglos, estas listas heredan su rendimiento característico. Las consultas simples como el acceso por índice son muy rápidas, mientras que las operaciones que implican mover datos (como inserciones o eliminaciones) tienen un costo mayor. Aun así, este enfoque ofrece una solución clara, predecible y fácil de implementar para manejar conjuntos de datos de tamaño fijo.

Tabla 2: Eficiencia de las consultas a una lista estática (desordenada).
Tipo de consulta	Eficiencia temporal	Razón
Inserción	O(n)	Debe desplazar los datos restantes del arreglo, en el mejor de los casos ninguno, en el peor n-1.
Búsqueda	O(n)	En el peor de los casos debe recorrer todo el arreglo para encontrar la coincidencia.
Eliminación	O(n)	Debe extraer el dato y mover a los huecos el resto de datos, en el mejor solo desplaza el índice, en el peor n-1.
Consulta	O(1)	Está indexado, así que es muy rápido acceder a un dato concreto.

Conclusiones.

Las listas estáticas son una excelente introducción a las estructuras de datos lineales. Ofrecen una implementación controlada y eficiente, especialmente útil cuando se conoce de antemano la cantidad máxima de elementos que se desea manejar. A través de los métodos auxiliares, de inserción y eliminación, hemos logrado simular comportamientos más dinámicos con estructuras fijas, reforzando conceptos clave como la manipulación por índice, el desplazamiento de datos y la validación de estados límite. Aunque presentan limitaciones en términos de flexibilidad, su claridad las convierte en una herramienta ideal para aprender principios fundamentales de la programación estructurada y del manejo de memoria.

Vídeo 1: Implementación de listas estáticas desordenadas.