'Coding has over 700 languages', '67% of programming jobs aren’t in the technology industry', 'Coding is behind almost everything that is powered by electricity'
Last Updated: Dec 27, 2023
Medium

Doubly Linked List From 2D Matrix

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

In this article, we will study how to construct a Doubly-Linked list from a 2D matrix. We do this because, in a doubly-linked list, traversal is possible in both ways, that is, forward and backward. By reading this article, the reader will be able to clear their concepts about doubly-linked lists, which will help them have a good foundation in Data Structures and Algorithms.

To construct a doubly-linked list from a 2D matrix (see 2-Dimensional Array), we use recursion in our solution. Readers who want to brush up their concepts on recursion can do so by clicking Recursion (Also see Data Structures).  

Problem Statement

You are given a 2D matrix of size n*m. Construct a doubly linked list from that 2D matrix. Consider each cell of the matrix as a node. Each node must have four pointers, namely- up, down, left, and right, connecting them.

Example

INPUT:

input[3][3] = { {1, 2, 3},

                     {4, 5, 6},

                     {7, 8, 9} }

OUTPUT:

1 <-> 2 <-> 3 <-> NULL

^     ^     ^

|     |     |

v     v     v

4 <-> 5 <-> 6 <-> NULL

^     ^     ^

|     |     |

v     v     v

7 <-> 8 <-> 9 <-> NULL

^     ^     ^

|     |     |

v     v     v

NULL  NULL  NULL

Recommended: Before moving on to the solution, check out a similar Problem.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach and Explanation

Doubly-Linked lists are special linked lists in which traversal is possible in both directions, that is, forward and backward. In our case, we have to maintain four pointers that will connect each node. 

In the case of the boundary elements, we have two pointers to link, and in the case of inner elements, we have four pointers to link. So our doubly-linked list will look like this-

doubly linked list matrix

(source: Creately)

 

The double-headed arrows indicate that traversal is possible in both directions. So, to make the required doubly-linked list, we do the following steps:

  1. Create a structure or constructor with five pointer members- data, up, down, left, and right. In the constructor pass one function argument. Set the value for data with the incoming value and initialize all the pointers to NULL.
  2. Create a method that will create our doubly linked list. Let us name this function createDLL(). This function will take four arguments:
    1. int input[][]: the 2D matrix inputted by the user.
    2. int posi, int posj: two integer values that will maintain the current cell of the 2D matrix on which we are working.
    3. DubLL *last: pointer of struct type that will point to the last added node.
  3. Inside this function, recursively take one cell of the 2D matrix and convert it into a node of the linked list and create the links.
  4. To create the node, we check if the values of posi or posj are pointing to the end of the matrix or not. If yes, then we return NULL; else, we create a new node and pass the value of the 2D matrix to the node of our doubly-linked list.
  5. Once the node is created, we check if it is a boundary element or not.
    1.  If the matrix cell lies on the 0th row, i.e., its index is (0,j), it will not have any node above it. So, the value of the up pointer is set to NULL; else, it points to the last node.
    2. If the matrix cell lies on the 0th column, i.e., its index is (i,0), it will not have any node on the left side. So, the value of the left pointer is set to NULL; else, it points to the last node.
  6. For the right-side nodes, call the function createDLL recursively, increase the value of posj by one and pass it along with all the other values.
  7. For the downward node, call the function createDLL recursively, increase the value of posi by one and pass it along with all the other values.
  8. We also have a print function in the solution code that will help us see our doubly-linked list.
     

Recommended: Try to write the code first before moving to the solution code provided in the article.  

C++ implementation

#include <iostream>
using namespace std;
#define ROW 3
#define COL 3

struct DubLL {
   
    int data;
    DubLL *up;
    DubLL *down;
    DubLL *left;
    DubLL *right;

    DubLL(int val) : data(val) , up(NULL), down(NULL), left(NULL), right(NULL){}
};

DubLL *createDLL(int input[][COL], int start, int end, DubLL *last){
   
    if(start >= ROW || end >= COL){
        return NULL;
    }

    DubLL *curr = new DubLL(input[start][end]);

    if(end == 0){
        curr->left = NULL;
    }else{
        curr->left = last;
    }

    if(start == 0){
        curr->up = NULL;
    }else{
        curr->up = last;
    }

    curr->right = createDLL(input, start, end+1, curr);
    curr->down = createDLL(input, start+1, end, curr);

    return curr;
}

void printLL(DubLL *head){
    DubLL *rightpt, *downpt = head;

    while(downpt){
        rightpt = downpt;

        while (rightpt)
        {
            cout << (rightpt->data) << " <-> ";
            rightpt = rightpt->right;
        }

        cout << "NULL";
        cout<< endl << "^     ^     ^" << endl;
        cout << "|     |     |" << endl;
        cout << "v     v     v" << endl;
        downpt = downpt->down;        
    }
    cout << "NULL  NULL  NULL";
}

int main()
{
    int input[ROW][COL] =   {
                                {1, 2, 3},
                                {4, 5, 6},
                                {7, 8, 9}
                            };

    DubLL *convLL = createDLL(input, 0, 0, NULL);
    printLL(convLL);

    return 0;
}


OUTPUT

1 <-> 2 <-> 3 <-> NULL
^     ^     ^
|     |     |
v     v     v
4 <-> 5 <-> 6 <-> NULL
^     ^     ^
|     |     |
v     v     v
7 <-> 8 <-> 9 <-> NULL
^     ^     ^
|     |     |
v     v     v
NULL  NULL  NUL

Complexity Analysis

Time Complexity

In the given implementation, we traverse the whole 2D matrix to create our Doubly Linked List. Thus, the time complexity is: 

T(n) = O(n*m), where n is the number of rows and m is the number of columns.

Space Complexity

In the given implementation, no extra space is used. Thus, Space complexity = O(1) 

Also see, Rabin Karp Algorithm

Frequently Asked Questions

What are the other ways to implement the construction of a doubly-linked list from a 2D matrix?

Yes, we can iteratively create a doubly-linked list using two nested for loops. One will travel all the rows, and the other will travel all the columns.

What is the difference between a singly-linked list and a doubly-linked list? 

In a singly-linked list, traversal is possible in one direction only. Once a node is passed, we cannot go to it unless we start our traversal from the head node again. In the case of a doubly-linked list, traversal is possible in both directions as we maintain two address pointer fields. Thus, if we pass a node once, we can traverse it again from any node.

Conclusion

To summarize the article, we studied how to construct a doubly-linked list from a 2D matrix. We saw the problem statement, an example, our approach and explanation, and finally the solution code. We also covered the time and space complexities along with some FAQs.

Recommended Problems:


Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and some more Interview Experiences curated by top Industry Experts only on  Coding Ninjas Studio.

Want to ace the coding rounds of big tech companies? Try our Attempt Unlimited Online Mock Test Series to start your preparation.

Happy Coding!

Previous article
Binary Tree to Doubly Linked List
Next article
Rotate Doubly Linked List by N nodes
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass