Create Linked List From A Given Array

Sometimes, we prefer a linked list over arrays as a linked list provides insertion and deletion operations faster as compared to arrays. Also, we need not define the size of the linked list, unlike arrays, therefore, we will see create linked list from array in this article, let’s have a look into the problem statement and try to understand it clearly.

Problem Statement of create linked list from array

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 regarding create linked list from a given array

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 to convert array to linked list

• 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 create linked list from array

Code Implementation to create linked list from array

#include<stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node* next;
};
void insert(struct Node** root, int item)
{
   struct Node* temp = (struct Node*) malloc(sizeof(struct Node));
    struct 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(struct Node* root)
{
    while (root != NULL) {
        printf("%d->", root->data);
        root = root->next;
    }
}
struct Node *arrayToList(int arr[], int n)
{
    struct 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]);
    struct Node* root = arrayToList(arr, n);
    print(root);
    return 0;
}

#include <iostream>
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;
}

class LinkedList
{

// Representation of a node
static class Node
{
    int data;
    Node next;
};
static Node root;

// Function to insert node
static Node insert(Node root, int item)
{
    Node temp = new Node();
    temp.data = item;
    temp.next = root;
    root = temp;
    return root;
}

static void display(Node root)
{
    while (root != null)
    {
        System.out.print(root.data + " ");
        root = root.next;
    }
}

static Node arrayToList(int arr[], int n)
{
    root = null;
    for (int i = n - 1; i >= 0 ; i--)
        root = insert(root, arr[i]);
    return root;
}

// Driver code
public static void main(String[] args)
{
    int arr[] = { 1, 2, 3, 4, 5 };
    int n = arr.length;
    Node root = arrayToList(arr, n);
    display(root);
}
}

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

def insert(root, item):
	temp = Node(item)
	
	if (root == None):
		root = temp
	else :
		ptr = root
		while (ptr.next != None):
			ptr = ptr.next
		ptr.next = temp
	
	return root

def display(root):
	while (root != None) :
		print(root.data, end = " ")
		root = root.next
		
def arrayToList(arr, n):
	root = None
	for i in range(0, n, 1):
		root = insert(root, arr[i])
	
	return root

if __name__=='__main__':
	arr = [0, 2, 3, 4, 5, 1]
	n = len(arr)
	root = arrayToList(arr, n)
	display(root)

Output:

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

Space complexity to create linked list from array : O(1), no extra space is used in this approach.

Conclusion

This blog tried to discuss how easily you can create linked list from array and described their time and space complexities. Also, we will explain the proper step-by-step dry run for better understanding. Hope this article “create linked list from array ” enhances your knowledge of linked lists. To practice more problems on LinkedList you can check out at PrepBytes Linked List.

FAQs

1. What is a linked list?
   A linked list is a dynamic data structure where each node consists of two parts i.e. the data and a pointer to the next node.

2. How many types of linked lists are there?
   There are 4 types of linked lists:

   • Singly-linked list
   • Doubly linked list
   • Circular linked list
   • Doubly circular linked list

3. What is the advantage of a linked list over an array?
   The advantages of a linked list over an array are as follows:

   • We do not need to define the size of the linked lists.
   • Operations such as insertion and deletion are far faster than in the arrays.