What is an "orthogonal linked list"?

Question

I understand what a linked list is, but my question is what is an orthogonal linked list? I searched on the web but couldn't find any helpful information. I am studying liked list in C++, if there any good books related to linked lists, please mention them.

Answer 1

This is not a very common term, but, according to the Dictionary of Computing, it is a multi-dimensional linked list whose elements hold pointers to neighbors in each dimension.

Take a simple matrix:

1 2 3 
4 5 6
7 8 9

Then,the element 5 would have a pointer to 4 and 6, but also to 2 and 8.

And the following questions might be helpful regarding C++ books:

• The Definitive C++ Book Guide and List
• https://stackoverflow.com/questions/74405/what-is-the-best-c-book-for-an-intermediate-to-expert-developer

Answer 2

Orthogonal linked list is combination of row and column list. So you can use it to represent a 2D array ( as it has also rows and columns )

In computer science generally we use it to represent sparse matrix so that the complexity of multiplication of big matrix decreases.

The first linked list consisted of non zero rows and each node points to its right and bottom non zero element.

typedef struct Orthogonal_linked_list_node
{
    float some_data;
    int row;
    int column;
    struct _matrix_element *next_row;
    struct _matrix_element *next_column;
}matrixNode;