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:
- 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.
- Create a method that will create our doubly linked list. Let us name this function createDLL[]. This function will take four arguments:
- int input[][]: the 2D matrix inputted by the user.
- int posi, int posj: two integer values that will maintain the current cell of the 2D matrix on which we are working.
- DubLL *last: pointer of struct type that will point to the last added node.
- 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.
- 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.
- Once the node is created, we check if it is a boundary element or not.
- 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.
- 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.
- 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.
- 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.
- 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.