C PROGRAMMING: Q1: BETTER INSERTING A better way to insert into a linked list in
ID: 3737232 • Letter: C
Question
C PROGRAMMING:
Q1: BETTER INSERTING
A better way to insert into a linked list in C
To avoid an 'if' statement where we assign either to "head" or to "something->next", since these are both "struct item *" variables we can use a pointer to "struct item *". In other words, a "struct item **".
After writing
, it is suitable to assign "&head" to pp.
Then accesses formerly to 'p' now can be made to "*pp".
Instead of "p = p->next;", we would now need to write the slightly awesome
The "&" is applying to all of "(*pp)->next"; no further parentheses are needed there. However, the parentheses around "*pp" are needed because of the operator precedence. So this is slightly awkward. (But it will be worth it below!)
Let's look at the new-style loop
and compare it to the old-style loop
In all cases, 'pp' in the first is a pointer to a variable containing the same value as 'p' in the second. Specifically, pp is a pointer to the variable containing the pointer to the struct-item we're looking at (whether it's stored in 'head' or in some other item's 'next' value).
So if the linked list is of length at least three, and p ends up being the values of head, head->next, and head->next->next in subsequent loop iterations;
then pp will be the values &head, &head->next, and &head->next->next in subsequent loop iterations.
So it doesn't sound so different so far. But we then have a very useful situation once we do find the item. Instead of the 'if's around whether this new item is going at the head of the list or in the middle, we can simply write:
If pp is still a pointer to 'head', this assigns new->next the former value of 'head', and changes 'head' to point to the new item.
If pp is a pointer to the 'next' field in some struct item, this assigns new->next to the former value of that 'next' field , and changes that 'next' field to point to the new item.
Eliminating these special cases is good. Code for this revised style of linked-list manipulation is slightly more complex in one sense, but that's something about pointers which you will get more and more used to. And it's simpler in all other respects. Once you are comfortable with all these pointers, it will be less error-prone to implement linked lists in this new style.
There is, however, no point in revising the search() function to use this new strategy. Since search() does not modify the list, nothing would be gained by having it manipulate pointers to the pointers, instead of the pointers themselves as it already does. So keep search() simple.
Note: To get the mark for Q1, you must eliminate all special cases -- no 'if' around whether the insertion is at the beginning of the list (or any other special case).
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();
/*
printf("After delete(22): ");
delete(22);
printall();
printf("After delete(5): ");
delete(5);
printall();
printf("delete(30) shouldn't do anything: ");
delete(30);
printall();
*/
return(0);
}
/*edit insert */
void insert(int key, int data)
{
struct item *new, *prev;
/* create the new item */
if ((new = malloc(sizeof(struct item))) == NULL) {
fprintf(stderr, "out of memory! "); /* unlikely */
exit(1);
}
new->key = key;
new->data = data;
/* find the node it goes after; NULL if it goes at the front */
if (head == NULL || head->key >= key) {
prev = NULL;
} else {
for (prev = head;
prev->next && prev->next->key < key;
prev = prev->next)
;
}
/* link it in */
if (prev == NULL) {
/* goes at the head of the list */
new->next = head;
head = new;
} else {
/* goes after 'prev' */
new->next = prev->next;
prev->next = new;
}
}
/*delete is for Q2*/
void delete(int key)
{
}
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>
//Null should be in capitals ie NULL
struct node
{
int info;
struct node* next;
};
struct node* start=NULL;
void create()
{
struct node *q,*temp;
q=start;
temp=(struct node *)(malloc(sizeof(struct node)));
printf("Enter the item ");
scanf("%d",&temp->info);
temp->next=NULL;
if(start==NULL)
start=temp;
else
{
while(q->next!=NULL)
{
q=q->next;
}
q->next=temp;
}
}
void display()
{
struct node *temp;
temp=start;
while(temp!=NULL)
{
printf("%d - > |%d| - > %d ",temp,temp->info,temp->next);
temp=temp->next;
}
printf(" ");
}
void insert(int k)//to insert after kth node
{
int p=k;//for printing the value of k
struct node *temp,*q;
q=start;
while((k-1)>0&&q!=NULL)//to go to that position
{
q=q->next;
k--;
}
if(q==NULL)
{
printf("%d number of nodes not present ",p);
return;
}
temp=(struct node *)malloc(sizeof(struct node));
printf("Enter the item ");
scanf("%d",&temp->info);
if(k==0)//for insertion at beginning
{
temp->next=start;
start=temp;
return;
}
temp->next=q->next;
q->next=temp;
}
void del(int p)
{
struct node *temp,*q;
if(start->info==p)//if 1st node to be deleted
{
temp=start;
start=start->next;
free(temp);
return;
}
q=start;
while(q->next!=NULL)//here if next->next is used we need to write spl case for last else this way no spl case required
{
if(q->next->info==p)
{
temp=q->next;
q->next=temp->next;
free(temp);
return;
}
q=q->next;
}
printf("The node is not present ");
}
struct node * rev(struct node *p)
{
struct node * r,* q;
q=NULL;
while(p)
{
r=p->next;
p->next=q;
q=p;
p=r;
}
return q;
}
int main()
{
create();
create();
create();
create();
create();
display();
insert(0);
display();
insert(2);
display();
insert(7);
display();
del(1);
printf("After deleting item 1 ");
display();
del(10);
display();
struct node *temp;
temp=start;
while(temp!=NULL)
{
start=temp->next; //to free the allocated memory
free(temp);
temp=start;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.