Listas enlazadas.

Laboratorio de lenguajes de Programación

Una lista enlazada es una de las estructuras de datos fundamentales, se utiliza para implementar otras estructuras de datos. Esta lista consiste en una secuencia de nodos, en los cuales se guardan campos de datos y uno o dos punteros al nodo anterior o al posterior. La principal ventaja de las listas enlazadas es que a comparación con los arreglos, el orden de los elementos que se enlazan puede ser diferente al orden de almacenamiento en la memoria.

Una lista enlazada contiene un puntero a otro dato del mismo tipo. Estas listas te permiten hacer inserciones y eliminación de nodos en cualquier parte de la lista. Existen diferentes tipos de listas enlazadas: Listas enlazadas simples, listas doblemente enlazadas, listas circulares y listas enlazadas doblemente circulares.

Pueden ser utilizadas en diversos lenguajes, como por ejemplo Lisp y Scheme los cuales tienen estructuras de datos construidas, así como operaciones para acceder a estas listas. Los lenguajes imperativos y los orientados a objetos como C, C++ y Java, tienen referencias para poder crear listas enlazadas.

Estas listas se desarrollaron entre 1955 y 1956 por Cliff Shaw y Herbert Simon en su lenguaje de procesamiento de la información (IPL). Se utilizó para programas que estuvieran relacionados con inteligencia artificial.

Listas enlazadas lineales

Listas simples enlazadas

Este tipo de lista es la básica, tiene un enlace por nodo. Dicho enlace apunta al siguiente nodo de la lista, también puede apuntar al valor NULL o a la lista vacía si es que es el último nodo.

Lista doblemente enlazada

Este es el tipo de lista más sofisticada, también es llamada lista enlazada de dos vías. Hay dos enlaces por nodo, uno apunta al anterior  o si es el primer nodo apunta al valor NULL, y el otro apunta al siguiente nodo, si es el útimo nodo apunta al valor NULL.

Listas enlazadas circulares

En las listas enlazadas circulares, el primer y el último nodo estan unidos. También se puede hacer esto en las listas enlazadas simples y en las doblemente sibles. Para recorrer una lista enlazada simple se puede empezar por cualquier nodo y seguir la lista en cualquier dirección hasta que regrese al nodo original, por lo que estas listas se pueden ver como listas sin comienzo ni fin. Son múy utilizadas para dirigir buffers, ingerir datos y visitar todos los nodos de la lista a partir de uno dado.

Listas enlazadas circulares simples

En este tipo de listas, cada nodo tiene un enlace así como en las listas enlazadas simples, la diferencia es que el siguiente nodo después del último apunta al primero. Los nodos nuevos solo pueden insertarse después de que ya tengamos uno referenciado. Gracias a esto, es usual quedarse con una referencia solamente al último elemento en una lista enlazada simple, lo cual nos permite realizar rápodas inserciones al principio y accesar al primer nodo desde el puntero del último nodo.

Lista enlazada doblemente circular

En estas listas cada nodo tiene dos enlaces, y el enlace anterior del primer nodo apunta al último, así como el enlace siguiente del último nodo apunta al primero. Las inserciones y eliminaciones pueden hacerse desde cualquier punto con acceso a algún nodo cercano. 

Nodos Centinelas

En algunos casos las listas enlazadas cuentan con un nodo centinela, el cual también se conoce como falso o ficticio. Cuando existe este nodo se encuentra al principio o final de la lista y se utiliza para guardar datos.  Su propósito es agilizar o simplificar ciertas operaciones, asegurando que todo nodo tiene un nodo anterior o posterior, y que toda la lista siempre contenga un primer y último nodo.

Algunas aplicaciones de estas listas son en estructuras de datos, como  en pilas, colas y sus variaciones. También son utilizadas para hacer arreglos asociativos, en este caso se llama listas asociativas.

Bueno espero que haya quedado todo claro, saludos a todos:)