Programming in C: oday we are working with singly linked lists. Last week in cla

Question

Programming in C:

oday 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 -->

We have included the code from class on thursday 11/16, that contains insert( ), deleteFromList( ), sortList( ), and printList( ) so you can use that code as a starting point.

Explanation / Answer

#include "stdio.h"
#include "stdlib.h"

/* linked list structure */
typedef struct node{
int data;
struct node *next;
}ll;

/* insert in sorted order */
ll* insertSorted(ll *head,int d){
// create a temp node
ll *temp = (ll *)malloc(sizeof(ll));
  
// insert data to node
temp->data = d;
temp->next = NULL;
  
// create reference node
ll *temp1 = head;
  
// if head is empty make temp as head
if(head==NULL){
return temp;
}
  
// insert at beginning.
if(temp1->data<=d){
temp->next = temp1;
return temp;
}
  
// insert in middle
while(temp1->next!=NULL){
if(temp1->next->data<d){
temp->next = temp1->next;
temp1->next = temp;
return head;
}
else{
temp1 = temp1->next;
}
}
  
// insert at the end.
temp1->next = temp;
return head;
}

/*printing the linked list */
void printList(ll *head){
ll *temp = head;
while(temp!=NULL){
printf("%d-->",temp->data);
temp = temp->next;
}
printf(" ");
}

int main(void) {
// Disable stdout buffering
setvbuf(stdout, NULL, _IONBF, 0);
ll *head = NULL;
head = insertSorted(head,100);
head = insertSorted(head,65);
head = insertSorted(head,29);
head = insertSorted(head,-5);
head = insertSorted(head,-138);
printList(head);
head = insertSorted(head,51);
printList(head);
return 0;
}

/* sample output

100-->65-->29-->-5-->-138-->
100-->65-->51-->29-->-5-->-138-->

*/

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.