Construct a Linked List from a 2D Matrix

Approach

To create a linked list from a 2D matrix, we create a node for each cell of the matrix with two pointers, right and down, to attach to its adjacent elements.

We start by creating m-linked lists, where m is the number of rows in the matrix, and store their head pointers in an array of nodes. Then we traverse each matrix row and initialise the head pointers to NULL.

Next, we loop through the columns of the matrix and create a new node for each element. If we are at the first row column, we store the node's address in the corresponding linked list's head pointer. Otherwise, we attach the node to the right of the previous node using the right pointer.

After we have created all nodes and attached them to their right elements, we loop through the head pointers again and connect the corresponding nodes of each ith linked list to its (i+1)th linked list using the down pointers.

Finally, we return the head pointer of the first linked list in the array.

Algorithm

• First, we need to create an array of node pointers called "head". The size of this array should be equal to the number of rows in the matrix. We then initialize each element of the "head" array to NULL.
   
• Next, we can loop through each row in the matrix. For each element in a row, we can create a new node with a value equal to the element's value.

• If the corresponding element in the "head" array is NULL, we set it to the address of the newly created node. This will be the first node of the linked list for that row.

• If the corresponding element in the "head" array is not NULL, we connect the current node to the previous node in the linked list using the "right" pointer. We then update the "right" pointer of the previous node to point to the current node.

• We can store the address of the current node in a temporary pointer called "righttemp". This will allow us to connect the "down" pointer of each node to the corresponding node in the next row.

• Once we have created the linked list for each row, we can loop through the "head" array again. For each linked list, we can connect the "down" pointer of each node in the "ith" linked list to the corresponding node in the "(i+1)th" linked list. This will create a linked list that represents the 2D matrix.

Dry Run

Let's say we have the following 2D matrix:

• We create nodes for each cell of the matrix and attach them using the right and down pointers.

• We start by creating a node for the first cell (1) and store its address in head[0].

• Then we create nodes for the remaining cells and attach them to their right and down elements.

• Each node stores its right node, and the head pointers of each m linked list are stored in an array of nodes.

• Finally, we set the down pointers of each node of the ith list to its corresponding node of the (i+1)th list.

C++ Implementation

#include <iostream>
#include <vector>

using namespace std;

// Define a class for a node in a linked list.
class Node {
public:
    int data;            // The data value stored in the node.
    Node* right;         // Pointer to the next node in the same row.
    Node* down;          // Pointer to the next node in the same column.


    // Constructor for creating a new node.
    Node(int value) {
        data = value;
        right = nullptr;
        down = nullptr;
    }
};


// Function to convert a 2D matrix into a linked list.
Node* convertMatrixToList(vector<vector<int>> matrix, int numRows, int numCols) {
    Node* head[numRows];
    Node* rightTemp;
    Node* newNode;


    // Create a linked list for each row.
    for (int i = 0; i < numRows; i++) {
        head[i] = nullptr;
        for (int j = 0; j < numCols; j++) {
            // Create a new node with the data from the matrix.
            newNode = new Node(matrix[i][j]);

            if (!head[i])
                head[i] = newNode;
            else
                rightTemp->right = newNode;


            rightTemp = newNode;
        }
    }


    // Connect each node to the node below it.
    for (int i = 0; i < numRows - 1; i++) {
        Node* firstTemp = head[i];
        Node* secondTemp = head[i + 1];


        while (firstTemp && secondTemp) {
            firstTemp->down = secondTemp;
            firstTemp = firstTemp->right;
            secondTemp = secondTemp->right;
        }
    }


    return head[0];
}


// Function to print the linked list.
void printList(Node* head) {
    Node* rightPtr;
    Node* downPtr = head;


    while (downPtr) {
        rightPtr = downPtr;
        while (rightPtr) {
            cout << rightPtr->data << " ";
            rightPtr = rightPtr->right;
        }
        cout << "\n";
        downPtr = downPtr->down;
    }
}


// Main function.
int main() {
    vector<vector<int>> matrix{
        {5, 2, 7},
        {8, 9, 3},
        {4, 8, 1}
    };


    int numRows = 3, numCols = 3;
    Node* head = convertMatrixToList(matrix, numRows, numCols);
    printList(head);


    return 0;
}

Output

5 2 7 
8 9 3 
4 8 1 

Java Implementation

import java.util.*;

class Node {
    public int data;
    public Node right; // points to the node to its right
    public Node down; // points to the node below it

    public Node(int x) {
        data = x;
        right = null;
        down = null;
    }
}

public class Solution {
    public static Node convertOLinkedList(List<List<Integer>> mat, int numRows, int numCols) {
        // array of node pointer to store starting address of each row
        Node[] head = new Node[numRows];
        Node right_temp = null, new_node;

        // create m linked lists for each row
        for (int i = 0; i < numRows; i++) {
            // initialize head[i] with NULL
            head[i] = null;
            for (int j = 0; j < numCols; j++) {
                // create a new node
                new_node = new Node(mat.get(i).get(j));

                if (head[i] == null) { // head[i] == NULL i.e we are in first column of the matrix so we need
                    head[i] = new_node;
                } else {
                    right_temp.right = new_node; // attach node to right node
                }

                right_temp = new_node;
            }
        }

        // For every ith row's list set corresponding down pointers to (i+1)th list's node
        for (int i = 0; i < numRows - 1; i++) {
            Node first_tmp = head[i];
            Node second_tmp = head[i + 1];

            while (first_tmp != null && second_tmp != null) {
                first_tmp.down = second_tmp;
                first_tmp = first_tmp.right;
                second_tmp = second_tmp.right;
            }
        }

        // return the main head pointer of the newly created list
        return head[0];
    }

    public static void print(Node head) {
        Node right_ptr;
        Node down_ptr = head;

        // iterate till down pointer is not NULL
        while (down_ptr != null) {
            right_ptr = down_ptr;
            // iterate till right pointer is not NULL
            while (right_ptr != null) {
                System.out.print(right_ptr.data + " ");
                right_ptr = right_ptr.right;
            }
            System.out.println();
            down_ptr = down_ptr.down;
        }
    }

    public static void main(String[] args) {
        // 2D matrix
        List<List<Integer>> mat = new ArrayList<>();
        mat.add(Arrays.asList(5, 2, 7));
        mat.add(Arrays.asList(8, 9, 3));
        mat.add(Arrays.asList(4, 8, 1));

        int row = 3, col = 3;
        Node head = convertOLinkedList(mat, row, col);
        print(head);
    }
}

Output

5 2 7 
8 9 3 
4 8 1 

Complexity analysis

Time Complexity

O(m*n): where n is columns and m is rows.

Reason: The above code iterates over each element in the matrix exactly once to create the linked list. It creates a new node for each element and attaches it to the right of the previous node in the same row. For the first node in each row, it sets the head of the row to the new node.

After creating the linked lists for each row, it sets the down pointers for each node to point to the corresponding node in the next row. It does this by iterating over the rows, and for each pair of nodes (one in the current row and one in the next row), it sets the down pointer of the current node to point to the next node. Therefore, the overall time complexity is O(mn) for creating the linked list. 

Space Complexity

O(m * n): where n is columns and m is rows.

Reason: Each element in the matrix is converted into a new node in the linked list, so the total number of nodes created is m * n. Therefore, the overall space complexity is O(m * n) for creating the linked list.

Frequently Asked Questions

What is a linked list?

A linked list is a dynamic data structure consisting of nodes. Each node in a linked list is composed of two items: the node's data and a reference (or pointer) to the next node in the list. The nodes in a linked list are connected through their pointers, creating a collection of connected nodes.

How is a linked list constructed from a 2D matrix?

The code constructs a linked list by creating a new node for each element in the matrix and linking the nodes horizontally and vertically to form a grid of nodes.

What is the purpose of the node class in this code?

The node class defines the structure of each node in the linked list. Each node contains a data value and two pointers - right and down - that point to the next node in the horizontal and vertical directions, respectively.

How is the head pointer of the linked list determined in this code?

The head pointer of the linked list is the first node of the first row of the matrix. This is stored in the head[0] array element.

What is a 2D matrix, and how is it related to a linked list?

A 2D matrix is a collection of elements arranged in a rectangular grid of rows and columns. In this code, a linked list is constructed where each row of the matrix corresponds to a linked list.

Conclusion

In this article, we discussed the process of creating a linked list from a 2D matrix. Also we have discussed the approach and algorithm. Proficiency in linked lists can be a significant advantage in a coding interview.

Check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 
 

Happy learning!