Estructura

Estructura de Datos y Algoritmos Tema­I­Introducción y conceptos fundamentales

1.2.4 Listas enlazadas
Las listas enlazadas son tipos de datos dinámicos que se construyen con nodos. Un nodo es un registro con  al   menos,   dos   campos,   uno   de   ellos   contiene   las   componentes   y   se   le   denomina  data  (estructura   de registro), el otro es un valor que señala al siguiente nodo y se le denomina enlace (next). Como definición más formal se tiene que: El TDA lista enlazada es una colección de nodos ordenada según  su posición, tal que cada uno de ellos es accedido a través del campo enlace del nodo anterior. Las   listas   enlazadas   se   implementan   aprovechando   todas   las   ventajas   de   la   asignación   dinámica   de memoria. Ésta es la forma habitual y más eficaz de realizar su implementación. Sin embargo, ésta no  es la única implementación posible. También pueden ser implementadas estáticamente definiendo el tipo  arreglo como nodos y utilizar los índices en el campo enlace para determinar el siguiente nodo. Aunque pueda parecer más eficiente implementar una lista enlazada mediante arreglos, realmente no lo es. En el caso de un arreglo, siempre se deberá mantener una lista paralela de nodos vacíos de manera que  cuando se necesite alojar un nuevo nodo, se tome de esta última lista un nodo disponible y cuando se  quiera liberar un nodo habrá de ser devuelto a la lista. Es importante observar la distinción existente entre un tipo de datos abstracto y su implementación. Ambos  conceptos   pueden   ser   considerados   de   forma   estática   o   dinámica.  Una   variable   de   tipo   array   es   una  estructura   típicamente   estática,   pero   puede   ser   almacenada   en   memoria   de   forma   estática   o   dinámica  (mediante punteros). Lo mismo sucede con los conceptos pila  o lista, que por naturaleza son estructuras  puramente dinámicas pero que pueden implementarse con asignación de memoria estática (dentro de un  array).Una definición de un tipo nodo puede ser la siguiente: TYPE  Ptr_nodo = POINTER RO Nodo;       Nodo = RECORD                 datos: Tipo_datos                 enlace: Ptr_nodo;              END Para acceder a los elementos de una lista se necesita un primer elemento o puntero externo. Este puntero  apuntará al primer elemento de la lista. Para ello será necesario declarar una variable a tal fin: VAR lista: Ptr_nodo;

Acciones a realizar en una lista enlazada:
Inserción por la cabeza 1. Crear un nuevo nodo. 2. Almacenar el dato en el campo correspondiente (datos). 3. Como va a ser el primer nodo, su enlace deberá apuntar al que hasta ahora era el primer nodo  (apuntado por el enlace externo). 4. El elnace externo deberá apuntar al nuevo nodo (que ahora es el primero).

Enric Rubio Rodríguez(2008) erubio1@gmail.com

http://www.erubio.es Página: 1

Estructura de Datos y Algoritmos Tema­I­Introducción y conceptos fundamentales
Inserción por el final Para insertar por el final, se debe llegar hasta el último nodo de la lista. Para ello, y partiendo del enlace  externo, se saltará de nodo a nodo (a través del campo enlace), hasta alcanzar un nodo cuyo enlace sea nulo (NIL). En ese momento, el campo enlace se cambiará por el enlace hacia el nuevo nodo (recordar que  al crear un nuevo nodo, por defecto, su enlace debe estar siempre a NIL). Suprimir por la cabeza 1. Almacenar la dirección del primer elemento apuntado por el enlace externo en una variable puntero  temporal. 2. Se asigna al enlace externo el elemento que figura en el enlace del primer elemento. 3.Se elimina el nodo apuntado por el puntero auxiliar. Suprimir por el final En este caso se procederá del mismo modo que en la inserción por el final pero con una variable puntero  auxiliar se irá guardando la dirección del nodo anterior. Al alcanzar el nodo con enlace=NIL, se borrará y al  nodo anterior apuntado por el puntero auxiliar, se modificará su enlace a NIL....