2D matrix using linked list in C++

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 DSA.

To construct a doubly-linked list from a 2D matrix, we use recursion in our solution. Readers who want to brush up their concepts on recursion can do so by clickingRecursion.

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

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-

(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 usingnamespacestd; #define ROW3 #define COL3 structDubLL { intdata; DubLL *up; DubLL *down; DubLL *left; DubLL *right; DubLL(intval) :data(val) ,up(NULL),down(NULL),left(NULL),right(NULL){} }; DubLL*createDLL(intinput[][COL],intstart,intend,DubLL*last){ if(start >=ROW ||end >=COL){ returnNULL; } DubLL *curr =newDubLL(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); returncurr; } voidprintLL(DubLL*head){ DubLL *rightpt, *downpt =head; while(downpt){ rightpt =downpt; while (rightpt) { cout<< (rightpt->data)<<" <-> "; rightpt =rightpt->right; } cout<<"NULL"; cout<down; } cout<<"NULL NULL NULL"; } intmain() { intinput[ROW][COL] = { {1,2,3}, {4,5,6}, {7,8,9} }; DubLL *convLL =createDLL(input,0,0,NULL); printLL(convLL); return0; }

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

Complexities

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)

Frequently Asked Questions

1. What are the other ways to implement the construction of a doubly-linked list from a 2D matrix?
   Ans.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.
2. What is the difference between a singly-linked list and a doubly-linked list?
   Ans. 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.

Key Takeaways

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

Confident about Doubly-Linked List construction? Practice this questionConvert A Given Binary Tree To Doubly Linked List on ourCodeStudio.

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

Happy Coding!