Question

write any 2 c functions for a linked list and a doubly-linked sorted list

create at least two data structures

Answer 1

We will be wirting c function to

1)insert an element

2)delete an element

For linked list, to insert an element, we simply need to create a node, and add it to the beginning of the list

To delete an element in linked list, we need to find that element and delete it from the list.

For doubly sorted linked list, to insert an element we need to find out the correct position of the linked list and put the node there since it is sorted. To delete the node, we need to find the node and delete it.

Given below are the two data structures created as node1 and node2 for singly linked list and doubly linked list respectively:

======================================================

#include<stdio.h>
#include<stdlib.h>

typedef struct node1 {
int data;
struct node1 *next;
} node1;

typedef struct node2 {
int data;
struct node2 *prev;
struct node2 *next;
} node2;

node1 *makeNode1(int x){ //returns new node for linked list
node1 *newNode;
newNode = (node1*)malloc(sizeof(node1));
newNode->data=x;
newNode->next=NULL;
return newNode;
}

node2 *makeNode2(int x){ //returns new node for doubly linked list
node2 *newNode;
newNode = (node2*)malloc(sizeof(node2));
newNode->data=x;
newNode->next=NULL;
newNode->prev=NULL;
return newNode;
}

node1 *insertLinkedNode1(node1 *head,int x){
node1 *temp = makeNode1(x);
temp->next=head;
head=temp;

printf("\nNode %d inserted, new list is: ", x);
temp=head;
while(temp){
printf(" %d ", temp->data);
temp=temp->next;
}
return head;
}

node1 *deleteLinkedNode1(node1 *head,int x){
node1 *temp;
temp=head;
int flag=0;
if(head->data==x){
head=head->next;
free(temp);
flag=1;
}
else{
while(temp->next!=NULL && temp->next->data!=x)
temp=temp->next;
if(temp->next!=NULL){
node1 *temp3 = temp->next;
temp->next=temp->next->next;
free(temp3);
flag=1;
}

}

if(flag==0)
printf("\nNode not found");
else{
printf("\nNode %d deleted, new list is: ",x);
temp=head;
while(temp){
printf(" %d ", temp->data);
temp=temp->next;
}
}

return head;
}

node2 *insertLinkedNode2(node2 *head,int x){
node2 *temp = makeNode2(x);
if(temp->data < head->data){
temp->next=head;
head->prev=temp;
temp->prev=NULL;
head=temp;}
else{
node2 *temp1;
temp1=head;
while(temp1->next!=NULL && temp->data > temp1->next->data)
temp1=temp1->next;
if(temp1->next==NULL){
temp1->next=temp;
temp->prev=temp1;
}
else{
temp->next=temp1->next;
temp->prev=temp;
temp1->next=temp;
temp->next->prev=temp;
}
}
printf("\nNode %d inserted, new list is: ", x);
temp=head;
while(temp){
printf(" %d ", temp->data);
temp=temp->next;
}
return head;
}

node2 *deleteLinkedNode2(node2 *head,int x){
node2 *temp;
temp=head;
int flag=0;
if(head->data==x){
head=head->next;
free(temp);
flag=1;
}
else{
while(temp->next!=NULL && temp->next->data!=x)
temp=temp->next;
if(temp->next!=NULL){
//node2 *temp3= temp->next;
temp->next=temp->next->next;
if(temp->next!=NULL)
temp->next->prev=temp;
// free(temp3);
flag=1;
}
}

if(flag==0)
printf("\nNode not found");
else{
printf("\nNode %d deleted, new list is: ", x);
temp=head;
while(temp){
printf(" %d ", temp->data);
temp=temp->next;
}
}
return head;

}

int main(){
node1 *head1;
node1 *temp1 = makeNode1(3);
head1=temp1;
printf("Linked List: ");
head1=insertLinkedNode1(head1,10);
head1=insertLinkedNode1(head1,7);
head1=insertLinkedNode1(head1,2);
head1=deleteLinkedNode1(head1,7);
head1=deleteLinkedNode1(head1,10);
head1=deleteLinkedNode1(head1,3);

printf("\n\nDoubly sorted linked list: ");
node2 *head2;
node2 *temp2 = makeNode2(3);
head2 = temp2;
head2=insertLinkedNode2(head2,10);
head2=insertLinkedNode2(head2,7);
head2=insertLinkedNode2(head2,2);
head2=deleteLinkedNode2(head2,7);
head2=deleteLinkedNode2(head2,10);
head2=deleteLinkedNode2(head2,3);

return 0;

}

===============================================

Here is the screenshot of code: