Doubly Linked List From 2D Matrix

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-

(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;
}

You can also try this code with Online C++ Compiler

Run Code

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:

• Convert A Given Binary Tree To Doubly Linked List 
• Largest Rectangle in a Matrix 
• Boundary Traversal of Binary Tree

Recommended Readings:

• Implementing  Linked List in Java using Class
• Advantages and Limitations of Linked Lists
• Difference Between Singly Linked List and Doubly Linked List
• Linked List From an Array

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!