Listas y grafos

3. Lista

1 4.1 Introdución

[pic]
Una lista enlazada o encadenada es una colección de elementos ó nodos, en donde cada uno contiene datos y un enlace o liga.
Un nodo es una secuencia decaracteres en memoria dividida en campos (de cualquier tipo). Un nodo siempre contiene la dirección de memoria del siguiente nodo de información si este existe.
Un apuntador es la dirección de memoria deun nodo
La figura siguiente muestra la estructura de un nodo:
[pic]
El campo liga, que es de tipo puntero, es el que se usa para establecer la liga con el siguiente nodo de la lista. Si el nodofuera el último, este campo recibe como valor NIL (vacío).
A continuación se muestra el esquema de una lista :
[pic]

2 4.2 Operaciones en Listas Enlazadas

[pic]
Las operaciones que podemosrealizar sobre una lista enlazada son las siguientes:
• Recorrido. Esta operación consiste en visitar cada uno de los nodos que forman la lista . Para recorrer todos los nodos de la lista, se comienzacon el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente.
• Inserción. Esta operaciónconsiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos:
o Insertar un nodo al inicio.
o Insertar un nodo antes o después de cierto nodo.o Insertar un nodo al final.
• Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos:o Eliminar el primer nodo.
o Eliminar el último nodo.
o Eliminar un nodo con cierta información.
o Eliminar el nodo anterior o posterior al nodo cierta con información.• Búsqueda. Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar.

3 4.3 Listas Lineales

[pic]
En esta sección se...