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

#include

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] ");

}