C PROGRAMMING: Inserting into a linked list in C Your task is to write insert()
ID: 3737474 • Letter: C
Question
C PROGRAMMING: Inserting into a linked list in C
Your task is to write insert() now. The insert() function will insert in order, maintaining the property that the linked list is sorted at all times, as is relied on in search(). So you have to traverse the linked list until you find either the end of the list or an item with a greater key, and insert a new item at that point, calling malloc(sizeof(struct item)) to get space for the new list item. (Don't worry about the case where there is already a node with that key -- you will just add a second node with that key -- let's not make this a special case.)
If malloc returns null indicating out of memory, we will make this a fatal error for simplicity. (I.e. print an error message and exit(1).)
Starter code provided below:
#include <stdio.h>
#include <stdlib.h>
struct item {
int key;
int data;
struct item *next;
};
struct item *head = NULL;
int main()
{
extern void insert(int key, int data), delete(int key), printall();
extern int search(int key);
insert(38, 3);
insert(20, 2);
insert(5, 0);
insert(22, 6);
insert(46, 18);
printf("With all five items: ");
printall();
return(0);
}
/*PLEASE EDIT INSERT BY INSTRUCTION*/
/*PLEASE DONT COPY FROM THE SOLUTION*/
void insert(int key, int data)
{
}
int search(int key) /* returns -1 if not found */
{
struct item *p;
for (p = head; p && p->key < key; p = p->next)
;
if (p && p->key == key)
return(p->data);
else
return(-1);
}
void printall()
{
struct item *p;
for (p = head; p; p = p->next)
printf("%d: %d ", p->key, p->data);
printf("[end] ");
}
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct item {
int key;
int data;
struct item *next;
};
struct item *head = NULL;
int main()
{
extern void insert(int key, int data), delete(int key), printall();
extern int search(int key);
insert(38, 3);
insert(20, 2);
insert(5, 0);
insert(22, 6);
insert(46, 18);
printf("With all five items: ");
printall();
return(0);
}
/*PLEASE EDIT INSERT BY INSTRUCTION*/
/*PLEASE DONT COPY FROM THE SOLUTION*/
void insert(int k,int data)
{
struct item *t=head;
struct item *prev=NULL;
struct item *ptr;
//memory allocation for new item which is to inserted
ptr=(struct item*)malloc(sizeof(struct item));
ptr->data=data;
ptr->key=k;
ptr->next=NULL;
if(t==NULL)
{
//Runs when the list is NULL
ptr->next=NULL;
head=ptr;
return;
}
if(data<t->data)
{
//runs if given data is less than data in first item of linked list
ptr->next=head;
head=ptr;
return;
}
else
{
while(t!=NULL)
{
if(data>t->data)
{
//search location point for inserting the new item
prev=t;
t=t->next;
continue;
}
else
{
//Insert the item
prev->next=ptr;
ptr->next=t;
return;
}
}
prev->next=ptr;
//Insert item at last
}
}
int search(int key) /* returns -1 if not found */
{
struct item *p;
for (p = head; p && p->key < key; p = p->next)
;
if (p && p->key == key)
return(p->data);
else
return(-1);
}
void printall()
{
struct item *p;
for (p = head; p; p = p->next)
printf("%d: %d ", p->key, p->data);
printf("[end] ");
}
Sample Output :
With all five items:
5: 0
20: 2
38: 3
22: 6
46: 18
[end]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.