Listas estructura de datos PDF

Preview

Summary

Listas Estructura de Datos...

Description

1. Definición de Listas. Las listas son: ▪ Una colección de 0 o más elementos o Si la lista no tiene elementos, se dice que está vacía o En una lista, todos los elementos son de un mismo tipo ▪ Son estructuras lineales, es decir: o Sus elementos están colocados uno detrás de otro o Cada elemento de una lista se conoce con el nombre de nodo ▪ Son mucho más flexibles que los arreglos. ▪ Permiten trabajo “dinámico” con un grupo de elementos Las listas Simples ▪ Se define como un conjunto de nodos: o Uno detrás de otro. o Del cual siempre se puede conocer al nodo inicial y al final. ▪ De cada nodo de la lista, se conoce: o Un contenido, que es la información que almacena dentro, puede ser de cualquier tipo de dato. o Un sucesor único, Excepto el ultimo nodo de la lista. Las listas Enlazadas Se define por: ▪ El tipo de sus elementos: campo de información (datos) y campo enlace (puntero o apuntador). ▪ Un puntero de cabecera que permite acceder al primer elemento de la lista. ▪ Un medio para detectar el último elemento de la lista: puntero nulo (nil).

Ejemplos Vivimos rodeados de listas: ✓ Lista de compra ✓ Lista de regalos de boda ✓ Lista escolar ✓ Lista de pasajeros de un avión ✓ Lista de Contactos ✓ Entre otros. Siendo el denominador común de todas estas listas el establecer una ordenación entre sus elementos. 2. Características.

▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪ ▪

Son flexibles, pueden crecer y decrecer. Podemos acceder a cualquier posición dentro de la lista. Podemos insertar y borrar elementos de cualquier posición. Pueden ser concatenadas o divididas (sublistas). Una lista se suele representar como una sucesión de elementos separados por comas: a1; a2; :::; an : n >= 0. Matemáticamente una lista es una secuencia de cero o más elementos. Si tiene 0 elementos se llama lista vacía. Son una sucesión de nodos en la que a partir de un nodo se puede acceder al que ocupa la siguiente posición en la lista. Forman una sucesión de nodos encadenados a través de punteros.

3. Importancia. Las listas son estructuras de datos muy útiles para los casos en los que se quiere almacenar información de la que no se conoce su tamaño con antelación. También son valiosas para las situaciones en las que el volumen de datos se puede incrementar o decrementar dinámicamente durante la ejecución del programa. Cuando se aplican restricciones de acceso a las listas, se tienen a las pilas y a las colas, que son listas especiales. Puede usarse para implementar una amplia variedad de TDA (Tipo de Dato Abstracto), es decir, el TDA Lista, sirve a menudo como una pieza básica en la construcción de los TDA más complicados, como es el caso de las tablas hash, los árboles, los grafos, etc.

4. Ventajas. ▪ ▪ ▪ ▪

▪ ▪

Se puede almacenar en ellas tantos elementos como necesitemos, siempre y cuando haya espacio suficiente espacio en memoria. El orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco. Son muy versátiles. Con ellas puedes representar diversos tipos de estructura de datos, como Listas, Diccionarios, Árboles, Grafos. Al insertar un elemento en la lista, la operación tiene un tiempo constante independientemente de la posición en la que se inserte, solo se debe crear el nodo y modificar los enlaces. Al eliminar un elemento paso lo mismo que se mencionó en el punto anterior. Se accede a cualquier elemento en tiempo constante

5. Desventajas. ▪ ▪ ▪ ▪ ▪ ▪

El acceso a un elemento es más lento, debido a que la información no está en posiciones contiguas de memoria. Al asignar el arreglo en el tiempo de compilación debe establecerse un límite a priori sobre el número de elementos que pueden ser almacenados en las listas. Las listas son accesos secuenciales, y solo puede ser recorrida en una sola dirección. Se requiere de almacenamiento extra para las referencias. Puede resultar lento asignar memoria para cada nuevo elemento. No permite el acceso directo a un elemento arbitrario de la lista. Para acceder al Iésimo elemento, debe recorrer la lista, comenzando por el primer nodo, hasta llegar al elemento deseado.

6. Clasificación. Las listas se clasifican en: 6.1. Listas Simplemente Enlazadas Es una estructura de datos en la que cada elemento apunta al siguiente elemento. De esta forma, con la referencia al inicio de la lista, podemos acceder a todos los elementos de la lista. Son similares al array, excepto que el acceso a los elementos no se realiza a través de índices sino a través de punteros. La asignación de memoria se realiza durante la ejecución. Se puede utilizar cuando necesite realizar varias operaciones para insertar y eliminar elementos, puede utilizar listas vinculadas. 6.2. Listas Doblemente Enlazadas Es una estructura de datos que consiste en un conjunto de nodos enlazados secuencialmente. Cada nodo contiene tres campos, dos para los llamados enlaces, que son referencias al nodo siguiente y al anterior en la secuencia de nodos, y otro más para el almacenamiento de la información (en este caso un entero). El enlace al nodo anterior del primer nodo y el enlace al nodo siguiente del último nodo, apuntan a un tipo de nodo que marca el final de la lista, normalmente un nodo centinela o puntero null, para facilitar el recorrido de la lista. Si existe un único nodo centinela, entonces la lista es circular a través del nodo centinela.

El doble enlace de los nodos permite recorrer la lista en cualquier dirección. Mientras que agregar o eliminar un nodo en una lista doblemente enlazada requiere cambiar más enlaces que en estas mismas operaciones en una lista enlazada simple, las operaciones son más simples porque no hay necesidad de mantener guardado el nodo anterior durante el recorrido, ni necesidad de recorrer la lista para hallar el nodo anterior, la referencia al nodo que se quiere eliminar o insertar es lo único necesario. 6.3. Listas Circulares La lista circular es una especie de lista enlazada simple o doblemente enlazada, pero que posee una característica adicional para el desplazamiento dentro de la lista: esta no tiene fin. Para que la lista sea sin fin, el puntero siguiente del último elemento apuntará hacia el primer elemento de la lista en lugar de apuntar al valor NULL, como hemos visto en el caso de listas enlazadas simples o doblemente enlazadas. En las listas circulares, nunca se llega a una posición en la que ya no sea posible desplazarse. Cuando se llegue al último elemento, el desplazamiento volverá a comenzar desde el primer elemento. 6.4. Listas basadas en array Esta implementación sí que es bastante diferente a la enlazada (a diferencia de la doblemente enlazada y la circular). Junto a la enlazada, son las dos implementaciones más comunes en los lenguajes de programación. La idea es bien simple: ▪ ▪

Tendremos un tipo Lista (struct en C, clase en Python) Este almacenará los datos internamente como un array. ▪ En C tendremos un puntero

Agregar un elemento Adicionar un elemento a la lista de tipo array tiene varios problemas: ▪

Por un lado, es costoso a nivel de memoria, ya que debemos hacer crecer el array una posición, pidiendo memoria = cantidad Actual + 1c

▪

Por otro lado, también podría ser costoso a nivel de tiempo, porque se deben copiar los elementos a la nueva posición (en caso de realocación)

Remover un elemento Esta operación también es costosa. Ya que no podemos simplemente "nullear" la posición donde está el elemento a eliminar, porque tendríamos los índices corridos, y porque tendríamos fragmentación. Necesitamos re-ordenar todos los elementos, corriéndolos a la izquierda. Por ejemplo, si en para la lista anterior nos pueden borrar la "E". Acá podemos ver los pasos:

Acceso aleatorio (lista[i]) Por otro lado, por el contrario, a las listas enlazadas, el acceder a un elemento arbitrario, es decir en la posición "i", es mucho más simple, ya que justamente tenemos todos los elementos contiguos (localidad), con lo cual podemos "indexar", a través de aritmética de punteros (o bien la notación de arrays). Esta operación tiene orden de complejidad constante O (1), y es la principal ventaja de la lista basada en array.

7. Operaciones

En toda estructura de datos hay dos operaciones que sobresalen por encima del resto: Insertar y borrar. Estas dos operaciones aparecerán en toda estructura de datos, puede que, con otro nombre, o con una funcionalidad ligeramente diferente, pero su filosofía será la misma, proporcionar unas operaciones para la construcción de la estructura de datos. ▪ Insertar La operación insertar consiste en la introducción de un nuevo elemento en la lista. En una lista no ordenada no es necesario mantener ningún orden, por lo tanto, la inserción de elementos se puede realizar en cualquier lugar de la lista, al principio, al final, en una posición aleatoria, ... Generalmente se realiza la inserción de tal forma que la complejidad temporal sea mínima, es decir, que sea una operación sencilla para que se realice en el menor tiempo posible. La operación más sencilla depende de la implementación de la estructura de datos, en unos casos puede ser la inserción al inicio, en otros la inserción al final y en este caso la inserción la realiza en el segundo nodo de la lista. Si tenemos la lista... Lista 3, 76, -6 ... e insertamos el elemento 0, la lista quedaría de la siguiente forma: Lista 3, 0, 76, -6 ▪ Borrar La operación borrar consiste en la eliminación de la lista de un elemento concreto. El elemento a borrar será escogido por el programador. La eliminación en una lista no conlleva ningún trabajo adicional más que el propio de la eliminación del elemento en sí. Para borrar un elemento cualquiera habría que realizar un recorrido secuencial de la lista hasta encontrar el nodo buscado y una vez localizado reestructurar los punteros para saltarse el nodo a borrar y así poder eliminarlo. Vamos a verlo con un ejemplo. Borrado del elemento 76 en la lista anterior: Paso 1: Localizar el elemento a borrar. Lista 3, 0, 76, -6 Paso 2: Reestructurar punteros y eliminar nodo.

Lista 3, 0, -6 Otras operaciones A partir de estas dos operaciones básicas cada lista puede presentar muchas operaciones diferentes, vamos a comentar algunas de ellas, dejando claro que las dos básicas que siempre aparecerán son las anteriores. Tamaño: Esta operación suele informar sobre el número de elementos que tiene en ese instante la lista. Buscar: Comprueba si existe un determinado elemento en la lista. Recorrer lista: Recorre toda la lista, realizando una operación en cada nodo. Por ejemplo, mostrar el contenido por pantalla.

8. Implementación

9. Aplicaciones (con ejemplos de la vida cotidiana) Luego de haber estudiado los distintos tipos de listas y entender su funcionamiento, podemos decir que: ▪ ▪ ▪

La lista sencilla puede ser utilizada para organizar las actividades diarias. La lista doble suele utilizarse para los datos de transacción de una cuenta bancaria. La lista circular puede utilizarse con el reproductor de música, para que cuando termine la última canción vuelva a empezar la primera.

Aplicaciones: Las listas son comunes en la vida diaria: listas de alumnos, listas de clientes, listas de espera, listas de distribución de correo, etc....