# Construct A Doubly Linked List From 2D Matrix

This blog will help in understanding how to construct a doubly linked list from a 2d matrix. Data Structures like linked lists play an important role in the technical interviews of many companies. Let’s discuss how to construct a 2d doubly linked list.

## How To Construct 2D Doubly Linked List

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 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 , i.e 12.

• It only has 2 adjacent members, matrix and matrix, 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, i.e. 2

• It has 4 adjacent, matrix, matrix, matrix, matrix, 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 To Construct 2D Doubly Linked List

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 To Construct 2D Doubly Linked List

```#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[], 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;

}
// Require 2 pointers, downptr and rightptr, for rows and columns.
Node* rightptr;
while (downptr) {
rightptr = downptr;
while (rightptr) {
cout << (rightptr->data) << " ";
rightptr = rightptr->right;
}
cout << "\n";
downptr = downptr->down;
}
}
int main() {
int matrix = {{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 To Construct 2D Doubly Linked List: O(n*m), where n is the number of rows and m is the number of columns in the given Matrix.
Space Complexity To Construct 2D Doubly Linked List: O(1), constant space complexity, as no extra space is used.

This blog has discussed the problem of constructing a 2d doubly linked list. Creating doubly linked list from 2D matrix will make your data structures strong which will always help in the interviews, you can follow this link Linked List.

## FAQs

1. What are two dimensional linked lists?
2. A linked list is a dynamic data structure where each element (called a node) is made up of two items: the data and a reference (or pointer), which points to the next node.

3. What is a doubly linked list?
4. In computer science, a doubly linked list is a linked data structure that consists of a set of sequentially linked records called nodes. Each node contains three fields: two link fields (references to the previous and to the next node in the sequence of nodes) and one data field.

5. Why is a doubly linked list called a Two Way list?
6. A doubly linked list contains a pointer to the next node as well as the previous node. This ensures that the list can be traversed in both directions.