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.
C++
3.5.
Java
3.6.
Python
3.7.
Javascript
3.8.
C#
3.9.
Complexity Analysis
3.9.1.
Time Complexity 
3.9.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.
C++
4.5.
Java
4.6.
Python
4.7.
Javascript
4.8.
C#
4.9.
Complexity Analysis
4.9.1.
Time Complexity 
4.9.2.
Space Complexity 
5.
Approach 3: Inserting node at the start
5.1.
Algorithm
5.2.
Dry Run
5.3.
Code
5.4.
C++
5.5.
Java
5.6.
Python
5.7.
Javascript
5.8.
C#
5.9.
Complexity Analysis
5.9.1.
Time Complexity 
5.9.2.
Space Complexity 
6.
Frequently Asked Questions
6.1.
How do you turn an array into a linked list?
6.2.
What is the array implementation of a singly linked list?
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: May 8, 2024
Easy

Create a Linked List From a given array

Author Akshat Aggarwal
4 upvotes
Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 2024 @ 01:30 PM

Introduction

Welcome to our insightful journey into the linked lists, where we explore the fascinating process of transforming arrays into linked data structures. Linked lists, a fundamental concept in computer science, offer dynamic memory allocation and efficient insertion and deletion operations. In this comprehensive blog, we delve into the intricacies of creating linked lists from given arrays, unlocking the potential for enhanced data manipulation and storage. 

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++
  • Java
  • Python
  • Javascript
  • C#

C++

// 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);
}

Java

class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public class Main {
public static void main(String[] args) {
int[] arr = {3, 1, 4, 5, 2};
ListNode head = createLinkedList(arr);
printLinkedList(head);
}

public static ListNode createLinkedList(int[] arr) {
ListNode head = null, temp = null;
for (int element : arr) {
ListNode toAdd = new ListNode(element);
if (head == null) {
head = temp = toAdd;
} else {
temp.next = toAdd;
temp = temp.next;
}
}
return head;
}

public static void printLinkedList(ListNode head) {
while (head != null) {
System.out.print(head.val);
if (head.next != null) System.out.print(" -> ");
head = head.next;
}
System.out.println();
}
}

Python

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def createLinkedList(arr):
head = temp = None
for element in arr:
toAdd = ListNode(element)
if head is None:
head = temp = toAdd
else:
temp.next = toAdd
temp = temp.next
return head

def printLinkedList(head):
while head:
print(head.val, end="")
if head.next:
print(" -> ", end="")
head = head.next
print()

arr = [3, 1, 4, 5, 2]
head = createLinkedList(arr)
printLinkedList(head)

Javascript

class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}

function createLinkedList(arr) {
let head = null, temp = null;
for (let element of arr) {
let toAdd = new ListNode(element);
if (!head) {
head = temp = toAdd;
} else {
temp.next = toAdd;
temp = temp.next;
}
}
return head;
}

function printLinkedList(head) {
while (head) {
process.stdout.write(head.val.toString());
if (head.next) process.stdout.write(" -> ");
head = head.next;
}
console.log();
}

let arr = [3, 1, 4, 5, 2];
let head = createLinkedList(arr);
printLinkedList(head);

C#

using System;

public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}

class Program {
static void Main(string[] args) {
int[] arr = {3, 1, 4, 5, 2};
ListNode head = CreateLinkedList(arr);
PrintLinkedList(head);
}

static ListNode CreateLinkedList(int[] arr) {
ListNode head = null, temp = null;
foreach (int element in arr) {
ListNode toAdd = new ListNode(element);
if (head == null) {
head = temp = toAdd;
} else {
temp.next = toAdd;
temp = temp.next;
}
}
return head;
}

static void PrintLinkedList(ListNode head) {
while (head != null) {
Console.Write(head.val);
if (head.next != null) Console.Write(" -> ");
head = head.next;
}
Console.WriteLine();
}
}

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++
  • Java
  • Python
  • Javascript
  • C#

C++

// 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);
}

Java

class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public class Main {
public static void main(String[] args) {
int[] arr = {3, 1, 4, 5, 2};
ListNode head = createLinkedList(arr);
printLinkedList(head);
}

public static ListNode createLinkedList(int[] arr) {
ListNode head = null, tail = null;
for (int element : arr) {
ListNode toAdd = new ListNode(element);
if (head == null) {
head = tail = toAdd;
} else {
tail.next = toAdd;
tail = tail.next;
}
}
return head;
}

public static void printLinkedList(ListNode head) {
while (head != null) {
System.out.print(head.val);
if (head.next != null) System.out.print(" -> ");
head = head.next;
}
System.out.println();
}
}

Python

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def createLinkedList(arr):
head = tail = None
for element in arr:
toAdd = ListNode(element)
if head is None:
head = tail = toAdd
else:
tail.next = toAdd
tail = tail.next
return head

def printLinkedList(head):
while head:
print(head.val, end="")
if head.next:
print(" -> ", end="")
head = head.next
print()

arr = [3, 1, 4, 5, 2]
head = createLinkedList(arr)
printLinkedList(head)

Javascript

class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}

function createLinkedList(arr) {
let head = null, tail = null;
for (let element of arr) {
let toAdd = new ListNode(element);
if (!head) {
head = tail = toAdd;
} else {
tail.next = toAdd;
tail = tail.next;
}
}
return head;
}

function printLinkedList(head) {
while (head) {
process.stdout.write(head.val.toString());
if (head.next) process.stdout.write(" -> ");
head = head.next;
}
console.log();
}

let arr = [3, 1, 4, 5, 2];
let head = createLinkedList(arr);
printLinkedList(head);

C#

using System;

public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}

class Program {
static void Main(string[] args) {
int[] arr = {3, 1, 4, 5, 2};
ListNode head = CreateLinkedList(arr);
PrintLinkedList(head);
}

static ListNode CreateLinkedList(int[] arr) {
ListNode head = null, tail = null;
foreach (int element in arr) {
ListNode toAdd = new ListNode(element);
if (head == null) {
head = tail = toAdd;
} else {
tail.next = toAdd;
tail = tail.next;
}
}
return head;
}

static void PrintLinkedList(ListNode head) {
while (head != null) {
Console.Write(head.val);
if (head.next != null) Console.Write(" -> ");
head = head.next;
}
Console.WriteLine();
}
}

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++
  • Java
  • Python
  • Javascript
  • C#

C++

// 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);
}

Java

class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}

public class Main {
public static void main(String[] args) {
int[] arr = {3, 1, 4, 5, 2};
ListNode head = createLinkedList(arr);
printLinkedList(head);
}

public static ListNode createLinkedList(int[] arr) {
ListNode head = null;
for (int i = arr.length - 1; i >= 0; --i) {
ListNode temp = new ListNode(arr[i]);
temp.next = head;
head = temp;
}
return head;
}

public static void printLinkedList(ListNode head) {
while (head != null) {
System.out.print(head.val);
if (head.next != null) System.out.print(" -> ");
head = head.next;
}
System.out.println();
}
}

Python

class ListNode:
def __init__(self, x):
self.val = x
self.next = None

def createLinkedList(arr):
head = None
for element in reversed(arr):
temp = ListNode(element)
temp.next = head
head = temp
return head

def printLinkedList(head):
while head:
print(head.val, end="")
if head.next:
print(" -> ", end="")
head = head.next
print()

arr = [3, 1, 4, 5, 2]
head = createLinkedList(arr)
printLinkedList(head)

Javascript

class ListNode {
constructor(val) {
this.val = val;
this.next = null;
}
}

function createLinkedList(arr) {
let head = null;
for (let i = arr.length - 1; i >= 0; --i) {
let temp = new ListNode(arr[i]);
temp.next = head;
head = temp;
}
return head;
}

function printLinkedList(head) {
while (head) {
process.stdout.write(head.val.toString());
if (head.next) process.stdout.write(" -> ");
head = head.next;
}
console.log();
}

let arr = [3, 1, 4, 5, 2];
let head = createLinkedList(arr);
printLinkedList(head);

C#

using System;

public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}

class Program {
static void Main(string[] args) {
int[] arr = {3, 1, 4, 5, 2};
ListNode head = CreateLinkedList(arr);
PrintLinkedList(head);
}

static ListNode CreateLinkedList(int[] arr) {
ListNode head = null;
for (int i = arr.Length - 1; i >= 0; --i) {
ListNode temp = new ListNode(arr[i]);
temp.next = head;
head = temp;
}
return head;
}

static void PrintLinkedList(ListNode head) {
while (head != null) {
Console.Write(head.val);
if (head.next != null) Console.Write(" -> ");
head = head.next;
}
Console.WriteLine();
}
}

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

How do you turn an array into a linked list?

To turn an array into a linked list, iterate through the array elements, create a node for each element, and link them sequentially.

What is the array implementation of a singly linked list?

The array implementation of a singly linked list uses an array to store elements and pointers to represent node connections.

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!

Live masterclass