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<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
[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.