Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Proyecto Programación: Listas Enlazadas




Enviado por Jose Mariaca



  1. Resumen
  2. Introducción
  3. Marco
    teórico
  4. Marco
    práctico
  5. Conclusiones
  6. Recomendaciones
  7. Referencias

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 son
contiguos en lo que concierne al enlazado. 

Monografias.com

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.

Monografias.com

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.

Monografias.com

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.

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.

Monografias.com

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.

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, Video, Informe. Cada una de ellas
    contiene un contenido específico sobre el tema de
    listas simplemente enlazadas, las cuales veremos una por una.

  • 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.

  • Video.- En esta opción, se encuentran
    links de videos que también hacen una
    explicación breve sobre las listas simplemente
    enlazadas y un pequeño resumen acerca de la
    página web.

  • Informe.- En esta opción se encuentra
    el link de este documento académico.

  • 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.

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).

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

 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Categorias
Newsletter