Generate matrix from given Sparse Matrix using Linked List and reconstruct the Sparse Matrix

0 0 15 minutes read

Given a sparse matrix mat[][] of dimensions N*M, the task is to construct and represent the original matrix using a Linked List and reconstruct the givensparse matrix.

Examples:

Input: mat[][] = {{0, 1, 0, 0, 0}, {0, 1, 0, 0, 0}, {0, 0, 2, 0, 0}, {0, 3, 0, 0, 4}, {0, 0, 5, 0, 0}}
Output:
Linked list representation: (4, 2, 5) ? (3, 4, 4) ? (3, 1, 3) ? (2, 2, 2) ? (1, 1, 1) ? (0, 1, 1) ? NULL
Original matrix:
{{0, 1, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 0, 2, 0, 0},
{0, 3, 0, 0, 4}
{0, 0, 5, 0, 0}}

Input: mat[][] = {{0, 0, 0, 4, 0}, {0, 1, 0, 0, 0}}
Output:
Linked list representation: (1, 1, 1) ? (0, 3, 4) ? NULL
Original matrix:
{{0, 0, 0, 4, 0},
{0, 1, 0, 0, 0}}

Approach: The given problem can be solved by storing the row index, column index, its value, and the next pointer of all non-zero elements in the node of the linked list. Follow the steps below to solve the problem:

For the construction of the sparse matrix using a linked list, traverse the matrix, and for every non-zero element create a new node and insert this newly created node to the beginning of the list.
For the reconstruction, create an auxiliary 2D array of dimensions N*M with all entries as 0, then traverse the linked list and update all the non-zero elements in this newly created array.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
#include <iostream>
#include <vector>
 
using namespace std;
 
// Linked list node
struct SNode {
    int data;
    int Col;
    int Row;
    SNode* next;
};
 
// Store the head pointer of the linked list
// and the size of the matrix
struct MatrixNode {
    vector<vector<int> > Matrix;
    SNode* SNPTR;
};
 
// Function to create a new node
SNode* CreateList(int Row, int Col, int data)
{
 
    // Create a new node
    SNode* New = new SNode();
 
    // Update the value and the row
    // and column index and set the
    // next pointer to NULL
    New->data = data;
    New->Col = Col;
    New->Row = Row;
    New->next = NULL;
 
    return New;
}
 
// Function to insert a node at the
// beginning of the linked list
MatrixNode* AddInList(MatrixNode* MNhead, int Row, int Col,
                      int data)
{
    MatrixNode* Mptr = MNhead;
 
    // Create a new node
    SNode* New = CreateList(Row, Col, data);
 
    // If the head is NULL, point it to the newly
    // created node
    if (Mptr->SNPTR == NULL) {
        Mptr->SNPTR = New;
        return MNhead;
    }
 
    // Insert this node at beginning
    New->next = Mptr->SNPTR;
 
    // Update the head pointer
    Mptr->SNPTR = New;
 
    return MNhead;
}
 
// Function to construct the sparse
// matrix using linked list
MatrixNode*
ConstructSparseMatrix(MatrixNode* MNhead,
                      vector<vector<int> > Matrix,
                      SNode* SNhead)
{
    MatrixNode* Mptr = MNhead;
 
    // If the head pointer is NULL
    if (MNhead == NULL) {
        MNhead = new MatrixNode();
        MNhead->Matrix = Matrix;
        MNhead->SNPTR = SNhead;
    }
 
    Mptr = MNhead;
 
    // Traverse the matrix, row-wise
    for (int i = 0; i < Mptr->Matrix.size(); i++) {
        for (int j = 0; j < Mptr->Matrix[i].size(); j++) {
            // For all non-zero values, push them in linked
            // list
            if (Matrix[i][j] != 0)
                MNhead
                    = AddInList(MNhead, i, j, Matrix[i][j]);
        }
    }
    return MNhead;
}
 
// Function to reconstruct the sparse
// matrix using linked list
void ReConstructArray(MatrixNode* MNhead)
{
    int i, j;
    SNode* Sptr = MNhead->SNPTR;
 
    // Create a 2D array
    vector<vector<int> > OriginalMatrix(
        MNhead->Matrix.size(),
        vector<int>(MNhead->Matrix[0].size()));
 
    // Initialize all the elements in the original matrix as
    // 0
    for (i = 0; i < MNhead->Matrix.size(); i++) {
        for (j = 0; j < MNhead->Matrix[i].size(); j++) {
            OriginalMatrix[i][j] = 0;
        }
    }
 
    // Print the linked list representation:
    cout << "Linked list representation:" << endl;
 
    // Iterate while sptr pointer is not NULL
    while (Sptr != NULL) {
        // Update the element in the original matrix and
        // print the current node:
        OriginalMatrix[Sptr->Row][Sptr->Col] = Sptr->data;
        cout << "(" << Sptr->Row << ", " << Sptr->Col
             << ", " << OriginalMatrix[Sptr->Row][Sptr->Col]
             << ")->";
        // Move to the next node:
        Sptr = Sptr->next;
    }
    cout << "NULL" << endl;
 
    // Print the original matrix
    cout << "Original Matrix Re-Construction:" << endl;
    for (i = 0; i < MNhead->Matrix.size(); i++) {
        for (j = 0; j < MNhead->Matrix[i].size(); j++) {
            cout << OriginalMatrix[i][j] << ", ";
        }
        cout << endl;
    }
}
 
int main()
{
    // Initialize the head pointer of the linked list
    MatrixNode* MNhead = NULL;
    SNode* SNhead = NULL;
 
    // Create the dense matrix
    vector<vector<int> > Matrix = { { 0, 1, 0, 0, 0 },
                                    { 0, 1, 0, 0, 0 },
                                    { 0, 0, 2, 0, 0 },
                                    { 0, 3, 0, 0, 4 },
                                    { 0, 0, 5, 0, 0 } };
 
    // Construct the sparse matrix
    MNhead = ConstructSparseMatrix(MNhead, Matrix, SNhead);
 
    // Reconstruct the original matrix
    ReConstructArray(MNhead);
 
    return 0;
}
 
// This code is contributed by lokeshmvs21.

C

// C program for the above approach
 
#include <stdio.h>
#include <stdlib.h>
 
// Store the size of sparse matrix
#define R 5
#define C 5
 
// Linked list node
typedef struct SNode {
    int data;
    int Col;
    int Row;
    struct SNode* next;
} SparseNode;
 
// Store the head pointer of the linked
// list and the size of the matrix
typedef struct MNode {
    int Matrix[2];
    SparseNode* SNPTR;
} MatrixNode;
 
// Function to initialize the head of
// the linked list
MatrixNode* ConstructMNhead(
    MatrixNode* MNhead, SparseNode* SNhead)
{
 
    MNhead = (MatrixNode*)malloc(sizeof(MNhead));
 
    // Update the number of rows and
    // columns and update head pointer
    MNhead->Matrix[0] = R;
    MNhead->Matrix[1] = C;
    MNhead->SNPTR = SNhead;
 
    return MNhead;
}
 
// Function to create a new node
SparseNode* CreateList(int Row, int Col,
                       int data)
{
 
    // Create a new node
    SparseNode* New
        = (SparseNode*)malloc(sizeof(SparseNode));
 
    // Update the value and the row
    // and column index and set the
    // next pointer to NULL
    New->data = data;
    New->Col = Col;
    New->Row = Row;
    New->next = NULL;
 
    return New;
}
 
// Function to insert a node at the
// beginning of the  linked list
MatrixNode* AddInList(
    MatrixNode* MNhead, int Row,
    int Col, int data)
{
    MatrixNode* Mptr = MNhead;
 
    // Create a new node
    SparseNode* New = CreateList(
        Row, Col, data);
 
    // If the head is NULL, point it
    // to the newly created node
    if (Mptr->SNPTR == NULL) {
        Mptr->SNPTR = New;
        return MNhead;
    }
 
    // Insert this node at beginning
    New->next = Mptr->SNPTR;
 
    // Update the head pointer
    Mptr->SNPTR = New;
 
    return MNhead;
}
 
// Function to construct the sparse
// matrix using linked list
MatrixNode* ConstructSparseMatrix(
    MatrixNode* MNhead, int Matrix[R][C],
    SparseNode* SNhead)
{
    int i, j;
    MatrixNode* Mptr = MNhead;
 
    // If the head pointer is NULL
    if (MNhead == NULL) {
        MNhead = ConstructMNhead(
            MNhead, SNhead);
    }
 
    Mptr = MNhead;
 
    // Traverse the matrix, row-wise
    for (i = 0;
         i < Mptr->Matrix[0]; i++) {
        for (j = 0;
             j < Mptr->Matrix[1]; j++) {
 
            // For all non-zero values,
            // push them in linked list
            if (Matrix[i][j])
                MNhead = AddInList(
                    MNhead, i, j,
                    Matrix[i][j]);
        }
    }
 
    return MNhead;
}
 
// Function to reconstruct the sparse
// matrix using linked list
void ReConstructArray(MatrixNode* MNhead)
{
    int i, j;
    SparseNode* Sptr = MNhead->SNPTR;
 
    // Create a 2D array
    int** OriginalMatrix
 
        = (int**)malloc(sizeof(int*)
                        * MNhead->Matrix[0]);
 
    for (i = 0;
         i < MNhead->Matrix[0]; i++) {
        OriginalMatrix[i]
            = (int*)malloc(sizeof(int)
                           * MNhead->Matrix[1]);
    }
 
    // Initialize all the elements
    // in the original matrix as 0
    for (i = 0;
         i < MNhead->Matrix[0]; i++) {
 
        for (j = 0;
             j < MNhead->Matrix[1]; j++) {
            OriginalMatrix[i][j] = 0;
        }
    }
 
    // Print the linked list
    printf("Linked list represe"
           "ntation:\n");
 
    // Iterate while sptr pointer is not NULL
    while (Sptr != NULL) {
 
        // Update the element in the
        // original matrix and print
        // the current node
        OriginalMatrix[Sptr->Row][Sptr->Col]
            = Sptr->data;
 
        printf("(%d, %d, %d)->",
               Sptr->Row, Sptr->Col,
               OriginalMatrix[Sptr->Row][Sptr->Col]);
 
        // Move to the next node
        Sptr = Sptr->next;
    }
    printf("NULL\n");
 
    // Print the reconstructed matrix
    printf("Original Matrix Re"
           "-Construction:\n");
 
    for (i = 0; i < R; i++) {
        for (j = 0; j < C; j++) {
            printf("%d, ", OriginalMatrix[i][j]);
        }
        printf("\n");
    }
}
 
// Create a head of the linked list
MatrixNode* MNhead = NULL;
SparseNode* SNhead = NULL;
 
// Driver Code
int main()
{
    int Matrix[R][C] = { { 0, 1, 0, 0, 0 },
                         { 0, 1, 0, 0, 0 },
                         { 0, 0, 2, 0, 0 },
                         { 0, 3, 0, 0, 4 },
                         { 0, 0, 5, 0, 0 } };
    int** OriginalMatrix;
 
    // Sparse matrix Construction
    MNhead = ConstructSparseMatrix(
        MNhead, Matrix, SNhead);
 
    // Sparse matrix Re-Construction
    ReConstructArray(MNhead);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class Main
{
   
    // Store the size of sparse matrix
    static int R = 5;
    static int C = 5;
 
    // Function to initialize the head of
    // the linked list
    public static MatrixNode
    ConstructMNhead(MatrixNode MNhead, SparseNode SNhead)
    {
        MNhead = new MatrixNode();
 
        // Update the number of rows and
        // columns and update head pointer
        MNhead.Matrix[0] = R;
        MNhead.Matrix[1] = C;
        MNhead.SNPTR = SNhead;
        return MNhead;
    }
 
    // Function to create a new node
    public static SparseNode CreateList(int Row, int Col,
                                        int data)
    {
        // Create a new node
        SparseNode New = new SparseNode();
 
        // Update the value and the row
        // and column index and set the
        // next pointer to NULL
        New.data = data;
        New.Col = Col;
        New.Row = Row;
        New.next = null;
 
        return New;
    }
 
    // Function to insert a node at the
    // beginning of the  linked list
    public static MatrixNode
    AddInList(MatrixNode MNhead, int Row, int Col, int data)
    {
        MatrixNode Mptr = MNhead;
 
        // Create a new node
        SparseNode New = CreateList(Row, Col, data);
 
        // If the head is NULL, point it to the newly
        // created node
        if (Mptr.SNPTR == null) {
            Mptr.SNPTR = New;
            return MNhead;
        }
 
        // Insert this node at beginning
        New.next = Mptr.SNPTR;
 
        // Update the head pointer
        Mptr.SNPTR = New;
 
        return MNhead;
    }
 
    // Function to construct the sparse
    // matrix using linked list
    public static MatrixNode
    ConstructSparseMatrix(MatrixNode MNhead, int[][] Matrix,
                          SparseNode SNhead)
    {
        int i, j;
        MatrixNode Mptr = MNhead;
 
        // If the head pointer is NULL
        if (MNhead == null) {
            MNhead = ConstructMNhead(MNhead, SNhead);
        }
 
        Mptr = MNhead;
 
        // Traverse the matrix, row-wise
        for (i = 0; i < Mptr.Matrix[0]; i++) {
            for (j = 0; j < Mptr.Matrix[1]; j++) {
                // For all non-zero values, push them in
                // linked list
                if (Matrix[i][j] != 0)
                    MNhead = AddInList(MNhead, i, j,
                                       Matrix[i][j]);
            }
        }
        return MNhead;
    }
 
    // Function to reconstruct the sparse
    // matrix using linked list
    public static void ReConstructArray(MatrixNode MNhead)
    {
        int i, j;
        SparseNode Sptr = MNhead.SNPTR;
 
        // Create a 2D array
        int[][] OriginalMatrix
            = new int[MNhead.Matrix[0]][MNhead.Matrix[1]];
 
        // Initialize all the elements in the original
        // matrix as 0
        for (i = 0; i < MNhead.Matrix[0]; i++) {
            for (j = 0; j < MNhead.Matrix[1]; j++) {
                OriginalMatrix[i][j] = 0;
            }
        }
 
        // Print the linked list representation:
        System.out.println("Linked list representation:");
 
        // Iterate while sptr pointer is not NULL
        while (Sptr != null) {
            // Update the element in the original matrix and
            // print the current node:
            OriginalMatrix[Sptr.Row][Sptr.Col] = Sptr.data;
            System.out.print(
                "(" + Sptr.Row + ", " + Sptr.Col + ", "
                + OriginalMatrix[Sptr.Row][Sptr.Col]
                + ")->");
            // Move to the next node:
            Sptr = Sptr.next;
        }
        System.out.println("NULL");
 
        // Print the reconstructed matrix
        System.out.println(
            "Original Matrix Re-Construction:");
 
        for (i = 0; i < R; i++) {
            for (j = 0; j < C; j++) {
                System.out.print(OriginalMatrix[i][j]
                                 + ", ");
            }
            System.out.println("");
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        // Create a head of the linked list
        MatrixNode MNhead = null;
        SparseNode SNhead = null;
 
        int[][] Matrix = { { 0, 1, 0, 0, 0 },
                           { 0, 1, 0, 0, 0 },
                           { 0, 0, 2, 0, 0 },
                           { 0, 3, 0, 0, 4 },
                           { 0, 0, 5, 0, 0 } };
        int[][] OriginalMatrix;
        // Sparse matrix Construction
        MNhead
            = ConstructSparseMatrix(MNhead, Matrix, SNhead);
        // Sparse matrix Re-Construction
        ReConstructArray(MNhead);
    }
}
 
// Linked list node
class SparseNode {
    int data;
    int Col;
    int Row;
    SparseNode next;
}
 
// Store the head pointer of the linked
// list and the size of the matrix
class MatrixNode {
    int[] Matrix = new int[2];
    SparseNode SNPTR;
}
 
// This code is contributed by Tapesh (tapeshdua420)

Python3

# python code for above approach
R = 5
C = 5
 
# linked list node
class SparseNode:
   
    # Function to initialize the node object
    def __init__(self, data, Col, Row):
        self.data = data  # Assign data
        self.Col = Col  # Assign Column
        self.Row = Row  # Assign Row
        self.next = None  # Initialize
        # next as null
 
# Store the head pointer of the linked
# list and the size of the matrix
class MatrixNode:
   
    # Function to initialize the node object
    def __init__(self, Matrix, SNPTR):
        self.Matrix = Matrix  # Initialize matrix
        self.SNPTR = None  # Initialize
        # SNPTR as null
 
# Function to initialize the head of
# the linked list
def ConstructMNhead(MNhead, SNhead):
   
    # add the number of rows and
    # columns and add head pointer
    MNhead = MatrixNode([R, C], SNhead)
    return MNhead
 
# Function to create a new node
 
 
def CreateList(Row, Col, data):
    # Create a new node
    New = SparseNode(data, Col, Row)
    return New
 
# Function to insert a node at the
# beginning of the  linked list
def AddInList(MNhead, Row, Col, data):
    Mptr = MNhead
    # Create a new node
    New = CreateList(Row, Col, data)
 
    # If the head is NULL, point it
    # to the newly created node
    if (Mptr.SNPTR == None):
        Mptr.SNPTR = New
        return MNhead
 
    # Insert this node at beginning
    New.next = Mptr.SNPTR
 
    # Update the head pointer
    Mptr.SNPTR = New
 
    return MNhead
 
# Function to construct the sparse
# matrix using linked list
def ConstructSparseMatrix(MNhead, Matrix,
                          SNhead):
    Mptr = MNhead
 
    # If the head pointer is NULL
    if (MNhead == None):
        MNhead = ConstructMNhead(
            MNhead, SNhead)
 
    Mptr = MNhead
 
    # Traverse the matrix, row-wise
    for i in range(0, Mptr.Matrix[0]):
        for j in range(0, Mptr.Matrix[1]):
 
            # For all non-zero values,
            # push them in linked list
            if (Matrix[i][j]):
                MNhead = AddInList(
                    MNhead, i, j,
                    Matrix[i][j])
 
    return MNhead
 
# Function to reconstruct the sparse
# matrix using linked list
def ReConstructArray(MNhead):
    Sptr = MNhead.SNPTR
 
    # Create a 2D array
    OriginalMatrix = []
 
    # Initialize all the elements
    # in the original matrix as 0
    for i in range(0, MNhead.Matrix[0]):
        OriginalMatrix.append([])
        for j in range(0, MNhead.Matrix[1]):
            OriginalMatrix[i].append(0)
 
    # Print the linked list
    print("Linked list represe"
          "ntation:\n")
 
    # Iterate while sptr pointer is not NULL
    while (Sptr != None):
 
        # Update the element in the
        # original matrix and print
        # the current node
        OriginalMatrix[Sptr.Row][Sptr.Col] = Sptr.data
 
        print("(", Sptr.Row, ",", Sptr.Col, ",",
              OriginalMatrix[Sptr.Row][Sptr.Col], ")->", end=" ")
 
        # Move to the next node
        Sptr = Sptr.next
    print("None\n")
 
    # Print the reconstructed matrix
    print("Original Matrix Re"
          "-Construction:\n")
 
    for i in range(0, R):
        for j in range(0, C):
            print(OriginalMatrix[i][j], end=" ")
        print("\n")
 
 
# Create a head of the linked list
 
# Driver Code
Matrix = [[0, 1, 0, 0, 0],
          [0, 1, 0, 0, 0],
          [0, 0, 2, 0, 0],
          [0, 3, 0, 0, 4],
          [0, 0, 5, 0, 0]]
 
MNhead = None
SNhead = None
# Sparse matrix Construction
MNhead = ConstructSparseMatrix(MNhead, Matrix, SNhead)
 
# Sparse matrix Re-Construction
ReConstructArray(MNhead)
 
# This code is contributed by rj13to

C#

// C# program for the above approach
using System;
 
class Program {
 
    // Store the size of sparse matrix
    static int R = 5;
    static int C = 5;
 
    // Function to initialize the head of
    // the linked list
    public static MatrixNode
    ConstructMNhead(MatrixNode MNhead, SparseNode SNhead)
    {
        MNhead = new MatrixNode();
 
        // Update the number of rows and
        // columns and update head pointer
        MNhead.Matrix[0] = R;
        MNhead.Matrix[1] = C;
        MNhead.SNPTR = SNhead;
        return MNhead;
    }
 
    // Function to create a new node
    public static SparseNode CreateList(int Row, int Col,
                                        int data)
    {
        // Create a new node
        SparseNode New = new SparseNode();
 
        // Update the value and the row
        // and column index and set the
        // next pointer to NULL
        New.data = data;
        New.Col = Col;
        New.Row = Row;
 
        return New;
    }
 
    // Function to insert a node at the
    // beginning of the  linked list
    public static MatrixNode
    AddInList(MatrixNode MNhead, int Row, int Col, int data)
    {
        MatrixNode Mptr = MNhead;
 
        // Create a new node
        SparseNode New = CreateList(Row, Col, data);
 
        // If the head is NULL, point it to the newly
        // created node
        if (Mptr.SNPTR == null) {
            Mptr.SNPTR = New;
            return MNhead;
        }
 
        // Insert this node at beginning
        New.next = Mptr.SNPTR;
 
        // Update the head pointer
        Mptr.SNPTR = New;
 
        return MNhead;
    }
 
    // Function to construct the sparse
    // matrix using linked list
    public static MatrixNode
    ConstructSparseMatrix(MatrixNode MNhead, int[, ] Matrix,
                          SparseNode SNhead)
    {
        int i, j;
        MatrixNode Mptr = MNhead;
 
        // If the head pointer is NULL
        if (MNhead == null) {
            MNhead = ConstructMNhead(MNhead, SNhead);
        }
 
        Mptr = MNhead;
 
        // Traverse the matrix, row-wise
        for (i = 0; i < Mptr.Matrix[0]; i++) {
            for (j = 0; j < Mptr.Matrix[1]; j++) {
                // For all non-zero values, push them in
                // linked list
                if (Matrix[i, j] != 0)
                    MNhead = AddInList(MNhead, i, j,
                                       Matrix[i, j]);
            }
        }
        return MNhead;
    }
 
    public static void ReConstructArray(MatrixNode MNhead)
    {
        int i, j;
        SparseNode Sptr = MNhead.SNPTR;
 
        // Create a 2D array
        int[, ] OriginalMatrix
            = new int[MNhead.Matrix[0], MNhead.Matrix[1]];
 
        // Initialize all the elements in the original
        // matrix as 0
        for (i = 0; i < MNhead.Matrix[0]; i++) {
            for (j = 0; j < MNhead.Matrix[1]; j++) {
                OriginalMatrix[i, j] = 0;
            }
        }
 
        // Print the linked list representation:
        Console.WriteLine("Linked list representation:");
 
        // Iterate while sptr pointer is not NULL
        while (Sptr != null) {
            // Update the element in the original matrix and
            // print the current node:
            OriginalMatrix[Sptr.Row, Sptr.Col] = Sptr.data;
            Console.Write(
                "(" + Sptr.Row + ", " + Sptr.Col + ", "
                + OriginalMatrix[Sptr.Row, Sptr.Col]
                + ")->");
            // Move to the next node:
            Sptr = Sptr.next;
        }
        Console.WriteLine("NULL");
 
        // Print the reconstructed matrix
        Console.WriteLine(
            "Original Matrix Re-Construction:");
 
        for (i = 0; i < R; i++) {
            for (j = 0; j < C; j++) {
                Console.Write(OriginalMatrix[i, j] + ", ");
            }
            Console.WriteLine("");
        }
    }
 
    // Driver Code
    public static void Main()
    {
        // Create a head of the linked list
        MatrixNode MNHead = null;
        SparseNode SNHead = null;
        int[, ] Matrix = new int[, ] { { 0, 1, 0, 0, 0 },
                                       { 0, 1, 0, 0, 0 },
                                       { 0, 0, 2, 0, 0 },
                                       { 0, 3, 0, 0, 4 },
                                       { 0, 0, 5, 0, 0 } };
 
        // Create a head of the linked list
        MNHead
            = ConstructSparseMatrix(MNHead, Matrix, SNHead);
        // Sparse matrix Re-Construction
        ReConstructArray(MNHead);
    }
}
 
// Linked list node
class SparseNode {
    public int data;
    public int Col;
    public int Row;
    public SparseNode next;
}
 
// Store the head pointer of the linked
// list and the size of the matrix
class MatrixNode {
    public int[] Matrix = new int[2];
    public SparseNode SNPTR;
}
 
// This code is contributed by Tapesh (tapeshdua420)

Javascript

  // JavaScript code for the above approach
  class SparseNode
  {
       
  // linked list node
  constructor(data, Col, Row) {
    this.data = data; // Assign data
    this.Col = Col; // Assign Column
    this.Row = Row; // Assign Row
    this.next = null; // Initialize next as null
  }
}
 
class MatrixNode {
  constructor(Matrix, SNPTR) {
    this.Matrix = Matrix; // Initialize matrix
    this.SNPTR = null; // Initialize SNPTR as null
  }
}
 
const R = 5;
const C = 5;
 
function ConstructMNhead(MNhead, SNhead) {
  // Function to initialize the head of the linked list
  MNhead = new MatrixNode([R, C], SNhead);
  return MNhead;
}
 
function CreateList(Row, Col, data) {
  // Function to create a new node
  const New = new SparseNode(data, Col, Row);
  return New;
}
 
function AddInList(MNhead, Row, Col, data) {
  let Mptr = MNhead;
  const New = CreateList(Row, Col, data);
 
  // Function to insert a node at the beginning of the linked list
  // If the head is NULL, point it to the newly created node
  if (Mptr.SNPTR === null) {
    Mptr.SNPTR = New;
    return MNhead;
  }
 
  // Insert this node at beginning
  New.next = Mptr.SNPTR;
 
  // Update the head pointer
  Mptr.SNPTR = New;
  return MNhead;
}
 
function ConstructSparseMatrix(MNhead, Matrix) {
  // Function to construct the sparse matrix using linked list
  let Mptr = MNhead;
 
  // If the head pointer is NULL
  if (MNhead === null) {
    MNhead = ConstructMNhead(MNhead);
  }
  Mptr = MNhead;
 
  // Traverse the matrix, row-wise
  for (let i = 0; i < Mptr.Matrix[0]; i++) {
    for (let j = 0; j < Mptr.Matrix[1]; j++) {
 
      // For all non-zero values, push them in linked list
      if (Matrix[i][j]) {
        MNhead = AddInList(MNhead, i, j, Matrix[i][j]);
      }
    }
  }
  return MNhead;
}
function ReConstructArray(MNhead) {
  let Sptr = MNhead.SNPTR;
 
  // Create a 2D array
  const OriginalMatrix = [];
 
  // Initialize all the elements in the original matrix as 0
  for (let i = 0; i < MNhead.Matrix[0]; i++) {
    OriginalMatrix.push([]);
    for (let j = 0; j < MNhead.Matrix[1]; j++) {
      OriginalMatrix[i].push(0);
    }
  }
 
  // Print the linked list representation
  console.log("Linked list representation:");
  console.log("<br>")
  // Iterate while sptr pointer is not NULL
  while (Sptr !== null)
  {
   
    // Update the element in the original matrix and print the current node
    OriginalMatrix[Sptr.Row][Sptr.Col] = Sptr.data;
    console.log(`(${Sptr.Row}, ${Sptr.Col}, ${OriginalMatrix[Sptr.Row][Sptr.Col]})->`);
 
    // Move to the next node
    Sptr = Sptr.next;
  }
  console.log("None");
  console.log("<br>")
 
  // Print the reconstructed matrix
  console.log("Original Matrix Re-Construction:");
  console.log("<br>")
  for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
      console.log(OriginalMatrix[i][j]+" ");
    }
   console.log("<br>")
  }
}
// Create a 2D matrix
const Matrix =[[0, 1, 0, 0, 0],
          [0, 1, 0, 0, 0],
          [0, 0, 2, 0, 0],
          [0, 3, 0, 0, 4],
          [0, 0, 5, 0, 0]]
 
// Create a head of the linked list
let MNhead = null;
 
// Construct the sparse matrix
MNhead = ConstructSparseMatrix(MNhead, Matrix);
 
// Re-construct the original matrix
ReConstructArray(MNhead);
 
// This code is contributed by lokeshpotta20.

Output

Linked list representation:
(4, 2, 5)->(3, 4, 4)->(3, 1, 3)->(2, 2, 2)->(1, 1, 1)->(0, 1, 1)->NULL
Original Matrix Re-Construction:
0, 1, 0, 0, 0, 
0, 1, 0, 0, 0, 
0, 0, 2, 0, 0, 
0, 3, 0, 0, 4, 
0, 0, 5, 0, 0,

Time Complexity: O(N*M)
Auxiliary Space: O(N*M)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!