Create a Linked List From a given array

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

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

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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

You can also try this code with Online Javascript Compiler

Run Code

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.

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

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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

You can also try this code with Online Javascript Compiler

Run Code

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

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

You can also try this code with Online C++ Compiler

Run Code

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

You can also try this code with Online Java Compiler

Run Code

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)

You can also try this code with Online Python Compiler

Run Code

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

You can also try this code with Online Javascript Compiler

Run Code

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.