Acces

Unidad 3 |
Listas enlazadas |
|
|
|
VALENCIA BARRANCO SONIA JOCELIN ECHEVERRIA CHAN IVONNE |
08/04/2011 |
|

LISTAS ENLAZADAS SIMPLES

En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.
Una estructura dedatos define la organización e interrelación de éstos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son:
•Alta, adicionar un nuevo valor a la estructura.
•Baja, borrar un valor de la estructura.
•Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binario (siempre y cuando los datosestén ordenados).
Otras operaciones que se pueden realizar son:
•Ordenamiento, de los elementos pertenecientes a la estructura.
•Apareo, dadas dos estructuras originar una nueva ordenada y que contenga las apareadas.
Cada estructura ofrece ventajas y desventajas en relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datosapropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.

LISTAS (informática)
En Ciencias de la Computación, una 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 datosarbitrarios y una o dos referencias (punteros) al nodo anterior y/o posterior.

El principal beneficio de las listas enlazadas respecto a los array 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 datoauto-referenciado porque contienen un puntero o link 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: Lista Enlazadas Simples, ListasDoblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.
Las listas enlazadas pueden ser implementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene 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 referenciaspara crear listas enlazadas.

ALGORITMO
Un algoritmo común de las listas de enlace simple es la inserción de nodos. Este algoritmo está implicado de alguna forma porque tiene mucho que ver con cuatro casos: cuando el nodo se debe insertar antes del primer nodo; cuando el nodo se debe insertar después del último nodo; cuando el nodo se debe insertar entre dos nodos; y cuando la lista de enlacesimple no existe. Antes de estudiar cada caso consideremos el siguiente pseudocódigo:
DECLARE CLASS Node
DECLARE STRING name
DECLARE Node next
END DECLARE

DECLARE Node top = NULL
Este pseudocódigo declara una clase auto-referenciada llamada Node con un campo no de enlace llamado name y uncampo de enlace llamado next. También declara una variable de referencia top (del tipo Node) que contiene una referencia al primer Node de una lista de enlace simple. Como la lista todavía no existe, el valor inicial de top es NULL. Cada uno de los siguientes cuatro casos asume las declaraciones de Node y top:

LISTAS ENLAZADAS DOBLES
Recorrido
Definición:
Recorrido simplemente despliega los...