Lista enlazada ortogonal

Una Lista Enlazada Ortogonal es una estructura de datos compuesta por elementos fundamentales llamados Nodes (similares a las listas enlazadas). Cada Node en una lista enlazada ortogonal apunta a otros 4 Nodes, a saber, arriba, abajo, izquierda y derecha. En esencia, al igual que una array es una versión 2D de un arreglo, una lista enlazada ortogonal es una versión 2D de una lista enlazada lineal. 

Algoritmo para convertir una array en una lista enlazada ortogonal:

1. Cree un Node para cada celda de la array. En un mapa, y también almacena el valor de la celda y un puntero al Node creado para la celda.
2. Si la fila actual (i) no es la fila 0 de la array, establezca el puntero hacia arriba del Node actual en el Node de la celda justo encima de él (utilice el mapa para obtener el puntero correcto) y establezca el puntero hacia abajo del Node superior en el Node actual. 
3. De manera similar, si la columna actual (j) no es el 0 , la columna de la array, establezca el puntero izquierdo del Node actual en el Node de la celda a la izquierda del Node actual y establezca el puntero derecho del Node a la izquierda en el Node actual. Node
4. repita el proceso 1 a 3 para cada celda en la array
5. return map[matrix[0][0]] para devolver el puntero al Node superior izquierdo de la lista enlazada ortogonal

A continuación se muestra una implementación del algoritmo anterior.

Input:
    matrix = {
    {1, 2, 3},
    {4, 5, 6},
    {7, 8, 9}
    }

Output: 
    A Node pointing to the top-left corner of the orthogonal linked list.
    
       ^      ^      ^
       |      |      |
    <--1 <--> 2 <--> 3-->
       ^      ^      ^
       |      |      |
       v      v      v
    <--4 <--> 5 <--> 6-->
       ^      ^      ^
       |      |      |
       v      v      v
    <--7 <--> 8 <--> 9-->
       |      |      |
       v      v      v

#include <bits/stdc++.h>
using namespace std;
 
struct MatrixNode
{
    int _val;
    MatrixNode* _u; // pointer to node above
    MatrixNode* _d; // pointer to node below
    MatrixNode* _l; // pointer to node towards left
    MatrixNode* _r; // pointer to node towards right
 
    // Constructor for MatrixNode
    MatrixNode( int val = 0,
                MatrixNode* u = nullptr,
                MatrixNode* d = nullptr,
                MatrixNode* l = nullptr,
                MatrixNode* r = nullptr )
        {
            _val = val;
            _u = u;
            _d = d;
            _l = l;
            _r = r;
        }
};
 
MatrixNode* BuildOrthogonalList(int matrix[][3], int r, int c)
{
    // an unordered_map to store the {value, pointers} pair
    // for easy access while building the list
    unordered_map<int, MatrixNode*> mp;
 
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            // create a newNode for each entry in the matrix
            MatrixNode* newNode = new MatrixNode(matrix[i][j]);
            // store the pointer of the new node
            mp[matrix[i][j]] = newNode;
 
            // set the up and down pointing pointers correctly
            if(i != 0)
            {
                newNode->_u = mp[matrix[i - 1][j]];
                mp[matrix[i - 1][j]]->_d = newNode;
            }
 
            // similarly set the left and right pointing pointers
            if(j != 0)
            {
                newNode->_l = mp[matrix[i][j - 1]];
                mp[matrix[i][j - 1]]->_r = newNode;
            }
        }
    }
 
    // return the start of the list
    return mp[matrix[0][0]];
}
 
void PrintOrthogonalList(MatrixNode* head)
{
    MatrixNode* curRow; // will point to the begin of each row
    MatrixNode* cur; // will traverse each row and print the element
    for(curRow = head; curRow != nullptr; curRow = curRow->_d)
    {
        for(cur = curRow; cur != nullptr; cur = cur->_r)
        {
            cout << cur->_val << " ";
        }
        cout << endl;
    }
}
 
int main()
{
    int matrix[3][3] = {
        {1, 2, 3},
        {4, 5, 6},
        {7, 8, 9}
    };
 
    MatrixNode* list = BuildOrthogonalList(matrix, 3, 3);
    PrintOrthogonalList(list);
 
    return 0;
}

Aplicación:
La aplicación más común de la lista enlazada ortogonal es en representación de array dispersa. En resumen, una array dispersa es una array en la que la mayoría de sus elementos son ceros (o cualquier constante conocida). Aparecen a menudo en aplicaciones científicas. Representar arrays dispersas como una array 2D es un gran desperdicio de memoria. En cambio, las arrays dispersas se representan como una lista enlazada ortogonal. Creamos un Node solo para elementos distintos de cero en la array y en cada Node, almacenamos el valor, el índice de fila y el índice de columna junto con los punteros necesarios a otros Nodes. Esto ahorra una gran cantidad de gastos generales de rendimiento y es la forma más eficiente en memoria para implementar una array dispersa.