# Construct a Linked List from a 2D Matrix

## Introduction

The linked list is one of the most important concepts and data structures to learn.

This problem of constructing a linked list from a 2D matrix will cover a basic understanding of the linked list.

## Problem Statement

Given a 2D matrix, construct a linked list from the matrix. So, we need to represent the 2D matrix as a linked list.

## Method

We need to create a node for each cell of the matrix and then attach it to its right and down elements using the right and down pointers of the node, respectively.

So, we need to construct a linked list in which each node will have two pointers named right and down.

When we reach the boundary of the matrix, point to a NULL pointer.

The idea is to create m linked lists ( where m is the number of rows in the matrix) whose each node stores its right node. The head pointers of each m linked list are stored in an array of nodes.

Then, traverse m lists, for every ith and (i+1)th list, set the down pointers of each node of ith list to its corresponding node of (i+1)th list.

Algorithm

- Create an array of node pointers (say head) of size equal to the number of rows(m) in the 2D matrix.
- At first, traverse through all the rows of the matrix, and inside this for loop initialize the
**head[i]**to NULL. - Create a nested for loop to traverse the column elements of the matrix and, while traversing, create new nodes having a value equal to the value at the corresponding position in the given matrix and then check if
**head[i]**is NULL or not.- If
**head[i]**is NULL, then we are at the first column, so we need to store the address of the newly created node in the**head[i]**.

- If

- If
**head[i]**is not NULL, we will connect the current node in the ith linked list using the right pointer.

- Then store the address of this node in the
**righttemp**node pointer so that we can connect the new node after this node further.

- After the above nested for loops, we need to loop through the head pointers' array again and connect down pointers of the corresponding ith linked list to (i+1)th linked list.
- Return
**head[0]**, as it would contain the address of the first node of the newly created linked list.

// function to convert the 2D matrix to linked listnode* constructMatrixtoLL(vector<vector<int>> mat, int n, int m) { // array of node pointer to store starting address of each row node* head[m]; node *righttemp, *newptr; // create m linked lists for each rowfor (int i = 0; i < m; i++) { // initialize head[i] with NULLhead[i] = NULL; for (int j = 0; j < n; j++) { // create a new nodenewptr = new node(mat[i][j]); if (!head[i]) // head[i]==NULL i.e we are in first column of the matrix so we need// to store the address of first node of each rowhead[i] = newptr; else righttemp->right = newptr; // attach node to right noderighttemp = newptr; } } // For every ith row's list set corresponding down pointers// to (i+1)th list's node for (int i = 0; i < n - 1; i++) { node *temp1 = head[i], *temp2 = head[i + 1]; while (temp1 && temp2) { temp1->down = temp2; temp1 = temp1->right; temp2 = temp2->right; } } // return the main head pointer of the newly created listreturn head[0]; } |

## Code

// C++ code for constructing a linked list from a 2D matrix #include <bits/stdc++.h> using namespace std; class node { public: int data; node* right, *down; node(int x){ data = x; right = NULL; down = NULL; } }; // function to convert the 2D matrix to linked list node* constructMatrixtoLL(vector<vector<int>> mat, int n, int m) { // array of node pointer to store starting address of each row node* head[m]; node *righttemp, *newptr; // create m linked lists for each row for (int i = 0; i < m; i++) { // initialize head[i] with NULL head[i] = NULL; for (int j = 0; j < n; j++) { // create a new node newptr = new node(mat[i][j]); if (!head[i]) // head[i]==NULL i.e we are in first column of the matrix so we need // to store the address of first node of each row head[i] = newptr; else righttemp->right = newptr;// attach node to right node righttemp = newptr; } } // For every ith row's list set corresponding down pointers // to (i+1)th list's node for (int i = 0; i < n - 1; i++) { node *temp1 = head[i], *temp2 = head[i + 1]; while (temp1 && temp2) { temp1->down = temp2; temp1 = temp1->right; temp2 = temp2->right; } } // return the main head pointer of the newly created list return head[0]; } void print(node* head) { // pointer that will move rightwards node* Rp; // pointer that will move downwards node* Dp = head; // iterate till down pointer is not NULL while (Dp) { Rp = Dp; // iterate till right pointer is not NULL while (Rp) { cout << Rp->data << " "; Rp = Rp->right; } cout << "\n"; Dp = Dp->down; } } // driver code int main() { // 2D matrix vector<vector<int>> mat{ { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } }; int row = 3, col = 3; node* head = constructMatrixtoLL(mat, row, col); print(head); return 0; } |

Output

1 2 3 4 5 6 7 8 9 |

## Complexity analysis

The time complexity of the above algorithm is O(m*n) in the worst case where m is no. of rows in the matrix and n is the number of columns.

Space complexity is also O(m*n) as we are creating m*n number of nodes.

## FAQs

**1). What is linked list?**

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. A linked list is a collection of nodes where each node is connected to the next node through its pointer.

**2). How many types of linked lists are there?**

There are mainly four types of linked lists.

- Singly linked list
- Doubly linked list
- Circular linked list
- Doubly Circular linked list

## Key Takeaways

This article covered how to construct a linked list from a 2D matrix. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Check out the CodeStudio __library__ for getting a better hold of the data structures and algorithms.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in __CodeStudio__. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here.

Happy learning!

Comments

## No comments yet

## Be the first to share what you think