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
Output Doubly Linked List:
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 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
#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 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
 What are two dimensional linked lists?
 What is a doubly linked list?
 Why is a doubly linked list called a Two Way list?
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.
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.
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.