No encontrado

Listas enlazadas

Daniel Cocotle

¿Qué es una lista? Una lista es una colección de elementos organizados en secuencia que puede crecer y decrecer libremente y a cuyos elementos individuales se puede acceder, insertar y eliminar en cualquier posición. Una lista lineal se almacena en la memoria principal de una computadora en posiciones sucesivas de memoria.

Las líneas así definidas se denominan listas contiguas. Los elementos de la lista se almacenan normalmente en posiciones consecutivas de memoria, es decir, almacenamiento secuencial, donde se define la constante longitud máxima, que determina el tamaño de la mayor lista que se puede tener. Se implementan a través de arreglos, donde la inserción o eliminación de un elemento excepto en la cabecera o al final de la lista necesitará una traslación de los elementos de la lista.

Operaciones en listas

Las operaciones que se pueden realizar con listas lineales contiguas son:

  • Insertar, eliminar o localizar un elemento
  • Determinar el tamaño (número de elementos) de la lista
  • Recorrer la lista para localizar un determinado elemento
  • Clasificar los elementos de la lista en orden ascendente o descendente
  • Unir dos o más listas en una sola
  • Dividir una lista en varias sublistas
  • Copiar la lista
  • Borrar la lista

Lista enlazada

Una lista enlazada o encadenada es una lista que se construye empleando apuntadores. Además, no tiene un tamaño fijo, sino que puede crecer y decrecer durante la ejecución del programa. Se constituyen como variables dinámicas. En las listas enlazadas no es necesario que los elementos en la lista sean almacenados en posiciones físicas adyacentes, ya que el apuntador indica dónde se encuentra el siguiente elemento de la lista.

Por consiguiente, la inserción y borrado no exigen desplazamiento como en el caso de las listas contiguas.Una lista enlazada sin ningún elemento se llama lista vacía. Su puntero inicial o de cabecera tiene el valor nulo (null).

Una lista enlazada se define por:

  • El tipo de sus elementos: campo de información (datos) y campo enlace (puntero)
  • 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 (null)