Create Linked List From A Given Array

Problem Statement

In this problem, we are given an array and are asked to create a linked list from the given array. The idea is quite simple and this problem can be treated as a basic level problem for understanding how linked lists work.

Let me explain this problem with an example test case-

Sample Input

Array: arr[]={0, 2, 3, 5, 1}

Sample Output

Approach

The idea is to traverse the array from one end and for each element that we encounter we create a new node with that and insert that element into the linked list.

Algorithm

• Initially, traverse the array and for each element, create a new node for each element that we encounter.
• Each new node is inserted into the linked list
• Finally, we return the head of the created linked list.

Dry Run

Code Implementation

#include 
using namespace std;
struct Node {
    int data;
    Node* next;
};
void insert(Node** root, int item)
{
    Node* temp = new Node;
    Node* ptr;
    temp->data = item;
    temp->next = NULL;

    if (*root == NULL)
        *root = temp;
    else {
        ptr = *root;
        while (ptr->next != NULL)
            ptr = ptr->next;
        ptr->next = temp;
    }
}

void print(Node* root)
{
    while (root != NULL) {
        cout << root->data << " ";
        root = root->next;
    }
}

Node *arrayToList(int arr[], int n)
{
    Node *root = NULL;
    for (int i = 0; i < n; i++)
        insert(&root, arr[i]);
return root;
}
int main()
{
    int arr[] = { 0, 2, 3, 5, 1 };
    int n = sizeof(arr) / sizeof(arr[0]);
    Node* root = arrayToList(arr, n);
    print(root);
    return 0;
}

Output:

0->2->3->5->1

Space complexity: O(1), no extra space is used in this approach.

This blog tried to explain how easily you can create a linked list from a given array of elements and described their time and space complexities. To practice more problems on LinkedList you can check out at PrepBytes Linked List.