Resumen
El presente proyecto académico, muestras mediante una página web, algunos ejemplos de funciones relacionadas con las listas simplemente enlazadas. Además que mostramos un poco de conceptos básicos relacionados también con las listas simplemente enlazadas y videos, que nos ayudan como una herramienta visual extra para comprender mejor la funcionalidad y uso de las listas simplemente enlazadas.
PALABRAS CLAVE: Funciones, Listas, Nodos, Página Web.
Introducción
El presente proyecto académico está dirigido a estudiar y comprender la forma en cómo se trabaja con nodos en listas simplemente enlazadas. Para lo cual se diseño y empleo una página web en donde se explican algunos ejemplos de listas simplemente enlazadas
OBJETIVO
Estudiar y comprender las listas simplemente enlazadas y su uso para poder tener mayores facilidades a la hora de resolver ciertos algoritmos que requieren de estas estructuras.
Marco teórico
3.1 Listas Simplemente Enlazadas
Las listas simplemente enlazadas son estructuras de datos semejantes a las estructuras array salvo que el acceso a un elemento no se hace mediante un índice, sino mediante un puntero.
La asignación de memoria se la realiza durante la ejecución.
En una lista simplemente enlazada, los elementos no son contiguos en lo que concierne al enlazado.
Figura 1. En esta figura se muestra un ejemple sencillo y directo de la estructura de una lista simplemente enlazada.
A diferencia de las estructuras array, en la que los elementos están contiguos en la memoria, en una lista simplemente enlazada los elementos están dispersos. Es decir, que cada elemento se almacena en un lugar de memoria que le asigna el ordenador de forma aleatoria. Esta asignación como ya se mencionó, se la realiza durante la ejecución. Cada dirección de memoria designada a una lista, estará ocupada por nodos.
3.2 Nodos
Una lista se compone de nodos, que son estructuras de datos que nos permiten registrar datos de interés. Para que estos nodos se conviertan en una lista, debe existir un enlace entre ellos, que en términos más propios se los conoce como apuntadores o punteros. Los punteros o apuntadores, son la parte de los nodos que nos permiten recorrer la lista y acceder también a las direcciones de memoria donde se almacenan los elementos de la lista. Como se muestra en la Figura 1, La lista tiene un inicio y tiene un fin. El inicio se lo conoce como cabecera, mientras que el final de lista se lo conoce como cola. Para poder darle fin a la lista, lo único que se hace es que el último apuntador o último enlace apunte a NULL, es decir, que apunte a nada.Para acceder a un elemento de la lista simplemente enlazada, esta debe ser recorrida comenzando por el inicio (o cabecera como se mencionó); el puntero siguiente o el enlace, permite recorrer o desplazarnos hacia el próximo elemento, hasta llegar al final.
En el caso de las listas simplemente enlazadas, el desplazamiento se hace en una sola dirección, es decir, que el apuntador o enlace de un nodo apunta solo al nodo inmediato siguiente, desde el primer nodo (cabecera), hasta el último nodo (cola).
Si es que se deseara desplazarse tanto hacia adelante, como hacia atrás, en las listas simplemente enlazadas no se puede hacer eso, y tampoco hay métodos o funciones que nos permitan hacer eso. Para conseguirlo, la única alternativa es usar listas doblemente enlazadas.
Figura 2. Un nodo se compone de dos partes, la primera es la parte de Dato, que es donde se registran datos de interés; y la segunda parte que es la Dirección, que es la parte que nos ayuda a crear enlaces entre nodos y así generar listas.
A consecuencia de las listas simplemente enlazadas, doblemente enlazadas, etc., se pueden generar varias otras estructuras un poco más complejas, pero igual de importantes y fáciles de implementar y estudiar, como ser: árboles y grafos.
3.3 Árboles
Los Árboles son estructuras de datos de memoria dinámica de una cantidad finita de elementos que consta de un "Nodo Raíz", del cual van saliendo ramificaciones a manera de un árbol.
En otras palabras, un árbol se define como una colección de nodos organizados en forma recursiva. Cuando hay 0 nodos se dice que el árbol está vacío, en caso contrario el árbol consiste en un nodo denominado raíz, el cual tiene 0 o más referencias a otros árboles, conocidos como sub-árboles. Las raíces de los sub-árboles se denominan hijos de la raíz, y consecuentemente la raíz se denomina padre de las raíces de sus sub-árboles.
Los nodos que no poseen hijos se denominan hojas. Dos nodos que tienen el padre en común se denominan hermanos.
Los árboles poseen dos características principales:
Grado.- El grado hace referencia a el número total de nodos hijos.
Altura.- La altura hacer referencia al total de filas de nodos u hojas existentes en el árbol.
Figura 3. En esta figura vemos un ejemplo de árbol. En él, la raíz es "page" del cual nacen dos hijos, y de estos también van saliendo más hijos, dando a la gráfica una semejanza con un árbol.
3.4 Grafos
Un grafo, en el ámbito de las ciencias de la computación, es una estructura de datos que consiste en un conjunto de nodos (también llamados vértices) y un conjunto de arcos (aristas) que establecen relaciones entre los nodos. El concepto de grafo desciende directamente del concepto matemático de grafo.
Informalmente se define como:
G = (V, E) (1)
Siendo los elementos de V los vértices, y los elementos de E, las aristas (edges en inglés). Formalmente, un grafo, G, se define como un par ordenado, G = (V, E), donde V es un conjunto finito y E es un conjunto que consta de dos elementos de V.
Los grafos se pueden clasificar en dos grupos:
Dirigidos.- En un grafo dirigido cada arco está representado por un par ordenado de vértices, de forma que representan dos arcos diferentes.
No Dirigidos.- En un grafo no dirigido, el par de vértices que representa un arco no está ordenado.
Figura 4. Un grafo tiene un esquema parecido a un árbol, la diferencia es que un árbol tiene un esquema jerárquico y ordenado en una sola dirección, mientras que un grafo no necesariamente presenta este esquema.
3.5 Funciones
En listas simplemente enlazadas, existen algunas funciones principales o elementales:
Agregar.- Una de las característica de las listas simplemente enlazadas, y de cualquier otro tipo de estructura similar, es que es dinámico, es por eso que una lista no es fija, más al contrario, podemos agregarle nodos al principio, al final, o en cualquier posición de la lista.
Eliminar.- Así como podemos ir agregando nuevos nodos a nuestra lista, también podemos eliminar nodos de la misma; una de las razones principales, para liberar espacio en memoria ya que es posible el ya no estar utilizando ese nodo.
Buscar.- Podemos obtener, mediante algoritmos de búsqueda, los datos o direcciones de uno o varios nodos de la lista.
Marco práctico
Para comprender mejor las listas simplemente enlazadas y sus respectivas operaciones, lo que se hizo fue desarrollar una página web, en la que se encuentran, además de un poco de teoría básica y rápida, las distintas funciones de las operaciones con listas simplemente enlazadas y videos a manera de ayuda visual.
Menú Principal.- En el menú principal, nos encontramos con 4 opciones principales: Concepto, Funciones y Extras. Cada una de ellas contiene un contenido específico sobre el tema de listas simplemente enlazadas, las cuales veremos una por una.
Figura 5. Estas 3 opciones nos permitirán navegar a través de la página web.
Concepto.- La primera opción es Concepto, en esta opción encontraremos justamente conceptos básicos que se deben tomar en cuenta antes de comenzar a trabajar o estudiar las listas simplemente enlazadas.
Figura 6,7,8. En la opción de Concepto, se muestran algunos conceptos básicos relacionados con listas.
Extras.- En esta opción, se encuentran links de videos, y del informe del proyecto académico que también hacen una explicación breve sobre las listas simplemente enlazadas y un pequeño resumen acerca de la página web.
Para acceder, lo único que se debe hacer es dar un click sobre el logo, el cual nos enviará a la respectiva página donde se encuentra alojado tanto el informe como los videos.
Solo está disponible un link de informe, ya que solo hay uno; pero existen dos links para video, ya que hay un video hecho por ambos autores de esta página
Figura 9. Estos son los links que permiten acceder a los videos e informe sobre esta página web.
Funciones.- A pesar del contenido interesante y relevante de las otras opciones, esta es la principal, ya que es aquí donde se muestran algunos ejemplos de funciones para trabajar sobre listas simplemente enlazadas.
Al entrar en esta opción, en un extremo de la pantalla, se tiene a disposición una pequeña lista de ejemplos de funciones de listas simplemente enlazadas. Para ver una de estas funciones, solo se hace un click sobre alguna de ellas.
Figura 10. En la parte izquierda de la pantalla, se encuentra una lista con ejemplos de funciones para listas simplemente enlazadas.
Se muestra por pantalla una pequeña explicación de la función, así como también una ayuda visual a su lado, que explica paso a paso el código fuente de la función (escrito en Java).
Figura 11. La ayuda visual, es una imagen animada (imagen flash), para mejor comprensión de la función.
Las funciones enlistadas en la página web, son solo algunos ejemplos básicos de cómo trabajar con listas simplemente enlazadas. Sin embargo, la implementación de funciones más complejas no es de mayor dificultad, dado que se basan en estas funciones básicas.
Conclusiones
De acuerdo a la forma de trabajo, y lo visto en este documento académico, podemos concluir que:
Las listas simplemente enlazadas, son posiblemente las estructuras de datos más fáciles, rápidas y sencillas de estudiar, aprender y entender.
La resolución de una función relacionada con listas simplemente enlazadas, es fácil y rápida, en especial porque no se requieren demasiadas líneas de código, por ende la solución es inmediata.
La implementación de una aplicación basada en listas simplemente enlazadas, también supone un fácil desarrollo, es especial si se trabaja con lenguajes de programación como Java, dada las facilidades que brinda al momento de trabajar con este tipo de estructuras, un ejemplo es la facilidad, eficacia y rapidez para eliminar un nodo de la lista, ya que con otras herramientas, lo más probable sea tener que soltar el enlace nodo por nodo, mientras que en Java, solo soltamos el enlace del nodo que queremos eliminar.
Las listas simplemente enlazadas, así como también otro tipo de estructuras similares, son útiles a la hora de trabajar problemas como PILAS y COLAS, ya que se maneja la misma lógica de agregar, borrar o buscar elementos. Algunos ejemplos pueden ser la fila para el cine o un banco, en donde tal vez se necesite de estas tres funciones principales de listas simplemente enlazadas, para registrar quien es el primero de la lista, el último, el tiempo que lleva en espera, etc.
A pesar, de que podríamos trabajar con árboles y/o grafos, cuando se trata de listas simplemente enlazadas, lo más probable es que tanto nuestro árbol, como nuestro grafo, adquieran una característica lineal.
Recomendaciones
En función a la forma de trabajo y las conclusiones generadas para este proyecto académico, se recomienda lo siguiente:
A pesar de ser fáciles y rápidas de aprender y entender, sería mucho más factible que para hacer dicho trabajo, exista un apoyo en la parte gráfica; de esta manera, se recomienda usar estas ayudas gráficas que presenta la página (en la opción de funciones), para que personas que adquieran este conocimiento por primera vez, tengan a la mano una herramienta útil para comprender mejor.
Además, se recomienda usar estas ayudas gráficas, para que otros puedan también desarrollar ayudas iguales o mejores en el futuro.
Se recomienda tratar de que las líneas de código para cada función sean mínimas, ya que si se quisiera implementar una aplicación con una cantidad significativa de funciones para listas simples, el código en general sería complejo y robusto.
Como ya se explico en el anterior subtítulo, se recomienda emplear el lenguaje Java, dada las facilidades que presenta a la hora de trabajar con listas simplemente enlazadas o estructuras de datos similares.
También se recomienda, verificar y reutilizar estos ejemplos en otras estructuras como listas circulares, listas doblemente enlazadas, etc., ya que la resolución para problemas en estas estructuras de datos, son similares (por no decir las mismas) a las que se aplican para listas simplemente enlazadas.
Por último, hay que tomar en cuenta que, si bien las listas simplemente enlazadas nos dan la posibilidad de registrar gran cantidad de datos de forma dinámica, hay que tener cuidado de no perder los enlaces de esta lista, ya que si por error eliminamos un nodo que no deberíamos haber eliminado, no lo podremos recuperar; peor aún si es la cabecera (principio) la que se pierde, porque se perdería la lista entera.
Referencias
[1] http://casicodigo.blogspot.com, "Representación De Un Grafo En Forma Enlazada", 2012.
[2] http://users.dcc.uchile.cl, "Estructuras De Datos Básicas".
[3] http://tutorialms-dos.bligoo.com, "Listas Enlazadas Simples, Circulares… Y Árboles Binarios", 2002.
[4] http://es.kioskea.net, "La Listas Simplemente Enlazada", 2007.
[5] http://www.calcifer.org, "Estructuras De Datos: Listas Enlazadas, Pilas Y Colas".
[6] http://www.sisman.utm.edu.ec, "Investigación Operativa. Teoría, Ejercicios y Prácticas con ordenador", Rosa Rodríguez Huerta, Antonio Gámez Mellado, Quito, 2002.
[7] http://claudiazmorelo.blogspot.com, "Método De La Esquina Noroeste", Claudia Díaz Morelo, 2012.
[8] http://invdoperaciones.wordpress.com, "Método Esquina Noroeste", 2011.
Autor:
José Antonio Mariaca Valenti
Carlos Andrés Quiroga Alvarado