Construct a Linked List using a 2D matrix in C++

In this tutorial, you will learn how to construct a linked list using a double-dimensional matrix in C++.

Let us have a look at the demonstration below to get the clear notion of the problem:

Example of Linked List using 2D Matrix in C++

Input : [ 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

 

Algorithm

1. Creating m linked list(m=no of rows) whose each node stores its right node. The head node pointer of each of the m linked lists are stored in an array.
2. then traversing through m lists, for every (i)th and (i+1)th list, setting down the pointers of each node of the (i)th list to its corresponding node of (i+1)th list.

 

Implementation in C++

//C++ program to construct a Linked List
//from a 2D matrix

#include<bits/stdc++.h>
using namespace std;

//struct node of linked list
struct node{
  int data;
  node *right,*down;
};


//creating a new node
node* newnode(int x)
{
  node* temp=new node;
  temp->data=x;
  temp->right=temp->down=NULL;
  return temp;
}


//printing the linked list
void print(node* head){
  node *r,*d=head;
  
  //looping till the end of list vertically
  while(d){
    r=d;
    
    //looping till the end of the list horizontally
    while(r){
      cout<<r->data<<" ";
      r=r->right;
    }
    cout<<endl;
    d=d->down;
  }
}


//func for creating linked list
node* create(int a[][3],int m,int n){
  
  //head of the linked list(initial point [0][0])
  node* start=NULL;
  
  //creating head of each row linked list
  node* head[m];
  node *righttemp, *newptr;
  
  //Creating m  linked list
  for(int i=0;i<m;i++){
    //initialising head of each row
    head[i]=NULL;
    for(int j=0;j<n;j++){
      newptr=newnode(a[i][j]);
      
      //stores a[0][0] node as the
      //starthead of linked list
      if(!start)
      start=newptr;
      
      if(!head[i])
      head[i]=newptr;
      else
      righttemp->right=newptr;
      
      righttemp=newptr;
    }
  }
  
  //setting down the pointers
  for(int i=0;i<m-1;i++)
{
    node *temp1=head[i],*temp2=head[i+1];
    while(temp1&&temp2)
{
      temp1->down=temp2;
      temp1=temp1->right;
      temp2=temp2->right;
    }
  }
  
  //return starthead pointer of the linked list
  return start;
}

//driver program
int main(){
  int m,n;
  m=3;
  n=3;
  //creating matrix
  int a[][3]={{1,2,3},
        {4,5,6},
        {7,8,9}};
  node* head=create(a,m,n);
  print(head);
}

Output

1 2 3
4 5 6
7 8 9

I hope this tutorial helps you better understand the implementation of how to create a linked list using a 2-D matrix.