¿Qué es una lista ? 

La definición mas general de una lisita es la siguiente: " secuencia lineal y ordenada de elementos" lineal y ordenada hacer referencia a que un elemento es seguido y/o  precedido por un un único otro elemento. Esto quiere decir que para cada elemento en la lista existirá un predecesor y un sucesor, excepto dos  elementos el primer y el ultimo elemento.  En el caso del primer elemento no cuenta con un predecesor y el ultimo que no cuenta con un sucesor. 

Si las listas son implementadas con arreglos, basta con usar el índice de dichos elementos para accesar a ellos; en caso de que sean implementadas con listas enlazadas,  entonces no será posible accesar a ellos aleatoriamente, es por esta razón que será necesario hacer uso de otros elementos como cursores y métodos alternativos.         

Operaciones en una lista: 

Las operaciones mas simples de las listas son las creación, destrucción, inserción, extracción, longitud ordenamiento y búsqueda.    Una característica importante de las listas es que las inserciones se pueden realizar en cualquier parte de la misma.

Listas enlazadas. 

En una lista a lo elementos se le conoce como nodos. Cada nodo tiene la información que se desea procesar, además de  otra referencia a el o los nodos vecinos.  

Tipos de listas enlazadas: 

Hay varios tipos de listas enlazadas, entre las que se incluyen:

• Lista enlazada simple: Cada nodo solo tiene un puntero que apunta al siguiente nodo en la secuencia. 

• Lista enlazada doble: Cada nodo tiene dos punteros, uno que apunta al siguiente nodo y otro que apunta al nodo anterior en la secuencia.                    
• Lista enlazada circular: La lista se cierra en un ciclo, donde el último nodo apunta al primer nodo de la lista.

Elementos en una lista enlazada:

Cursor: Apuntador que pude moverse libremente  

Nodo inicial (first): Apuntador al primer nodo "nunca se debe perder".

Nodo ultimo (last): Es un apuntador al ultimo nodo.   

Nodo: Cada nodo consta  principalmente de los siguientes elementos:

1. Dato: Almacena el elemento que queremos guardar en la lista.
2. Referencia al siguiente nodo: Un puntero que apunta al siguiente nodo en la lista.
3. Referencia al nodo anterior:  En el caso de estar de las listas enlazada dobles. 

Recorrido en una lista enlazada.

En el caso de las listas, al carecer de índice, no es tan fácil acceder directa o aleatoriamente a sus nodos, ya que para ello es necesario acceder al primer nodo mediante el puntero externo, al segundo, después de acceder al primero, etc. Afortunadamente, esto se resuelve, usando una variable puntero, auxiliar X, que apunte en cada momento al nodo procesado, de forma que,  con solo hacer la asignación: X ← SIG(X), esto es guardar en X el campo puntero del nodo.

Inserción de un elemento. 

Insertar, al igual que borrar, consiste básicamente en modificar los punteros de la lista. En cualquier inserción necesitamos disponer de un nodo vacío, donde depositar la información que queremos añadir; posteriormente  buscamos la posición donde queremos insertar nuestro elemento y reasignamos los apuntadores síguete y posterior de nuestros nodos. 

Eliminación de un elemento. 

Al igual que el caso de la inserción,  es necesario buscar ele elemento que se desea eliminar  y resignar los apuntadores siguiente y posterior de nuestros nodos, a diferencia de la inserción no se  necesita  un nuevo nodo vacío, la siguiente imagen muestra este proceso.

1) Búsqueda  y Eliminación 

2) Reasignación de punteros. 

Operaciones en una lista enlazada.

• Insertar (Insert): Agrega un nuevo elemento a la lista en una posición específica.
• Eliminar desde el frente (Remove Front): Elimina el primer elemento de la lista.
• Obtener (Get): Devuelve el elemento en una posición específica de la lista. 
• Longitud (Len): Devuelve el número de elementos en la lista. 
• ¿Está vacía? (IsEmpty): Verifica si la lista está vacía. 
• Vaciar (MakeEmpty): Elimina todos los elementos de la lista. 
• Cursor al principio (Cursor First): Mueve el "cursor" (puntero) al primer elemento de la lista. 
• Cursor al final (Cursor Last): Mueve el "cursor" al último elemento de la lista. 
• Cursor al siguiente (Cursor Next): Mueve el "cursor" al siguiente elemento de la lista. 
• Buscar (Find): Busca un elemento específico en la lista y devuelve su posición si se encuentra, de lo contrario devuelve un valor indicando que el elemento no está en la lista.