Ir al contenido principal

Listas Dinámicas

Muestra de una lista dinámica con elementos numéricos
Las listas dinámicas son un tipo de estructuras que están formadas por nodos que contienen los elementos de la lista, usando referencias o punteros para accederlos, los nodos se unen en una secuencia, conforme se vaya agregando más nodos, este se acomoda de una forma secuencial. Las listas de un solo enlace se pueden implementar de dos formas distintas, que son: la pila (LIFO Last In First Out, que traducido al español sería: Último En Entrar Primero En Salir) y la otra forma es: cola (FIFO First In First Out, que traducido al español sería: Primero En Entrar Primero En Salir ). Estas son las formas más usuales de implementar las listas enlazadas.

Ahora bien, se sabe que las listas dinámicas son las que se pueden acceder mediante punteros, pero, ¿ Qué da a entender, que es mejor que los arreglos? Pues bien, lo vamos a aclarar con una breve descripción que detalla las ventajas y desventajas de este tipo de dato, comparándolo con los arreglos (array). Una de las principales desventajas de las listas enlazadas, es que perdemos la capacidad de acceder a cualquier elemento usando "get(i)" o "set(i,x)" en tiempo constante, por lo cual en una lista dinámica tenemos que recorrer la lista un elemento a la vez hasta llegar al enésimo elemento. La principal ventaja de las listas enlazadas es que son dinámicas, que su tamaño no es constante y que se pueden meter tantos elementos(nodos) a la lista. A comparación con los arreglos, que su tamaño es constante o fijo y que por lo tanto en los arreglos hay que establecerle el tamaño de memoria.
Los recorridos de una lista enlazada consiste en visitar cada uno de los nodos que conforman la lista. La visita puede implicar una operación simple, por ejemplo, imprimir la información del nodo, o una compleja, dependiendo del problema que se intente resolver.
Las listas enlazadas simples también se caracteriza por poder resolver problemas matemáticos,como lo son, los polinomios.

Para darle un manejo mejor a las listas enlazadas, hay que prestar mucha atención al problema que se plantea, ya que si por ejemplo: se requiere que se resuelva un ejercicio con matriz. Para poder resolver este problema basta con definir el tamaño de la matriz en un arreglo, que a comparación de las listas, se tendría que hacer un proceso más tedioso que fácilmente se puede hacer en un arreglo. Por lo tanto, las listas dinámicas son una herramienta indispensable en la programación, pero dandole un adecuado uso. Además de que las listas dinámicas son el impulso del entendimiento para ver temas más difíciles, como lo son los grafos y los árboles.

Fuentes:
Estructuras de datos 3ra edicion Osvaldo Cairo y Silvia Guarda
http://cslibrary.stanford.edu/103/LinkedListBasics.pdf

Comentarios

Publicar un comentario

Entradas populares de este blog

Árbol Binario

Representación gráfica de un árbol binario  Un árbol binario es un árbol nulo o un árbol cuyos nodos tienen a lo sumo dos hijos. Los hijos de un árbol binario se pueden denotar como hijo izquierdo e hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado a un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsquedas, los montículos binarios y Codificación de Huffman. Un árbol binario es un árbol en el que ningún nodo puede tener cero, uno o dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho. Existen tipos de árboles binarios que suelen usarse para fines específicos, como: Árbol binario de búsqueda y Árbol de Fibonnacci. Complejidad: árboles completos Deduciremos, de manera indu...
Publicar un comentario
Leer más

Abstracción de datos

¿Qué entendemos por abstracción? Pues bien, básicamente es un medio fundamental usado por el ser humano para enfrentarse a la complejidad del mundo. Consiste en básicamente describir o especificar aspectos esenciales e importantes de un fenómeno o entidad, al mismo tiempo que se desechan características irrelevantes según el interés de quien realiza la abstracción, un claro ejemplo sería la imagen que tenemos arriba, en donde se presenta un gato y dos personas con visión diferente con respecto a la mascota, la anciana de la izquierda observa a la criatura de una manera que se le pueda dar amor o cariño, por otra parte, la señora de la derecha, observa al animal de una manera más científica, es decir, se centra más en la cualidades o partes internas del gato. La abstracción de datos en la programación nos ayuda muchas veces a entender los problemas y atacarlos de una manera más sencilla y que la situación que se haya presentado se entienda más fácil, es decir, desechar lo que no oc...
Publicar un comentario
Leer más

Búsquedas en Listas: Búsqueda Secuencial y Binaria

Procedimiento de las búsquedas Con mucha frecuencia los programadores trabajan con grandes cantidades de datos almacenados en arrays y registros, y por ello será necesario determinar si un array contiene un valor que coincida con un cierto valor clave. El proceso de encontrar un elemento específico de un array se denomina "búsqueda". En esta sección se examinarán dos técnicas de búsquedas: búsqueda lineal o secuencial, la técnica más sencilla, y búsqueda binaria o dicotómica, la técnica más eficiente. Búsqueda Secuencial La búsqueda secuencial busca un elemento de una lista utilizando un valor destino llamado clave. En una búsqueda secuencial (a veces búsqueda lineal), los elementos de una lista o vector se exploran (se examinan) en secuencia, uno después de otro, La búsqueda secuencial es necesaria, por ejemplo, si se desea encontrar la persona cuyo número de teléfono es 958-220000 en un directorio o listado telefónico de su ciudad. Los directorios de teléfono están o...
Publicar un comentario
Leer más