Create Linked List From A Given Array

Introduction

Sometimes, we prefer a linked list over an array as insertion and deletion of elements in the linked list is faster than array, and we need not define the linked list’s size unlike, an array. So, it is necessary to know how we can create a linked list from an array as it has more real-world implementations. Before we get started on this, let's brush up our knowledge of linked lists with this short video.

Problem statement

You are given an array. Create a linked list from the given array. 

Input: arr[]={7,4,3,2,5}

Output:7->4->3->2->5

Note: Please try to solve the problem first and then see the solution below.

Approaches

There are mainly two methods that can be used to create a linked list from an array.

Method 1

In this approach, we will insert a new node at the end of the linked list for each element of the array.

• First, allocate memory for  the new node
• Then find the last node of the linked list
• add the new node after the last node

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

struct node{
	int data;
	node* next;

};

//function for inserting a new node at the end
void insert_end(node** head,int value)
{
	//allocate memory for new node

	node* new_node= new node;
	new_node->data=value;
	new_node->next=NULL;

	//finding the last node 
	if(*head==NULL)
	{
		*head=new_node;
	}
	else{
		node* tmp=*head;

		while(tmp->next!=NULL)
		{
			tmp=tmp->next;
		}
		// adding the new node after the last node
		tmp->next=new_node;
	}
}

//function for printing the linked list

void print(node* head) 
{
	while(head->next!=NULL)
	{

		cout<<head->data<<"->";
		head=head->next;
	}

	cout<<head->data;

}

int main()
{
	int arr[]={7,4,3,2,5};

	node* head=NULL;

	for(int i=0;i<5;i++)
	{
		insert_end(&head,arr[i]);
	}

	print(head);
}

Output

The above approach takes O( n²) time in the worst case where n is the size of the given array. We need to traverse the whole linked list, every time we are adding a new node in the linked list.

Method 2

In this approach, we will start iterating the given array from the end and add the new node in front of the last added node(i.e., at the beginning of the linked list).

• First, allocate memory for  the new node
• add the new node in front of the last added node(head)

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

struct node {
	int data;
	node* next;

};


//function for inserting a new node at the beginning 
void insert_front(node** head,int value) {
	//allocate memory for new node

	node* new_node= new node;
	new_node->data=value;

	// adding new node at the beginning
	new_node->next=*head;

	*head=new_node;
}



//function for printing the linked list
void print(node* head) 
{
	while(head->next!=NULL) {

		cout<<head->data<<"->";
		head=head->next;
	}

	cout<<head->data;

}

//driver code
int main() {
	int arr[]={7,4,3,2,5};

	node* head=NULL;

	for(int i=4;i>=0;i--) {
		insert_front(&head,arr[i]);
	}

	print(head);
}

Output

The above approach takes O(n) time in the worst case where n is the size of the given array. So, it is an optimized approach for creating a linked list from a given array.

For both methods, space complexity is O(n) as we are allocating memory for each node.

Frequently Asked Questions

1). What is a 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

3). What is the advantage of linked lists over array?

• We don’t need to specify the size of the linked list while declaration. So it is a dynamic data structure, but an array is a static data structure with a fixed length.
•  Insertion and deletion of elements in the linked list are faster than array.

Conclusion

This article covered how to create a linked list from a given array. 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!