IN C LANGUAGE Today we are working with singly linked lists. Last week in class
ID: 3821081 • Letter: I
Question
IN C LANGUAGE
Today we are working with singly linked lists. Last week in class we covered inserting into, deleting from, sorting, and printing a singly linked list. For lab today we want you to create a new function called insertSorted() that is similar to insert() we created last week, but instead of just inserting the new value at the beginning of the list, the function should insert the value into the linked-list so that the values in the list are in sorted order from LARGEST to SMALLEST. The largest value should always be the first item in the list, and the smallest should always be the last item in the list. The function should take two arguments, 1) The reference (pointer) to the beginning of the list and 2) the value to be inserted. The function should return the new reference (pointer) to the list. Here is an example list detailing what the function should do:
Let's say we start with a linked list as follows: head --> 100 --> 65 --> 29 --> -5 --> -138 --> if we now want to insert 51, the value would NOT go at the beginning of the list, instead it would go somewhere in the middle and would look like: head --> 100 --> 65 --> 51 --> 29 --> -5 --> -138 -->
Explanation / Answer
/* Program to insert in a sorted list */
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct node
{
int data;
struct node* next;
};
/* function to insert a new_node in a list. Note that this
function expects a pointer to head_ref as this can modify the
head of the input linked list (similar to push())*/
struct node* insertSorted(struct node* head, struct node* new_node)
{
struct node* current;
/* Special case for the head end */
if (head == NULL || head->data < new_node->data)
{
new_node->next = head;
head = new_node;
return head;
}
else
{
/* Locate the node before the point of insertion */
current = head;
while (current->next!=NULL &&
current->next->data >= new_node->data)
{
current = current->next;
}
new_node->next = current->next;
current->next = new_node;
return head;
}
}
/* BELOW FUNCTIONS ARE JUST UTILITY TO TEST insertSorted */
/* A utility function to create a new node */
struct node *newNode(int new_data)
{
/* allocate node */
struct node* new_node =
(struct node*) malloc(sizeof(struct node));
/* put in the data */
new_node->data = new_data;
new_node->next = NULL;
return new_node;
}
/* Function to print linked list */
void printList(struct node *head)
{
struct node *temp = head;
printf("head-->");
while(temp != NULL)
{
printf("%d-->", temp->data);
temp = temp->next;
}
printf(" ");
}
/* Drier program to test count function*/
int main()
{
/* Start with the empty list */
struct node* head = NULL;
struct node *new_node = newNode(5);
head = insertSorted(head, new_node);
new_node = newNode(65);
head = insertSorted(head, new_node);
new_node = newNode(100);
head = insertSorted(head, new_node);
new_node = newNode(29);
head = insertSorted(head, new_node);
new_node = newNode(138);
head = insertSorted(head, new_node);
printList(head);
return 0;
}