Sparse Matrix Representation in LinkedList

Matrix is with a 2-dimensional array which has row and column. A 2-dimensional array has n rows and m columns is represented as an nXm matrix.

elements in the matrix can be ZERO and NON-ZERO. if a matrix has a greater number of ZERO values compared to NON-ZERO values are then known as a sparse matrix.
{0, 2, 0} {4, 0, 6} {0, 8, 0}

An Integer value takes 2 bytes

Total space is taken by 3 X 3 matrix is 3 X 3 X 2 =18 bytes.

Where only 4 X 2 = 8 bytes are in use which has a NON-ZERO value and the rest 18 – 8 = 10 bytes are storing ZERO.

This kind of sparse matrix consumes a lot of space. hence, we store only NON-ZERO values in the memory.

saving only NON-ZERO elements in a logically designed Linked List when a NON-ZERO element is lesser than ZERO in the matrix, saves memory and computing time because logically designed data structure traverses only NON-ZERO elements.
 

package org.wesome.dsalgo;

import lombok.Data;

import java.util.Objects;

public class SparseMatrixToLinkedList {
    @Data
    static class Node {
        int row;
        int col;
        int data;
        Node next;

        public Node(int row, int col, int data) {
            this.row = row;
            this.col = col;
            this.data = data;
        }
    }

    static Node head;

    public static void insertAtTheEnd(int row, int col, int data) {
        Node tempNode = new Node(row, col, data);
        if (Objects.isNull(head)) {
            head = tempNode;
        } else {
            Node temp = head;
            while (Objects.nonNull(temp.next)) {
                temp = temp.next;
            }
            temp.next = tempNode;
        }
    }

    public static void sparseMatrixToLinkedList(int[][] arr) {
        for (int row = 0; row < arr.length; row++) {
            for (int col = 0; col < arr[row].length; col++) {
                if (!(arr[row][col] == 0)) {
                    insertAtTheEnd(row, col, arr[row][col]);
                }
            }
        }
    }

    public static void printLinkedList() {
        Node tempNode = head;
        if (Objects.isNull(tempNode)) {
            System.out.println("head is null");
        }
        while (Objects.nonNull(tempNode)) {
            System.out.println("[" + tempNode.row + "]" + "[" + tempNode.col + "]" + tempNode.data);
            tempNode = tempNode.next;
        }
    }
}

package org.wesome.dsalgo;

import org.junit.jupiter.api.Test;

import static org.wesome.dsalgo.SparseMatrixToLinkedList.printLinkedList;
import static org.wesome.dsalgo.SparseMatrixToLinkedList.sparseMatrixToLinkedList;

public class SparseMatrixToLinkedListTest {
    @Test
    void sparseMatrixToLinkedListTest1() {
        SparseMatrixToLinkedList.head = null;
        int[][] arr = new int[][]{
                {0, 2, 0},
                {4, 0, 6},
                {0, 8, 0}};
        sparseMatrixToLinkedList(arr);
        printLinkedList();
    }

    @Test
    void sparseMatrixToLinkedListTest2() {
        SparseMatrixToLinkedList.head = null;
        int[][] arr = new int[][]{
                {1, 0, 3, 0, 5},
                {6, 0, 8, 0, 10},
                {11, 0, 13, 0, 15},
                {16, 0, 18, 0, 20},
                {21, 0, 23, 0, 25}};
        sparseMatrixToLinkedList(arr);
        printLinkedList();
    }
}

plugins {
    id 'java'
    id "io.freefair.lombok" version "6.2.0"
}

group = 'org.wesome'
version = '0.0.1-SNAPSHOT'
sourceCompatibility = JavaVersion.VERSION_1_8

configurations {
    compileOnly {
        extendsFrom annotationProcessor
    }
}

repositories {
    mavenCentral()
}

dependencies {
    testImplementation 'org.junit.jupiter:junit-jupiter:5.6.2'
}

test {
    useJUnitPlatform()
}