C PROGRAMMING: Inserting into a linked list in C Your task is to write insert()
ID: 3737473 • 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
Given below is the completed code for the question.
Please do rate the answer if it was helpful. Thank you
#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)
{
struct item *p = (struct item *) malloc(sizeof(struct item));
struct item *prev = NULL, *curr = head;
if(p == NULL)
{
printf("Could not allocate memory! ");
exit(1);
}
p->key = key;
p->data = data;
p->next = NULL;
if(head == NULL)
head = p;
else
{
/*insert in ascending order of key*/
for(; curr != NULL; prev = curr, curr = curr->next)
{
if(key < curr->key)
break;
}
p->next = curr; /*link new node to next node*/
if(prev == NULL) /*insert before head node?*/
head = p;
else
prev->next = p; /*link the previous node to new node*/
}
}
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] ");
}
OUTPUT
======
With all five items:
5: 0
20: 2
22: 6
38: 3
46: 18
[end]
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.