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

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

#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 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?

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.


2. What is a doubly linked list?

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.


3. Why is a doubly linked list called a Two Way list?

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.