listas enlazadas
Páginas: 19 (4528 palabras)
Publicado: 19 de noviembre de 2013
LISTAS ENLAZADAS
1) INTRODUCCION
Una lista enlazada es una de las estructuras de datos dinámicas fundamentales, y puede ser usada para implementar otras estructuras de datos.
Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior.
El principal beneficio de las listas enlazadas respecto a losarreglos convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo.
Las listas enlazadas permiten inserciones yeliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio.
Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.
Las listas enlazadas pueden serimplementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.
2) Tipos de Listas Enlazadas
2.1 Listas enlazadas lineales
2.1.1 Listas simplesenlazadas
2.1.2 Lista Doblemente Enlazada
2.2 Listas enlazadas circulares
2.2.1 Listas enlazadas circulares simples
2.2.2 Lista Enlazada Doblemente Circular
2.3 Nodos Centinelas
Listas enlazadas lineales:
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 listavací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 nodosiguiente, 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
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.
Listas enlazadascirculares:
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 circularespueden 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 nododel ú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...
1) INTRODUCCION
Una lista enlazada es una de las estructuras de datos dinámicas fundamentales, y puede ser usada para implementar otras estructuras de datos.
Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias (punteros) al nodo anterior o posterior.
El principal beneficio de las listas enlazadas respecto a losarreglos convencionales es que el orden de los elementos enlazados puede ser diferente al orden de almacenamiento en la memoria o el disco, permitiendo que el orden de recorrido de la lista sea diferente al de almacenamiento.
Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo.
Las listas enlazadas permiten inserciones yeliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio.
Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.
Las listas enlazadas pueden serimplementadas en muchos lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras de datos ya construidas, junto con operaciones para acceder a las listas enlazadas. Lenguajes imperativos u orientados a objetos tales como C o C++ y Java, respectivamente, disponen de referencias para crear listas enlazadas.
2) Tipos de Listas Enlazadas
2.1 Listas enlazadas lineales
2.1.1 Listas simplesenlazadas
2.1.2 Lista Doblemente Enlazada
2.2 Listas enlazadas circulares
2.2.1 Listas enlazadas circulares simples
2.2.2 Lista Enlazada Doblemente Circular
2.3 Nodos Centinelas
Listas enlazadas lineales:
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 listavací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 nodosiguiente, 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
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.
Listas enlazadascirculares:
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 circularespueden 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 nododel ú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...
Leer documento completo
Regístrate para leer el documento completo.