aquí:
Primero intente con la estructura de datos estática y la estructura de datos dinámica ->
Estructura de datos estática: –
- ¿Qué patrones iterativos y recursivos se pueden expresar como O (1), O (log2n), O (n) u O (n2) en notación O grande?
- ¿Qué es un algoritmo para darme sistemáticamente todas las combinaciones de elementos r de una matriz de elementos K?
- ¿Cuál crees que es el algoritmo de optimización más inteligente?
- ¿Cuáles son todas las áreas donde las estructuras de datos se aplican en escenarios del mundo real?
- ¿Por qué se usa el sistema binario?
Como sugiere la palabra estática, las estructuras de datos estáticos están diseñadas para almacenar un “conjunto de datos” estático. Sin embargo, el “conjunto de datos” estático no significa que no podamos cambiar los valores asignados de los elementos. Es el tamaño de memoria asignado a “datos”, que es estático. De modo que es posible cambiar el contenido de una estructura estática pero sin aumentar el espacio de memoria asignado a ella.
Estructura de datos dinámica: –
Las estructuras de datos dinámicos están diseñadas para facilitar el cambio de estructuras de datos en el tiempo de ejecución. Es posible cambiar los valores asignados de los elementos, como ocurrió con las estructuras estáticas. Además, en las estructuras dinámicas, el tamaño de memoria inicialmente asignado no es un problema. Es posible agregar nuevos elementos, eliminar elementos existentes o realizar cualquier tipo de operación en el conjunto de datos sin tener en cuenta el espacio de memoria asignado inicialmente.
Ahora:
La lista vinculada es una estructura de datos dinámica cuya longitud se puede aumentar o disminuir en tiempo de ejecución.
¿En qué se diferencian las listas vinculadas de las matrices? Considere los siguientes puntos:
- Una matriz es una estructura de datos estática. Esto significa que la longitud de la matriz no se puede modificar en tiempo de ejecución. Mientras, una lista vinculada es una estructura de datos dinámica.
- En una matriz, todos los elementos se mantienen en ubicaciones de memoria consecutivas, mientras que en una lista vinculada los elementos (o nodos) se pueden mantener en cualquier ubicación pero aún conectados entre sí.
¿Cuándo preferir listas enlazadas sobre matrices? Las listas vinculadas se prefieren principalmente cuando no conoce el volumen de datos que se almacenarán. Por ejemplo, en un sistema de gestión de empleados, no se pueden usar matrices ya que son de longitud fija, mientras que se puede unir cualquier número de nuevos empleados. En escenarios como estos, se utilizan listas vinculadas (u otras estructuras de datos dinámicos) ya que su capacidad se puede aumentar (o disminuir) en el tiempo de ejecución (como cuando sea necesario).
¿Cómo se organizan las listas vinculadas en la memoria?
La lista vinculada consiste básicamente en bloques de memoria que se encuentran en ubicaciones de memoria aleatorias. Ahora, uno preguntaría cómo están conectados o cómo se pueden atravesar. Bueno, están conectados a través de punteros. Por lo general, un bloque en una lista vinculada se representa a través de una estructura como esta:
struct test_struct
{
int val;
struct test_struct * next;
};
Como puede ver aquí, esta estructura contiene un valor ‘val’ y un puntero a una estructura del mismo tipo. El valor ‘val’ puede ser cualquier valor (dependiendo de los datos que contenga la lista vinculada) mientras que el puntero ‘siguiente’ contiene la dirección del siguiente bloque de esta lista vinculada. Por lo tanto, el recorrido de la lista vinculada es posible a través de estos ‘próximos’ punteros que contienen la dirección del siguiente nodo. El puntero ‘siguiente’ del último nodo (o para una lista enlazada de un solo nodo) contendría un NULL.
¿Cómo se crea un nodo?
Un nodo se crea asignando memoria a una estructura (como se muestra en el punto anterior) de la siguiente manera:
struct test_struct * ptr = (struct test_struct *) malloc (sizeof (struct test_struct));
Entonces, como podemos ver arriba, el puntero ‘ptr’ ahora contiene la dirección de un nodo recién creado. Si la lista vinculada está vacía y se crea el primer nodo, también se conoce como nodo principal.
Una vez que se crea un nodo, se le puede asignar el valor (que se creó para mantener) y su siguiente puntero se le asigna la dirección del siguiente nodo. Si no existe un nodo siguiente (o si es el último nodo), como ya se explicó, se asigna un NULL. Esto se puede hacer de la siguiente manera:
…
…
ptr-> val = val;
ptr-> siguiente = NULL;
…
…
¿Cómo buscar un nodo en una lista vinculada?
Buscar un nodo significa encontrar el nodo que contiene el valor que se está buscando. De hecho, esta es una tarea muy simple si hablamos de búsqueda lineal (tenga en cuenta que puede haber muchos algoritmos de búsqueda). Uno solo necesita comenzar con el primer nodo y luego comparar el valor que se está buscando con el valor contenido en este nodo. Si el valor no coincide, entonces a través del puntero ‘siguiente’ (que contiene la dirección del siguiente nodo) se accede al siguiente nodo y se realiza la misma comparación de valores allí. La búsqueda continúa hasta que se accede al último nodo o se encuentra un nodo cuyo valor es igual al valor que se está buscando. Un fragmento de código para esto puede verse así:
…
…
…
while (ptr! = NULL)
{
if (ptr-> val == val)
{
encontrado = verdadero;
rotura;
}
más
{
ptr = ptr-> siguiente;
}
}
…
…
…
¿Cómo se elimina un nodo?
Un nodo se elimina al encontrarlo primero en la lista vinculada y luego llamar a free () en el puntero que contiene su dirección. Si el nodo eliminado es cualquier otro que no sea el primero y el último nodo, entonces el puntero ‘siguiente’ del nodo anterior al nodo eliminado debe apuntar a la dirección del nodo que está justo después del nodo eliminado. Es como si una persona se separara de una cadena humana, entonces las dos personas (entre las cuales estaba la persona) necesitan unirse para mantener la cadena.
ref: estructuras de datos estáticos frente a estructuras de datos dinámicas
C Estructura de datos de la lista vinculada explicada con un programa de ejemplo C
