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

#include
#include

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

[forminator_quiz id="3504"]

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.

Leave a Reply

Your email address will not be published. Required fields are marked *