Concepto: Una lista enlazada es una colección lineal de estructuras autoreferenciadas llamadas nodos, conectadas por enlaces de apuntador.

El acceso a una lista enlazada por medio de un apuntador al primer nodo de la lista y a los nodos subsecuentes por medio del apuntador de enlace almacenado en cada nodo.

Fin de lista: Para marcar el fin de lista, el apuntador de enlace en el último nodo de la lista , se define a NULL.

Almacenamiento dinámico: En una lista enlazada lista datos se almacenan dinámicamente, es decir, cada nodo se crea conforme sea necesario.

Cada nodo puede contener datos de cualquier tipo, incluyendo otras struct. Las pilas y las colas también son estructuras de datos lineales, y como veremos son versiones restringidas de las lista enlazadas.

Ventajas:

• Una lista enlazada es apropiada cuando no es predecible de inmediato el número de elementos de datos a representarse en la estructura.
• Son dinámicas, por lo que conforme sea necesario, la longitud de la lista puede aumentar o disminuir, mientras que los arreglos que almacenan las listas de datos no son dinámicos, la memoria del arreglo es asignada en tiempo de compilación.
• Las lista enlazadas sólo se llenan cuando el sistema no tiene suficiente memoria para satisfacer las solicitudes de asignación dinámica de almacenamiento.

Las dos funciones primarias de las lista enlazadas son insert y delete. La función isEmpty se conoce como una función predicada, no altera en forma alguna la lista; más bien determina si la lista está vacia. La función printList imprime la lista.

Supongamos una lista de caracteres, los cuales se insertan en orden alfabético. La función insert recibe la dirección de la lista y el carácter a insertarse. Dado que la lista propiamente dicha es un apuntador (a su primer elemento) pasar la dirección de la lista crea un apuntador a un apuntador (es decir, una doble indirección). Los pasos para la inserción de un carácter en la lista son los siguientes:

1. Crear un nodo llamando a malloc, asignando a newPtr la dirección de la memoria asignada, asignando el caracter a insertarse a newPtr->data, y asignando NULL a newPtr->nextPtx.
2. Inicialice previousPtr a NULL, y currentPtr a *sPtr (el apuntador al inicio de la lista). Los apuntadores previousptr y currentPtr se utilizan para almacenar las posiciones del nodo anterior al punto de inserción y del nodo posterior al punto de inserción.
3. En tanto currentPtr no sea NULL y el valor a insertarse sea mayor que currentPtr->data, asigne currentPtr->data, asigne currentPtr a previousPtr y avance currentPtr al siguiente nodo de la lista. Esto proporciona en la lista el punto de inserción del valor.
4. Si previousPtr es NULL, se inserta el nuevo nodo como primer nodo de la lista . Asigne *sPtr a newPtr->nextPtr (el nuevo enlace de nodo apunta al anterior primer nodo), y asigne newPtr a *sPtr (*sPtr apunta al nuevo nodo). Si previousPtr no es NULL (el nodo anterior apunta al nuevo nodo), y asigne currentPtr a newPtr-> nextPtr (el enlace de nuevo nodo al nodo actual).

La función delete recibe la dirección del apuntador hacia el principio de la lista y un carácter a borrarse. Los pasos para borrar un carácter de la lista son como siguen:

1. Si el carácter a borrarse coincide con el primer carácter del primer nodo de la lista, asigna *sPtr a tempPtr (tempPtr será utilizado para liberar , usando free, la memoria no necesaria), asigna (*sPtr)->nextPtr a *sPtr (*sPtr ahora apunta al segundo nodo de la lista), free libera la memoria apuntada por tempPtr, y regresa el carácter que fue borrado.
2. De no ser así, inicializa previousPtr con *sPtr e inicializa currentPtr con (*sPtr)->nextPtr.
3. En tanto currentPtr no sea NULL y el valor a borrarse no sea igual a currentPtr->data, asigna currentPtr a previousPtr, y asigna currentPtr->nextPtr a currentPtr. Esto localizará el carácter a borrarse, si está contenido dentro de la lista.
4. Si currentPtr no es NULL, asigna currentPtr a tempPtr, asigna currentPtr->nextPtr a previousPtr->nextPtr, libera el nodo al cual apunta tempPtr, y regresa el carácter que fué borrado de la lista. Si currentPtr es NULL, regresa el carácter NULL ('\0'), pra significar que el carácter a borrarse no fué encontrado dentro de la lista.