Informatica

República Bolivariana de Venezuela
Ministerio del Poder Popular para la Educación Superior
Instituto Universitario Politécnico “Santiago Mariño”
Cátedra: Estructura de Datos

LISTAS

Profesor: Rodríguez Aurimar
Alumna: Borges Joselyn C.I 18.529.959

Caracas, Junio de 2011
CONCEPTOS

Una lista es una estructura de datos homogénea y dinámica, que va a estar formada por unasecuencia de elementos, donde cada uno de ellos va seguido de otro o de ninguno.

Una lista es una secuencia de objetos ordenados, en la que se dispone de un iterador especial con el que se puede: insertar o eliminar elementos en cualquier posición, recorrer los elementos de la lista hacia adelante y opcionalmente, hacia atrás, etc.

Una lista es una secuencia de elementos llamadosnodos. Cada nodo esta formado por un campo de datos y 1 o más campos de enlace que apunta(n) al siguiente nodo. Todo nodo tiene un predecesor y antecesor excepto el primero y el último.

CARACTERÍSTICAS

Homogénea: Todos los elementos que forman la lista tienen el mismo tipo base.
Dinámica: Puede crecer o decrecer en tiempo de ejecución según nuestras necesidades.

TIPOSExisten varios criterios para clasificar las listas: según su modo de acceso o según su información de acceso.

Modo De Acceso: Atendiendo a este, se dividen en densas y enlazadas. El modo de acceso es independiente de la implementación realizada.

- Listas densas: Se caracterizan porque los elementos siguen una secuencia física. Sabemos cuales es el siguiente elemento porque paraacceder a él hemos tenido que pasar por todos los anteriores.

- Listas enlazadas. 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 de caracteres en memoria dividida en campos (de cualquier tipo). Un nodo siempre contiene la dirección de memoria del siguiente nodo de información si esteexiste.
Un apuntador es la dirección de memoria de un nodo.
La figura siguiente muestra la estructura de un nodo:

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 nodo fuera el último, este campo recibe como valor NIL (vacío).

A continuación se muestra el esquema de una lista:
NIL

Información deacceso

- Listas ordinales: Los elementos se van colocando en la lista a medida que llegan y se identifican por el orden de llegada. El acceso a un elemento es por su orden o posición relativa dentro de la lista.

- Listas calificadas: Los elementos se clasifican por una clave y pueden estar ordenados o no estarlo. A un elemento se accede por la información contenida en un campo clave.- Pilas: Una pila es una lista de elementos en la que se pueden insertar y eliminar elementos sólo por uno de los extremos. Como consecuencia, los elementos de una pila serán eliminados en orden inverso al que se insertaron. Es decir, el último elemento que se metió a la pila será el primero en salir de ella.
En la vida cotidiana existen muchos ejemplos de pilas, una pila de platosen una alacena, una pila de latas en un supermercado, una pila de papeles sobre un escritorio, etc.
Debido al orden en que se insertan y eliminan los elementos en una pila, también se le conoce como estructura LIFO (Last In, First Out: último en entrar, primero en salir).

Otros Tipos De Listas

- Listas Reorganizables: Son aquellas en las que cada vez que se accede a un elementoéste se coloca al comienzo de la lista. Si el elemento al que se accede no está en la lista entonces se añade al comienzo de la misma.

- Listas Circulares: Estas, tienen la característica de que el último elemento de la misma apunta al primero.
La siguiente figura es una representación gráfica de una lista circular.

- Listas Dobles: Una lista doble, ó doblemente ligada es una...