estructura de datos dinamicas listas

Estructura de datos dinamicas listas
¿Qué es una lista?
– Es una colección de elementos del mismo tipo llamados
nodos, organizados arbitrariamente con un orden ya
definido y con la capacidad de inserción y eliminación de
sus elementos.
– Para cada elemento hay un predecesor y un sucesor. El
precedesor del primer elemento y el sucesor del último es el
elemento vacío.
• Característicasde las listas
– Las listas se caracterizan por:
• La forma en que se encadenan los elementos (esto es, la
forma en que se identifican el predecesor y sucesor de un
elemento). Para ello se suelen utilizar los punteros.
• Cómo y dónde se pueden insertar y eliminar sus elementos.
• El número de predecesores y sucesores de cada elemento.
Definición de lista:  una lista enlazada es una delas 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 serdiferente 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 lalista 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 talescomo 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 referencias para crear listas enlazadas.
Listas: Colección de elementos del mismo tipo, organizados
arbitrariamente con un orden ya definido y con la capacidad de
inserción yeliminación de sus elementos.
– Pila: Lista en la cual la inserción y eliminación de elementos se realizan
únicamente al final de la lista
– Cola:Lista en la cual la inserción de un elemento se hace por un
extremo mientras que la eliminación se realiza por el otro extremo.

Definición de un nodo:
type
ptrnodo=^tiponodo;
tiponodo= record
datos:tipo_datos;
siguiente:ptrnodo;
end;
•Declaración de la cabecera de una lista:
var
cabecera_lista:ptrnodo;
• Inicialización de la cabecera de una lista:
cabecera_lista:=nil;
datos ...
LISTA
CABECERA
NODOSFacultad de Matemáticas. Informática I
PUNTEROS Y ESTRUCTURAS DINÁMICAS DE DATOS
Fernando Pérez Nava
Listas:Operaciones Básicas (2)
• Inserción de un nodo en la cabecera de una lista (en
su principio)
var
p:ptrnodo;clista:ptrnodo;
begin
...
new(p);
p^.datos:=datos;
p^.siguiente:=clista;
clista:=p;
...
??? ???
p
datos ???
p
datos
p
...
clista
datos
clista
x
x
xFacultad de Matemáticas. Informática I
PUNTEROS Y ESTRUCTURAS DINÁMICAS DE DATOS
Fernando Pérez Nava
datos datos
datos
datos
datos
datos
Listas:Operaciones Básicas (3)
• Procesamiento de los datos
de una lista
varp:ptrnodo;clista:ptrnodo;
...
p:=clista
while pnil do
begin
procesa(p^datos);
p:=p^siguiente;
end
...
... datos
...
p
datos ...
p
...
• Inserción en un lugar arbitrario
var
p,nuevo,clista:ptrnodo;
...
new(nuevo);
nuevo^.datos:=datos;
nuevo^.siguiente:=p^.siguiente;
p^.siguiente:=nuevo;
...
... datos ...
p
... datos ...
datos
... ...
datos
p
p
nuevo
nuevoFacultad de...