Convert an array to a Linked List

Problem Statement: Given an array arr[] of size N. The task is to create a linked list from the given array and return the head of the linked list.

Examples

Example 1:
Input Format: N=3, arr[]=[0,1,2]
Result 0->1->2
Explanation: After converting the array into a linked list, the head of the linked list would be the start of the array, and thus the output will be 0.

Example 2:
Input Format: N=6, arr[]=[1,2,3,4,5,6]
Result 1->2->3->4->5->6
Explanation: Again, after converting the linked list, the head would be the first element of the array, and thus the output will be 1.

Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

Approach:

In order to convert an array to a linked list, start by defining a reference point. In this case, try to fix the start of the array, which will be the head of the linked list.

After fixing the head, iterate through the entire array, convert every element into a node of the linked List, and keep linking them.

Algorithm:

Initially, assign the 0th index element by creating a new node which will be the head of the linked list.

Once we have the head(store a reference in the mover node, this mover will always be the last node of the linked list created to date), which has the 0-th index element, the next task is to connect the next set of elements to the LinkedList. In order to do that, iterate through the entire array, and for every element, do the following:
1. Create a new node and assign the i-th index element value to it.
2. Link the previous nodes next to this new node.

Assign this node to be the mover node for the next iteration.

Code:

C++ Code

class Node{
    public:
    int data;
    Node* next;
    public:
    Node(int data1, Node* next1){
        data=data1;
        next=next1;
    }
    public:
    Node(int data1){
        data=data1;
        next=nullptr;
    }
};
Node* convertarr2LL(vector<int>& arr){
    Node* head= new Node(arr[0]); //creating head 
    Node* mover=head; //pointer pointing towards head
    for (int i=1;i<arr.size();i++){
        Node* temp=new Node(arr[i]); //creating new node every time
        mover->next=temp; //pointing mover to temp
        mover=mover->next; //moving mover to the next node
    }
    return head;
}
int main(){
    vector<int> arr={2,5,8,7};
    Node* head=convertarr2LL(arr);
    cout<<head->data<<'\n';
}

Output: 2

Time Complexity: O(N), since we are iterating over the entire array, where N is the number of elements in the array.

Space Complexity: O(1), as we have not used any extra space.

Java Code

class Node{
    int data;
    Node next;
    Node(int data1, Node next1){
        this.data=data1;
        this.next=next1;
    }
    Node(int data1){
        this.data=data1;
        this.next=null;
    }
};
public class LinkedList{
    private static Node convertarr2LL(int[] arr){
        Node head= new Node(arr[0]);
        Node mover=head;
        for (int i=1;i<arr.length;i++){
            Node temp= new Node(arr[i]);
            mover.next=temp;
            mover=mover.next;
        }
        return head;
    }
    public static void main(String[] args){
        int[] arr={2,5,8,7};
        Node head=convertarr2LL(arr);
        System.out.print(head.data);
    }
}

Output: 2

Time Complexity: O(N), since we are iterating over the entire array, where N is the number of elements in the array.

Space Complexity: O(1), as we have not used any extra space.

Python Code

class Node:
    def __init__(self, data1, next1=None):
        self.data = data1
        self.next = next1

def convert_arr_to_ll(arr):
    head = Node(arr[0])  # creating head
    mover = head  # pointer pointing towards head
    
    for i in range(1, len(arr)):
        temp = Node(arr[i])  # creating new node every time
        mover.next = temp  # pointing mover to temp
        mover = mover.next  # moving mover to the next node
    
    return head

arr = [2, 5, 8, 7]
head = convert_arr_to_ll(arr)
print(head.data)

Output: 2

Time Complexity: O(N), since we are iterating over the entire array, where N is the number of elements in the array.

Space Complexity: O(1), as we have not used any extra space.

JavaScript Code

class Node {
    constructor(data1, next1 = null) {
        this.data = data1;
        this.next = next1;
    }
}

function convertArrToLL(arr) {
    let head = new Node(arr[0]);  // creating head
    let mover = head;  // pointer pointing towards head
    
    for (let i = 1; i < arr.length; i++) {
        let temp = new Node(arr[i]);  // creating new node every time
        mover.next = temp;  // pointing mover to temp
        mover = mover.next;  // moving mover to the next node
    }
    
    return head;
}

let arr = [2, 5, 8, 7];
let head = convertArrToLL(arr);
console.log(head.data);

Output: 2

Time Complexity: O(N), since we are iterating over the entire array, where N is the number of elements in the array.

Space Complexity: O(1), as we have not used any extra space.

In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.

Special thanks to Neerav Sethi for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article