LISTAS
concepto:
La lista enlazada es un TDA que nos permite almacenar datos de una forma organizada, al igual que los vectores pero, a diferencia de estos, esta estructura es dinámica, por lo que no tenemos que saber "a priori" los elementos que puede contener.
TIPOS DE LISTAS
conceptoListas enlazadas lineales
Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo
Una lista doblemente enlazada contiene tres valores: el valor, el link al nodo siguiente, y el link al anterior En algún lenguaje de muy bajo nivel, XOR-Linking ofrece una vía para implementar listas doblemente enlazadas, usando una sola palabra para ambos enlaces, aunque el uso de esta técnica no se suele utilizar.
Una lista enlazada circular que contiene tres valores enteros
Listas simples enlazadas
La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.
Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo
Lista Doblemente Enlazada
Un tipo de lista enlazada más sofisticado es la lista doblemente enlazada o lista enlazadas de dos vías. Cada nodo tiene dos enlaces: uno apunta al nodo anterior, o apunta al valor NULL si es el primer nodo; y otro que apunta al nodo siguiente, o apunta al valor NULL si es el último nodo.
Una lista doblemente enlazada contiene tres valores: el valor, el link al nodo siguiente, y el link al anterior
Listas enlazadas circulares
En una lista enlazada circular, el primer y el último nodo están unidos juntos. Esto se puede hacer tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer una lista enlazada circular podemos empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. Desde otro punto de vista, las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin. Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.
Una lista enlazada circular que contiene tres valores enteros
Listas enlazadas circulares simples
Cada nodo tiene un enlace, similar al de las listas enlazadas simples, excepto que el siguiente nodo del último apunta al primero. Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado. Por esta razón, es usual quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo.Lista Enlazada Doblemente Circular
En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza o al nodo cola, y así mantener el orden tan bien como en una lista doblemente enlazada.Operaciones básicas de las listas
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...
... e insertamos el elemento 0, la lista quedaría de la siguiente forma:
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.
Paso 2: Reestructurar punteros y eliminar nodo.
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.
No hay comentarios:
Publicar un comentario