Castro Eduardo TI1

Trabajo individual 1
Alumno:
Eduardo Castro Salazar
Curso:
Programación
Licenciatura:
Ingeniería Industrial
Docente:
Dr. Enoc Gutiérrez Pallares
INTRODUCCIÓN
Existen patrones de organización para las variables de instancia, estos patrones
se denominan Estructuras de Datos y una de las aplicaciones más interesantes y
potentes de la memoria dinámica y los punteros son precisamente estas.
04-Octubre-2020
No existe una estructura de
datos que sirva para todos los
propósitos, por tal motivo es importante conocer las ventajas y desventajas de
cada una de ellas para en un momento dado conocer cuál es la óptima para darle
solución a un determinado problema.
Este documento exploraremos la estructura de lista enlazada es una de
las estructuras de datos fundamentales, y puede ser usada para implementar otras
estructuras de datos. Consiste en una secuencia de nodos, en los que se guardan
campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo
anterior o posterior. El principal beneficio de las listas enlazadas respecto a
los vectores convencionales es que el orden de los elementos enlazados puede
ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo
que el orden de recorrido de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de dato autorreferenciado porque contienen un
puntero o enlace (en inglés link, del mismo significado) a otro dato del mismo tipo.
Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier
punto de la lista en tiempo constante (suponiendo que dicho punto está
previamente identificado o localizado), pero no permiten un acceso aleatorio.
Existen diferentes tipos de listas enlazadas: listas enlazadas simples, listas
doblemente enlazadas, listas enlazadas circulares y listas enlazadas doblemente
circulares.
Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes
tales como Lisp, Scheme y Haskell tienen estructuras de datos ya construidas,
junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos
u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de
referencias para crear listas enlazadas.
Las listas enlazadas son usadas como módulos para otras muchas estructuras de
datos, tales como pilas, colas y sus variaciones.
El campo de datos de un nodo puede ser otra lista enlazada. Mediante este
mecanismo, podemos construir muchas estructuras de datos enlazadas con listas;
esta práctica tiene su origen en el lenguaje de programación Lisp, donde las listas
enlazadas son una estructura de datos primaria (aunque no la única), y ahora es
una característica común en el estilo de programación funcional.
A veces, las listas enlazadas son usadas para implementar vectores asociativos, y
estas en el contexto de las llamadas listas asociativas.
DESARROLLO
CREACIÓN E INICIALIZACIÓN DE LISTAS ENLAZADAS
04-Octubre-2020
Antes de empezar a
manipular una lista enlazada
hay que crear una variable dinámica con estructura de lista. Cada nodo de la lista
contiene como mínimo un campo valor y un campo puntero, por tanto y como ya
se vio previamente, la forma más simple de representarlo es mediante un registro.
En lenguaje algorítmico, podemos crear una lista enlazada de la siguiente manera:
donde cabeza debe ser inicializada a nulo ya que la lista inicialmente está vacía.
RECORRIDO DE UNA LISTA ENLAZADA

Recorrer una lista enlazada consiste en desplazarse desde el primer nodo hasta el
último para manipular su información (presentarla en pantalla, escribirla en un
archivo, aplicarle alguna transformación . . .). La siguiente subrutina se encarga de
recorrer una lista enlazada para presentar sus datos por pantalla:
04-Octubre-2020
donde el puntero cabeza ha sido inicializado previamente, bien con el valor nulo o
con la dirección de un espacio de memoria que contiene datos.
BÚSQUEDA DE UN ELEMENTO EN UNA LISTA ENLAZADA
Para buscar un elemento en una lista enlazada hay que recorrerla hasta el final o
hasta que el elemento buscado se encuentre. Una subrutina que realiza la
búsqueda de un DNI en la lista enlazada del apartado anterior viene a
continuación:
04-Octubre-2020
Figura: Inserción en una lista enlazada. a) Por el frente. b) Por la cola
INSERCIÓN DE UN ELEMENTO EN UNA LISTA ENLAZADA
Para insertar en una lista enlazada hay distintas formas de hacerlo: inserción por
delante (por el frente), inserción por el medio e inserción por detrás (por la cola).
En la figura 2.7 vemos la inserción por el frente y por la cola. A continuación
mostraremos las subrutinas que realizan las inserciones en esas posiciones,
considerándose en cualquiera de los dos casos que hay espacio suficiente en el
almacenamiento dinámico
04-Octubre-2020
04-Octubre-2020
ELIMINACION DE UN
ELEMENTO DE UNA LISTA ENLAZADA
Al borrar un elemento de una lista enlazada hay que enlazar correctamente el
puntero del sucesor para no perder la información en el resto de la lista. En la
figura presentamos el caso en el que al borrar un nodo concreto, la lista queda
dividida en dos porciones inconexas. A continuación mostramos una subrutina que
borra un nodo de la lista del apartado anterior.
Figura Eliminación de un nodo en una lista enlazada
04-Octubre-2020
Dada una lista enlazada (de tipo ptrl), cuyo campo de información contiene el
nombre, apellidos (cadenas de caracteres de tamaño 15) y DNI (entero) de una
persona, ordenada de menor a mayor por el subcampo apellidos se pide:
a) Realizar una subrutina que dado un nombre, apellidos y DNI, inserte
ordenadamente un nuevo nodo.
b) Realizar una subrutina que, dado un nombre, apellidos y DNI, borre de la lista el
nodo que lo contenga si éste existe.
04-Octubre-2020
CONCLUSIÓN
Cada estructura de datos ofrece ventajas y desventajas en relación con su
simplicidad y eficiencia para la realización de cada operación. Se requiere revisar
detenidamente información para ser capaz de establecer estructuras de datos
lógicas que permitan hacer un uso más eficiente del espacio ocupado en la
memoria de la computadora, de minimizar los tiempos de acceso, así como de
lograr formas más efectivas de inserción y eliminación de los datos en estructuras
04-Octubre-2020
de almacenamiento, para
lograr una solución óptima.
Las ventajas de una lista enlazada de
 Una lista enlazada es un TDA dinámico, su tamaño puede cambiar durante

la ejecución del programa y los elementos se pueden insertar
indefinidamente.
 No es preciso conocer la cantidad de elementos en tiempo de compilación.
 Ni las inserciones ni las eliminaciones implican realizar corrimientos de los
elementos de la lista. Al insertar un elemento en la lista, la operación tiene
un tiempo constante independientemente de la posición en la que se
inserte, solo se debe crear el nodo y modificar los enlaces.
Y las desventajas son que no permite el acceso directo a un elemento arbitrario
de la lista. Para acceder al i-ésimo elemento, se debe recorrer la lista,
comenzando por el primer nodo, hasta llegar al elemento deseado, es decir,
permiten solamente un acceso secuencial a los elementos.
Podemos concluir que son usadas más eficientemente para recorrer esta serie de
datos.
Como muchas opciones en programación y desarrollo, no existe un único método
correcto para resolver un problema. Una estructura de lista enlazada puede
trabajar bien en un caso, pero causar problemas en otros. En general, teniendo
una colección dinámica donde los elementos están siendo añadidos y eliminados
frecuentemente e importa la localización de los nuevos elementos introducidos se
incrementa el beneficio de las listas enlazadas.
04-Octubre-2020
BIBLIOGRAFÍA
 JUAN FCO. PÉREZ CASTELLANO, Teoría de grafos aplicada,

Departamento de Electrónica y Telecomunicación. Escuela Técnica
Superior de Ingenieros de Telecomunicación. ULPGC, 1995.
 SEYMOUR LIPSHUTZ, Estructura de datos, McGraw Hill, 1987
 Apuntes de Informática. Escuela Universitaria de Informática.
ULPGC. 1987
 Antonakos, James L. and Mansfield, Kenneth C., Jr. Practical Data
Structures Using C/C++ (1999). Prentice-Hall. ISBN 0-13-280843-9,
 HEILMAN, G. L. Estructuras de datos, algoritmos y programación
orientada a objetos. La Habana : Félix Varela, 2003.
 PROGRAMACIÓN, D. D. T. D. P2. Conferencia #1. Estructuras de
Datos Lineales. Los Tipos de Datos Abstractos. El TDA Lista. 2006-
2007.
 P2. CONFERENCIA #2. Estructuras de Datos Lineales.
Implementación del TDA Lista utilizando listas enlazadas. .
Departamento de Técnicas de Programación ed. curso: 2006-2007.
 HEILMAN, G. L. Estructuras de datos, algoritmos y programación
orientada a objetos. La Habana : Félix Varela, 2003.
 GREGORY, H. Estructuras de datos, algoritmos y programación
orientada a objetos. La Habana: Félix Varela, 2003.
04-Octubre-2020

Castro Eduardo TI1

Cargado por

Copyright:

Formatos disponibles

Castro Eduardo TI1

Cargado por

Información del documento

Descripción original:

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Castro Eduardo TI1

Cargado por

Copyright:

Formatos disponibles

Trabajo individual 1

RECORRIDO DE UNA LISTA ENLAZADA

Figura Eliminación de un nodo en una lista enlazada

Las ventajas de una lista enlazada de

 Una lista enlazada es un TDA dinámico, su tamaño puede cambiar durante

 JUAN FCO. PÉREZ CASTELLANO, Teoría de grafos aplicada,

También podría gustarte