Última actualización de la serie: Noviembre de 2019.
Artículos de la serie:
En este post analizaremos los aspectos básicos del diseño de una lista lineal doblemente enlazada, inspirándonos en las implementaciones de estructuras dinámicas de datos estándar de este tipo facilitadas por compiladores profesionales, muy especialmente GCC [1]. Como es habitual, nuestra motivación aquí es puramente educativa, de manera que algunas de las elecciones en la implementación de la lista serán ciertamente discutibles y mejorables, pero no restarán valor pedagógico al conjunto.
En contraste con un vector, donde los objetos ocupan posiciones adyacentes, los elementos contenidos en una lista (a los que nos referiremos desde ahora bajo el nombre de nodos) se encuentran generalmente desperdigados en memoria (ver la imagen superior), siendo necesario que cada uno de ellos almacene la posición del elemento inmediatamente posterior (resultando una lista simplemente enlazada) así como, opcionalmente, del elemento inmediatamente anterior (lista doblemente enlazada). Centraremos nuestra atención en este segundo caso (doble enlace), al ser el más general.
Procedemos, para ello, a definir un agregado Node_base que contenga dos punteros: uno al nodo anterior (prev) y otro al nodo posterior (next), respectivamente. Observemos que, en este punto concreto de nuestro diseño, preferimos no introducir aún la variable que define el área de datos para la lista. Existen dos razones para ello:
Procedemos, para ello, a definir un agregado Node_base que contenga dos punteros: uno al nodo anterior (prev) y otro al nodo posterior (next), respectivamente. Observemos que, en este punto concreto de nuestro diseño, preferimos no introducir aún la variable que define el área de datos para la lista. Existen dos razones para ello:
- De esta manera, la estructura Node_base no requiere ser parametrizada con el tipo de variable contenida en la lista. Ello evita replicaciones de código, al ser innecesaria la creación de distintas instancias de la estructura según el tipo de dato almacenado.
- Las operaciones de inserción, eliminación e intercambio de nodos en la lista (las cuales, si pensamos en ello, sólo involucran a los punteros de posicionamiento prev y next, pero no al área de datos) quedan definidas en la estructura Node_base, obteniéndose una separación formal entre dichas operaciones y las funciones miembro de la lista. Ello simplificará, como comprobaremos más adelante, el diseño del contenedor.
Incluiremos la estructura Node_base en un espacio de nombre detail, dando a entender con ello que se trata de un aspecto específico de la implementación de la lista de la que ningún usuario debiera hacer un uso explícito:
Las mencionadas operaciones de inserción (hook), desligadura (unhook) e intercambio (swap) de nodos, así como algunas otras funciones adicionales, resultan relativamente fáciles de codificar en la práctica (ver [1] y [2] para más detalles). Es recomendable, en todo caso, esbozar unos pocos gráficos como los abajo proporcionados (indicando las direcciones pasadas y futuras de los punteros involucrados) para convencernos de la correcta implementación de estos métodos:
namespace detail {
struct Node_base {
Node_base* prev, // nodo previo
* next; // próximo nodo
void hook(Node_base* p) noexcept; // ubicar este nodo antes de p
void unhook() noexcept; // aislar este nodo del resto
void swap(Node_base& p) noexcept; // intercambiar este nodo y p
};
}
Las mencionadas operaciones de inserción (hook), desligadura (unhook) e intercambio (swap) de nodos, así como algunas otras funciones adicionales, resultan relativamente fáciles de codificar en la práctica (ver [1] y [2] para más detalles). Es recomendable, en todo caso, esbozar unos pocos gráficos como los abajo proporcionados (indicando las direcciones pasadas y futuras de los punteros involucrados) para convencernos de la correcta implementación de estos métodos:
Ligadura/inserción (hook): Esta función inserta el nodo this que la invoca delante del nodo p pasado por argumento.
void hook(Node_base* p) noexcept
{
next = p;
prev = p->prev;
p->prev = p->prev->next = this;
}
Desligadura (unhook): Esta función aisla al nodo this que la invoca, de modo que sus campos prev y next terminan apuntando al propio objeto. En ausencia del nodo, los nodos anterior y posterior en la lista original se enlazan convenientemente entre sí.
void unhook() noexcept
{
prev->next = next;
next->prev = prev;
next = prev = this;
}
Intercambio (swap): Esta función intercambia dos nodos, distinguiéndose tres casos: (i) el nodo this a través del cual se realiza la llamada a la función es parte de una lista, al igual que el nodo p (ver la figura inferior); (ii) el nodo this es parte de una lista, mientras que p se encuentra aislado; (iii) el nodo this se encuentra aislado, pero no así el nodo p que forma parte de una lista.
void swap(Node_base& p) noexcept
{
if (next != this) { // si el nodo forma parte de la lista...
if (p.next != &p) { // ...al igual que p
std::swap(next, p.next);
std::swap(prev, p.prev);
next->prev = prev->next = this;
p.next->prev = p.prev->next = &p;
}
else { // ...pero p está aislado
p.next = next;
p.prev = prev;
p.next->prev = p.prev->next = &p;
next = prev = this;
}
}
else if (p.next != &p) { // este nodo está aislado, no así p
next = p.next;
prev = p.prev;
next->prev = prev->next = this;
p.next = p.prev = &p;
}
}
En el segundo post de esta serie analizaremos en detalle el uso de la estructura Node_base que acabamos de implementar en el diseño de la plantilla de clase List<>, que representará una lista lineal doblemente enlazada.
Referencias bibliográficas:
- [1] GCC Compilers - libstdc++ API - https://gcc.gnu.org/onlinedocs/gcc-6.1.0/libstdc++/api/. La lista estándar std::list<> se encuentra distribuida bajo la licencia GPL v3, con una cláusula adicional heredada de SGI. Consúltense los términos de distribución en https://gcc.gnu.org/onlinedocs/gcc-6.1.0/libstdc++/api/a01624_source.html
- [2] Cormen T. H., et al., Introduction to Algorithms, 3rd Edition, MIT Press.
No hay comentarios:
Publicar un comentario