Definición.
Una lista es, en general, una colección lineal de elementos; mientras que una lista enlazada es, en el contexto que nos compete, una colección lineal de objetos (nodos) auto referidos.
Se tiene acceso a una lista enlazada por medio de una referencia al primer nodo de la lista. Aunque resulta más conveniente, por las características inherentes a la implementación de la estructura de datos, que existan dos referencias a la misma: una que refiera el inicio de la lista, y otra que refiera el fin de la lista. El acceso a los nodos intermedios subsecuentes, se realiza a través del enlace o referencia que contiene cada uno de ellos.
Una lista enlazada es más conveniente que un arreglo estático por ejemplo, cuando no es posible determinar con anticipación el número de elementos a almacenar en la estructura de datos.
Las listas enlazadas son dinámicas, por lo que se puede aumentar o disminuir a discreción el número de elementos de la lista. Un aspecto importante a considerar respecto a las listas enlazadas es que pueden, simplemente por conveniencia, mantenerse en orden (tome en cuenta el lector que, aunque esto puede resultar sumamente conveniente, no es una característica inherente a la estructura de datos) insertando cada nuevo elemento en el punto apropiado dentro de la lista enlazada.
Se tiene acceso a una lista enlazada por medio de una referencia al primer nodo de la lista. Aunque resulta más conveniente, por las características inherentes a la implementación de la estructura de datos, que existan dos referencias a la misma: una que refiera el inicio de la lista, y otra que refiera el fin de la lista. El acceso a los nodos intermedios subsecuentes, se realiza a través del enlace o referencia que contiene cada uno de ellos.
Una lista enlazada es más conveniente que un arreglo estático por ejemplo, cuando no es posible determinar con anticipación el número de elementos a almacenar en la estructura de datos.
Las listas enlazadas son dinámicas, por lo que se puede aumentar o disminuir a discreción el número de elementos de la lista. Un aspecto importante a considerar respecto a las listas enlazadas es que pueden, simplemente por conveniencia, mantenerse en orden (tome en cuenta el lector que, aunque esto puede resultar sumamente conveniente, no es una característica inherente a la estructura de datos) insertando cada nuevo elemento en el punto apropiado dentro de la lista enlazada.
Normalmente los nodos de las listas enlazadas no están almacenados en forma contigua en la memoria; sin embargo, lógicamente los nodos aparecen como contiguos. Esto obedece a su representación física y lógica respectivamente.
Operaciones primitivas.
Se definen cinco operaciones primitivas sobre una lista enlazada (entre paréntesis aparece la definición para C++):
- La operación insertaAlInicio (inserta_al_inicio) agrega un elemento al inicio de la lista enlazada.
- La operación insertaAlFinal (inserta_al_final) agrega un elemento al final de la lista enlazada.
- La operación eliminaDelInicio (elimina_del_inicio) elimina un elemento del inicio de la lista enlazada.
- La operación eliminaDelFinal (elimina_del_final) elimina un elemento del final de la lista enlazada.
- La operación estaVacia (esta_vacia) regresa verdadero o falso, dependiendo de si la lista enlazada contiene o no elementos respectivamente.
Tome en cuenta que los elementos de una lista enlazada podrían ser insertados en cualquier parte, y que en función de ellos, podrían ser definidas más operaciones sobre una lista enlazada, por lo que el mecanismo de inserción estará en función directa de las necesidades específicas para la implementación de la estructura de datos.
En este sentido, si se desea mantener una lista enlazada ordenada por ejemplo, se deberá ir recorriendo la lista enlazada de manera secuencial, hasta encontrar el lugar apropiado para la inserción de cada uno de los elementos que la conformarán.
Por otro lado, la eliminación de un elemento particular, podría consistir en primer lugar, en la localización de dicho elemento dentro de la lista enlazada. Si existe, se procede a su correspondiente eliminación; en caso contrario, se debería indicar que el elemento que se está intentando eliminar, no existe dentro de la estructura de datos.
En este sentido, si se desea mantener una lista enlazada ordenada por ejemplo, se deberá ir recorriendo la lista enlazada de manera secuencial, hasta encontrar el lugar apropiado para la inserción de cada uno de los elementos que la conformarán.
Por otro lado, la eliminación de un elemento particular, podría consistir en primer lugar, en la localización de dicho elemento dentro de la lista enlazada. Si existe, se procede a su correspondiente eliminación; en caso contrario, se debería indicar que el elemento que se está intentando eliminar, no existe dentro de la estructura de datos.
Representación.
Como se mencionó en la sección anterior, el acceso a una lista enlazada se realiza por al menos una referencia al primer nodo de dicha lista enlazada. Aunque por otro lado, resulta más conveniente, por las características inherentes a la implementación de la estructura de datos, que existan dos referencias hacia la misma: una que refiera el inicio de la lista enlazada, y otra que refiera el fin de la lista enlazada.
El acceso a los nodos intermedios subsecuentes se realiza a través del enlace o referencia que contiene cada uno de ellos. Por regla convencional, para marcar el fin de la lista enlazada, el enlace al siguiente nodo en el último nodo de la lista enlazada se establece a null (nullptr).
La representación mostrada en la siguiente figura es una abstracción de la implementación que se realizará en una entrada posterior. También coincide con la representación lógica de una lista enlazada.
El acceso a los nodos intermedios subsecuentes se realiza a través del enlace o referencia que contiene cada uno de ellos. Por regla convencional, para marcar el fin de la lista enlazada, el enlace al siguiente nodo en el último nodo de la lista enlazada se establece a null (nullptr).
La representación mostrada en la siguiente figura es una abstracción de la implementación que se realizará en una entrada posterior. También coincide con la representación lógica de una lista enlazada.
 |
| Abstracción de una lista enlazada como una secuencia de nodos. |
Observe cómo la figura anterior luce muy similar a la figura correspondiente a las colas de espera, ya que también hace uso de dos referencias: inicio y fin, mismas que denotan respectivamente el primero y el último de los elementos almacenados en la lista enlazada. Note también que, para el caso de un solo elemento, dichas referencias harán referencia, valga la redundancia, al mismo nodo.
Por otro lado, los diagramas de clases UML que se presentan a continuación, muestran el diseño de clases de la lista enlazada que se desea implementar. Dicho diseño complementa, en conjunción con la definición hecha con anterioridad, el concepto de lista enlazada.
Por otro lado, los diagramas de clases UML que se presentan a continuación, muestran el diseño de clases de la lista enlazada que se desea implementar. Dicho diseño complementa, en conjunción con la definición hecha con anterioridad, el concepto de lista enlazada.
 |
| Diagrama de clases UML para la lista enlazada (Java). |
 |
| Diagrama de clases UML para la lista enlazada (C++). |
Los diagramas de clases UML de las figuras anteriores muestran también la relación que existe entre las clases más importantes que se involucrarán durante la implementación de la lista enlazada. Tome el lector el tiempo que considere necesario para revisar, analizar y comprender dichos diagramas de clases antes de avanzar a la implementación correspondiente.
