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
#includeusing 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.