Data structures & algorithms (Beginner to Intermediate)

Free guided path13 chapters99+ problems

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.

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

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

Traverse the array and allocate memory for the new node for each element.

Find the last node of the linked list.

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.

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.

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

Traverse the array and allocate memory for the new node for each element.

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.

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

Traverse the array from the end, and for each element, allocate memory for the new node.

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.

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.