ufo ufo - 2 months ago 4x
C Question

C - Representation of a matrix as a linked list

I have the following data structure:

enter image description here

that represents a matrix as a linked list.

I need to add a new row of the matrix at the bottom and initialize the values of that list with zeros.

Question: Is it possible to use singly list with two links for each node? That way, we can add a new list at the bottom with horizontal pointers (links).

But I don't understand how to link the vertical pointers (links) with the next list.

Could someone explain how to link vertical pointers of the bottom list?


If I understand the question, then yes its possible, and you can do so iteratively using a pointer-to-pointer and forward chaining, a common technique for building linked lists in input-traversal order.

Given a node structure like this:

struct Node
    struct Node *up;
    struct Node *right;
    int value;

You can hang a one-for-one matching node across the bottom of the "matrix" (meaning, your current bottom row has N nodes, the added row will likewise have N nodes) by doing this:

struct Node *addRow(struct Node *mat)
    struct Node *res = NULL, **pp = &res;
    for (; mat; mat = mat->right)
        *pp = malloc(sizeof **pp);
        (*pp)->value = 0;
        (*pp)->up = mat;
        pp = &(*pp)->right;
    *pp = NULL;
    return res;

This works by walking a pointer-to-pointer through the list being created, always having it address the pointer that will be populated with the next node node to be allocated. When the list is complete, the final right pointer must be set to NULL to terminate the right-chained list (*pp = NULL; accomplishes this).

Execution simply becomes

mat = addRow(mat);

That's it.