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
- 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.
- 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.
can you show implementation for same in C language.