Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
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.
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

Akshat Aggarwal
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.

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

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.

• 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 nodestruct 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 = Nonedef 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 headdef 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.

• 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 nodestruct 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 = Nonedef 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 headdef 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.

• 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 nodestruct 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 = Nonedef createLinkedList(arr):    head = None    for element in reversed(arr):        temp = ListNode(element)        temp.next = head        head = temp    return headdef 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.