Listas Enlazadas

Listas enlazadas: en ciencias de la computación es una estructura de datos fundamental 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 y/o posterior. El principal beneficio de las listas enlazadas respecto a los arreglos convencionales es que el orden de los elementos enlazados pueden 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 contiene un puntero o enlace a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminaciones de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto esta previamente identificado o localizado), pero no permite un acceso aleatorio.

Tipos de listas enlazadas

Listas enlazadas simple: es la básica, 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.

Listas Doblemente enlazadas: un tipo de lista enlazada de 2 vias. Cada nodo tiene dos enlaces: uno apunta al nodo anterior o al valor null o a la lista vacia si es el primer nodo, y otro q apunta al siguiente nodo siguiente o a la lista vacia si es el último nodo. Esta contiene 3 valores: el valor, el enlace al nodo siguiente y otro al anterior.

Listas circulares: en esta, el primer y último nodo están unidos. Esto se puede hacer tanto para listas enlazadas 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 q regrese al nodo original. Desde otro punto de vista las listas enlaz circulares pueden ser vistas como listas sin comienzo ni fin, este tipo de listas es el mas usado para dirigir buffers para ingerir datos y para visitar todos los nodos de la lista a partir de un nodo dado.

Listas enlazadas circulares simples: cada nodo tiene un enlace similar al de las listas enlaz simples excepto que el siguiente nodo del último apunta al primero. Como en una lista enlaz 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 de una lista enlaz circular simple, esto nos permite rápidas inserciones al principio y también permite acceso al primer nodo desde el puntero del último nodo.

Listas doblemente enlazadas circulares: cada nodo tiene 2 enlaces similar a los de la lista doblemente enlaz. Excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo apunta al primero.

...