Construct A Doubly Linked List From 2D Matrix

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

We are provided with a 2D Matrix, and we need to construct a doubly linked list with 4 pointers, namely:

  • up
  • down
  • left
  • right

Each node should be connected to its adjacent nodes using these 4 pointers.

Learn programming languages online and consider Example:

Input 2D Matrix:

12 11 10
1 2 3
6 8 9

Output Doubly Linked List:

Problem Statement Understanding

We are given a 2D Matrix with N rows and M columns. Every element at index i, j (i.e., matrix[i][j]) needs to be changed into a node, and it should be linked to all its adjacent cells using 4 pointers given to us.

  • up
  • left
  • right
  • down

For example, We are given a Matrix with 3 rows and 3 columns:
12 11 10
1 2 3
6 8 9

  • Lets take an example with element matrix[0][0] , i.e 12.

    • It only has 2 adjacent members, matrix[0][1] and matrix[1][0], i.e., 11 and 1 respectively.
    • We need to mark Node 12's right as 11. Since 11 is right adjacent to 12.
    • We need to mark Node 12's down as 1. Since 1 is lower adjacent to 12.
  • Let's take another example of the middle element matrix[1][1], i.e. 2

    • It has 4 adjacent, matrix[1][2], matrix[0][1], matrix[2][1], matrix[1][0], which are right, up, down, and left adjacent of element 2.
    • We need to mark Node 2's right as 3. Since 3 is right adjacent to 2.
    • We need to mark Node 2's up as 11. Since 11 is the up adjacent to 2.
    • We need to mark Node 2's down as 8. Since 8 is the lower adjacent to 2.
    • We need to mark Node 2's left as 1. Since 1 is the left adjacent to 2.

The Structure of Node will be:

struct Node{
    int data;   // To hold the value of the matrix

    // 4 pointers for left, right, up, down for markings.
    Node* left; 
    Node* right;
    Node* up;
    Node* down;

    Node(int x) : data(x), left(NULL), right(NULL), up(NULL), down(NULL) {}
};

Let's dive into the Approach and Algorithm now.

Approach and Algorithm

The Approach for the given problem statement is straightforward.

  • We create a new Node every time we visit an unvisited cell, starting from (0,0).
  • We change the left pointer (curr->left) and up pointer (curr->up) of our current node.
  • Recur for right pointer (curr->right) and down pointer (curr->down) of our current Node.

Implementation

#include
using namespace std;
struct Node {
    int data;   // To hold the value of the matrix

    // 4 pointers for left, right, up, down for markings.
    Node* left;
    Node* right;
    Node* up;
    Node* down;

    Node(int x) : data(x) , left(NULL) , right(NULL) , up(NULL) , down(NULL) {}
};
Node* constructDoublyLinkedList(int mat[][3], int i, int j, Node* last) {

    //Base Condition
    if (i >= 3 || j >= 3) return NULL;
    // since matrix is of dimension 3x3.

    Node* curr = new Node(mat[i][j]);

    if (j == 0) curr->left = NULL;
    else curr->left = last;

    if (i == 0) curr->up = NULL;
    else curr->up = last;

    //Recursively Calling for right and down pointers

    curr->right = constructDoublyLinkedList(mat, i, j + 1, curr);
    curr->down = constructDoublyLinkedList(mat, i + 1, j, curr);

    return curr;

}
void print(Node* head) {
    // Require 2 pointers, downptr and rightptr, for rows and columns.
    Node* downptr = head;
    Node* rightptr;
    while (downptr) {
        rightptr = downptr;
        while (rightptr) {
            cout << (rightptr->data) << " ";
            rightptr = rightptr->right;
        }
        cout << "\n";
        downptr = downptr->down;
    }
}
int main() {
    int matrix[3][3] = {{12,  11  , 10},
        {1 ,  2  ,  3},
        {6 ,  8  ,  9}
    };

    Node* newList = constructDoublyLinkedList(matrix, 0, 0, NULL);
    print(newList);

    return 0;
}

Output

12 11 10
1 2 3
6 8 9

Time Complexity: O(n*m), where n is the number of rows and m is the number of columns in the given Matrix.
Space Complexity: O(1), constant space complexity, as no extra space is used.

This blog tried to discuss the problem when we are given a 2D matrix, and we need to construct a doubly linked list out of it. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Search an element in a Linked List (Iterative and Recursive)
Next post Multiplication of two polynomials using Linked List

Leave a Reply

Your email address will not be published. Required fields are marked *