Question

Write a small program that uses a function to add array elements from an array into a linked list in-order.

Use the following array: const int size=5; int arr[size] = { 4, 1, 7, 2 ,3 };

Output: Array out of order: 4 1 7 2 3

Array in order using Linked List : 1 ,2, 3, 4, 7

Your program should display the linked list in-order using the array given.

Answer 1

#include<stdio.h>

#include<stdlib.h>

// size of arr

const int size = 5;

// define the structure of node

struct node{

    int data;

    struct node *next;

};

struct node *createOrderedList(int arr[size])

{

    // if the array is empty

    if( size == 0 )

        return NULL;

       

    // create a new node

    struct node *head = (struct node *)malloc(sizeof(struct node));

    // set the attributes of the node

    head->data = arr[0];

    head->next = NULL;

   

    int i;

   

    // traverse through the array

    for( i = 1 ; i < size ; i++ )

    {

        // create a new node

        struct node *new_node = (struct node *)malloc(sizeof(struct node));;

       

        // set the attributes of the node

        new_node->data = arr[i];

        new_node->next = NULL;

       

        // if the node is to be placed before the current head node

        if( arr[i] < head->data )

        {

            new_node->next = head;

           

            // make new_node as the new head

            head = new_node;

        }

        else

       {

            // point trav to head

            struct node *trav = head;

       

            // traverse through the list

            while(trav->next)

            {

                // if the new node is to be placed after the current node

                if( trav->next->data > arr[i] )

                    break;

                   

                // move to next node

                trav = trav->next;

            }

           

            new_node->next = trav->next;

            trav->next = new_node;

        }

    }

   

    return head;

}

int main()

{

    int arr[size] = { 4, 1, 7, 2 ,3 };

   

    int i;

   

    printf("Array out of order : ");

   

    // print array

    for( i = 0 ; i < size ; i++ )

        printf("%d " , arr[i]);

       

    printf("\n");

   

    // get the pointer to the head node of the ordered linked list

    struct node *head = createOrderedList(arr);

   

    // point trav to head

    struct node *trav = head;

   

    printf("Array in order using linked list : ");

   

    // traverse through the list

    while(trav)

    {

        printf("%d " , trav->data);

       

        // move to next node

        trav = trav->next;

    }

   

    return 0;

}

Sample Output