Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
3.
Approach 1: Inserting node at the end
3.1.
Algorithm
3.2.
Dry Run
3.3.
Code
3.4.
Complexity Analysis
3.4.1.
Time Complexity 
3.4.2.
Space Complexity 
4.
Approach 2: Inserting node at the end using the tail pointer
4.1.
Algorithm
4.2.
Dry Run
4.3.
Code
4.4.
Complexity Analysis
4.4.1.
Time Complexity 
4.4.2.
Space Complexity 
5.
Approach 3: Inserting node at the start
5.1.
Algorithm
5.2.
Dry Run
5.3.
Code
5.4.
Complexity Analysis
5.4.1.
Time Complexity 
5.4.2.
Space Complexity 
6.
Frequently Asked Questions
6.1.
What is a Linked List?
6.2.
How many types of linked lists are there?
6.3.
Why is a linked list different from an array?
6.4.
What is the advantage of a linked list over an array?
6.5.
Compare memory needed to store an array of n elements versus a linked list of n elements.
7.
Conclusion
Last Updated: Mar 27, 2024
Easy

Create a Linked List From a given array

Author Akshat Aggarwal
4 upvotes
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

Introduction

There are times when we prefer a linked list over an array because it is quicker to add and remove from a linked list than from an array, and it does not have a fixed size, unlike an array. So, it is necessary to know how to create a linked list from an array as it has more real-world implementations. 

 

Introduction

 

So, without further ado, let’s jump into the problem statement.

Problem statement

You are given an array nums[] of length n. The task is to create a linked list from the given array.

Example

Input

n = 5
nums[] = {3, 1, 4, 5, 2};

 

Output

Output
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach 1: Inserting node at the end

The main idea of the approach is to traverse the array from the start and insert each element at the end of the linked list.

Let’s see the algorithm step-by-step:

Algorithm

  1. Traverse the array and allocate memory for the new node for each element.
  2. Find the last node of the linked list.
  3. Add the new node after the last node.

Dry Run

Let’s dry-run the algorithm for the array [3, 1, 4, 5, 2] and look at the resultant linked list after adding each element.

 

Dry Run for Algorithm 1

Code

// C++ Program to Create Linked List from the given array - Approach 1
#include <bits/stdc++.h>
using namespace std;

// Representation of a Linked List's node
struct ListNode {
   int val;
   ListNode* next;
   ListNode(int x) : val(x), next(nullptr) {}
};

// Function to insert an element at the end of a Linked List - O(n)
void insertAtEnd(ListNode*& head, int element) {
   ListNode *toAdd = new ListNode(element), *temp = head;
   if (temp == nullptr) {
       // If empty list, assign the new node to head
       head = temp = toAdd;
   } else {
       // Otherwise, go to the last node and add the new node after it
       while (temp->next != nullptr) {
           temp = temp->next;
       }
       temp->next = toAdd;
   }
}

ListNode* createLinkedList(int arr[], int size) {
   ListNode* head = nullptr;
   for (int i = 0; i < size; ++i) {
       insertAtEnd(head, arr[i]);
   }
   return head;
}

void printLinkedList(ListNode* head) {
   ListNode* temp = head;
   while (temp) {
       cout << temp->val;
       if (temp->next) cout << " -> ";
       temp = temp->next;
   }
   cout << endl;
}

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

   // Converting the given array to a Linked List
   ListNode* head = createLinkedList(arr, size);

   // Printing the Linked List
   printLinkedList(head);
}

 

Output:

3 -> 1 -> 4 -> 5 -> 2

Complexity Analysis

Time Complexity 

The algorithm’s time complexity is O(n^2) in the worst case, where n is the size of the given array because we have to insert n elements into the linked list, and for each insertion, we need to reach the last node of the linked list which takes linear time.

Space Complexity 

The algorithm’s space complexity is O(n) because we allocate memory for each node.

Also read - Merge sort in linked list

Approach 2: Inserting node at the end using the tail pointer

The main idea of the approach is to traverse the array from the start and insert each element at the end of the linked list using the tail pointer.

The tail pointer is a pointer that always points to the end of a linked list.

Let’s see the algorithm step-by-step:

Algorithm

  1. Traverse the array and allocate memory for the new node for each element.
  2. If the list is currently empty, assign the new node as the head and tail of the list. Otherwise, insert the new node after the tail pointer and update the tail pointer to the new node.

Dry Run

Let’s dry-run the algorithm for the array [3, 1, 4, 5, 2] and look at the resultant linked list after adding each element.

Dry Run for Algorithm 2

Code

// C++ Program to Create Linked List from the given array - Approach 2
#include <bits/stdc++.h>
using namespace std;

// Representation of a Linked List's node
struct ListNode {
   int val;
   ListNode* next;
   ListNode(int x) : val(x), next(nullptr) {}
};

// Function to insert an element at the end of a Linked List using the tail pointer - O(1)
void insertAtEnd(ListNode*& head, ListNode*& tail, int element) {
   ListNode* toAdd = new ListNode(element);
   if (head == nullptr) {
       // If the list is empty, assign the new node to the head as well as the tail
       head = tail = toAdd;
   } else {
       // Otherwise, add the node after the tail pointer
       tail->next = toAdd;
       tail = tail->next;
   }
}

ListNode* createLinkedList(int arr[], int size) {
   ListNode *head = nullptr, *tail = nullptr;
   for (int i = 0; i < size; ++i) {
       insertAtEnd(head, tail, arr[i]);
   }
   return head;
}

void printLinkedList(ListNode* head) {
   ListNode* temp = head;
   while (temp) {
       cout << temp->val;
       if (temp->next) cout << " -> ";
       temp = temp->next;
   }
   cout << endl;
}

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

   // Converting the given array to a Linked List
   ListNode* head = createLinkedList(arr, size);

   // Printing the Linked List
   printLinkedList(head);
}

 

Output:

3 -> 1 -> 4 -> 5 -> 2

Complexity Analysis

Time Complexity 

The algorithm’s time complexity is O(n) in the worst case, where n is the size of the given array because we have to insert n elements into the linked list, and each insertion takes constant (O(1)) time.

Space Complexity 

The algorithm’s space complexity is O(n) because we allocate memory for each node.

Approach 3: Inserting node at the start

The main idea of the approach is to traverse the array from the end and insert each element at the start of the linked list.

Let’s see the algorithm step-by-step:

Algorithm

  1. Traverse the array from the end, and for each element, allocate memory for the new node.
  2. Add the new node in the front of the current linked list. We do this by assigning the head of the current linked list to the next of the new node. Then, we change the head of the linked list to the new node.

Dry Run

Let’s dry-run the algorithm for the array [3, 1, 4, 5, 2] and look at the resultant linked list after adding each element.

 

Dry Run for algorithm 3

Code

// C++ Program to Create Linked List from the given array - Approach 3
#include <bits/stdc++.h>
using namespace std;

// Representation of a Linked List's node
struct ListNode {
   int val;
   ListNode* next;
   ListNode(int x) : val(x), next(nullptr) {}
};

// Function to insert an element at the start of a Linked List - O(1)
void insertAtStart(ListNode*& head, int element) {
   ListNode* temp = new ListNode(element);
   // Add remaining list to the end of new node
   temp->next = head;
   // Assign the first node as head again
   head = temp;
}

ListNode* createLinkedList(int arr[], int size) {
   ListNode* head = nullptr;
   // Insert elements in reverse order at the start of Linked List
   for (int i = size - 1; i >= 0; --i) {
       insertAtStart(head, arr[i]);
   }
   return head;
}

void printLinkedList(ListNode* head) {
   ListNode* temp = head;
   while (temp) {
       cout << temp->val;
       if (temp->next) cout << " -> ";
       temp = temp->next;
   }
   cout << endl;
}

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

   // Converting the given array to a Linked List
   ListNode* head = createLinkedList(arr, size);

   // Printing the Linked List
   printLinkedList(head);
}

 

Output:

3 -> 1 -> 4 -> 5 -> 2

Complexity Analysis

Time Complexity 

In the worst case, the algorithm's time complexity is O(n), where n is the size of the given array because we have to insert n elements into the linked list, and each insertion takes constant (O(1)) time.

Space Complexity 

The algorithm’s space complexity is O(n) because we allocate memory for each node.

Frequently Asked Questions

What is a Linked List?

A linked list is a dynamic data structure where each element (called a node) comprises 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.

How many types of linked lists are there?

Various types of linked lists are as follows: Singly linked lists, Doubly linked lists, Circular linked lists, and Doubly circular linked lists.

Why is a linked list different from an array?

Arrays store elements in contiguous memory locations, thus allowing random access using the index. Linked lists may keep elements in non-contiguous memory locations, and an element can only be accessed sequentially using its address from the previous element.

What is the advantage of a linked list over an array?

A linked list is a dynamic data structure, so we don’t need to specify the size of the linked list while declaring. In contrast, an array is a static data structure with a fixed length. Also, Inserting and deleting elements in the linked list is faster than in an array.

Compare memory needed to store an array of n elements versus a linked list of n elements.

The memory required to store a linked list is more than that of an array because linked lists also use memory to store the addresses of the next nodes.

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. 

Refer to this short video to brush up on your knowledge of linked lists.

 

Check out the Coding Ninjas Studio library to better understand the Data Structures and algorithms.

Recommended Reading:


Check out The Interview guide for Product Based Companies and some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc., on Coding Ninjas Studio.

To study more about Linked Lists, refer to Applications Of Linked Lists.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMSand System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy learning!

By Akshat

 

Previous article
Applications Of Linked List Data Structure
Next article
Advantages and Disadvantages of Linked List
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass