This code gives you a sample single linked list implementation. Checkpoint 1 Go
ID: 3586215 • Letter: T
Question
This code gives you a sample single linked list implementation.
Checkpoint 1
Go over the code and make sure you understand the implementation. Question: what is the characteristic of the insert function?
Checkpoint 2
Change your code (without adding any new functions) to append nodes into the linked list in the order they were inserted.
You should be able to do this by calling the append() function instead of the insert() function for Case 1.
See if this code works. If it doesn’t, use gdb to find the error. Signal the grader to show the error using gdb.
Checkpoint 3
Fix your code to append nodes in the order they were inserted; you need to work with the functions provided in the code and not change them.
Checkpoint 4
Write new functions for the following:
(i) Alwaysinsertnodesatthebeginningofthelinkedlist.
(ii) Considering nodes were inserted following (i), Delete function should delete the “last
occurrence” of the number.
Checkpoint 5
Write a new function to insert nodes in a sorted fashion so that the same number is not duplicated.
Code:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
}*head;
void append(int num)
{
struct node *temp,*right;
temp= (struct node *)malloc(sizeof(struct node));
temp->data=num;
right=(struct node *)head;
while(right->next != NULL)
right=right->next;
right->next =temp;
right=temp;
right->next=NULL;
}
void add( int num )
{
struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
if (head== NULL)
{
head=temp;
head->next=NULL;
}
else
{
temp->next=head;
head=temp;
}
}
void addafter(int num, int loc)
{
int i;
struct node *temp,*left,*right;
right=head;
for(i=1;i<loc;i++)
{
left=right;
right=right->next;
}
temp=(struct node *)malloc(sizeof(struct node));
temp->data=num;
left->next=temp;
left=temp;
left->next=right;
return;
}
void insert(int num)
{
int c=0;
struct node *temp;
temp=head;
if(temp==NULL)
{
add(num);
}
else
{
while(temp!=NULL)
{
if(temp->data<num)
c++;
temp=temp->next;
}
if(c==0)
add(num);
else if(c<count())
addafter(num,++c);
else
append(num);
}
}
int delete(int num)
{
struct node *temp, *prev;
temp=head;
while(temp!=NULL)
{
if(temp->data==num)
{
if(temp==head)
{
head=temp->next;
free(temp);
return 1;
}
else
{
prev->next=temp->next;
free(temp);
return 1;
}
}
else
{
prev=temp;
temp= temp->next;
}
}
return 0;
}
void display(struct node *r)
{
r=head;
if(r==NULL)
{
return;
}
while(r!=NULL)
{
printf("%d ",r->data);
r=r->next;
}
printf(" ");
}
int count()
{
struct node *n;
int c=0;
n=head;
while(n!=NULL)
{
n=n->next;
c++;
}
return c;
}
int main()
{
int i,num;
struct node *n;
head=NULL;
while(1)
{
printf(" List Operations ");
printf("=============== ");
printf("1.Insert ");
printf("2.Display ");
printf("3.Size ");
printf("4.Delete ");
printf("5.Exit ");
printf("Enter your choice : ");
if(scanf("%d",&i)<=0){
printf("Enter only an Integer ");
exit(0);
} else {
switch(i)
{
case 1: printf("Enter the number to insert : ");
scanf("%d",&num);
insert(num);
break;
case 2: if(head==NULL)
{
printf("List is Empty ");
}
else
{
printf("Element(s) in the list are : ");
}
display(n);
break;
case 3: printf("Size of the list is %d ",count());
break;
case 4: if(head==NULL)
printf("List is Empty ");
else{
printf("Enter the number to delete : ");
scanf("%d",&num);
if(delete(num))
printf("%d deleted successfully ",num);
else
printf("%d not found in the list ",num);
}
break;
case 5: return 0;
default: printf("Invalid option ");
}
}
}
return 0;
}
Explanation / Answer
1. Insert function inserts the value in list.It traverse the entire list, find the postion at which it need to be inserted.Then inserts in corresponding position.-The list is maintained in Ascending order.
2.If we need to insert in given order append will work, but we need to handle the initial case of inserting the head.If this is handled, then it works in that case.
3.
void append(int num)
{
struct node *temp,*right;
temp= (struct node *)malloc(sizeof(struct node));
temp->data=num;
right=(struct node *)head;
if(right==NULL)
{
add(num);
}
else
{
while(right->next != NULL)
right=right->next;
right->next =temp;
right=temp;
right->next=NULL;
}
}
4.Just call Add method instead of insert to add at beginning of list always.
5.
void insert(int num)
{
int c=0;
struct node *temp;
temp=head;
if(temp==NULL)
{
add(num);
}
else
{
while(temp!=NULL)
{
if(temp->data==num)
return;
if(temp->data<num)
c++;
temp=temp->next;
}
if(c==0)
add(num);
else if(c<count())
addafter(num,++c);
else
append(num);
}
}