PLEASE SHOW CODE AND PROOF THAT IT WORKS!!! A doubly linked list is a list in wh
ID: 3546402 • Letter: P
Question
PLEASE SHOW CODE AND PROOF THAT IT WORKS!!!
A doubly linked list is a list in which each node contains a pointer to the previous node in the list as well as a pointer to the next node in the list. To make accessing Nodes at the head of the list and the tail of the list easier, you will keep two pointers to the head and tail of the list Define the appropriate structs for a doubly linked list and then write a small program that implements a small doubly linked list and prints out the elements of the list. See picture below for a representation of the doubly linked list: Create Node struct for doubly linked entry. The values in the nodes are of type int. Create a DLList struct that contains two pointers: one to the head of the list and one to the tail of the list. This struct will represent the doubly linked list Create function to insert values in the doubly linked list in order. Therefore, the head is always pointing to the smallest element while tail is pointing to the largest element in the list, and every entry is followed by an entry larger or equal to it. Create a function to remove a given value if it exists in the doubly linked list For example if I try to delete the value v, then the function will search through the doubly linked list and remove that value if it exists. Note that the function will delete EVERY instance of the value in the list so if the value v exists more than once in the list, then all of them will be deleted. Create a function that prints the doubly linked list forward: starting from head ending at tail. Create a function that prints the doubly linked list backward: starting from tail ending at head. Create main to test your functions. Your test should test insertion of 20 random elements into the list and ensuring that the list is in order. Your test should then insert a specific value into the list and attempt to delete that value to test the delete function After each change to the list, you should print the list forward and backward. Test corner cases: what happens if you try to delete an element in an empty list, what happens if you insert a duplicate value into the list? How does delete handle a case where there is duplicate values?Explanation / Answer
#include<stdio.h>
#include<malloc.h>
typedef struct node
{
int value;
struct node* next;
struct node* prev;
}node;
node *head=NULL,*tail=NULL;
void print_forward()
{
node *q;
q=head;
while(q!=NULL)
{
printf("%d ",q->value);
q=q->next;
}
printf(" ");
}
void print_backward()
{
node *q;
q=tail;
while(q!=NULL)
{
printf("%d ",q->value);
q=q->prev;
}
printf(" ");
}
void insert(int val)
{
node *p;
p=(node *)malloc(sizeof(node));
p->value=val;
p->next=NULL;
p->prev=NULL;
node *q;
q=head;
if(q==NULL)
{
head=p;
tail=p;
}
else
{
while(q->value < val)
{
q=q->next;
if(q==NULL)
break;
}
if(q==head)
{
p->next=head;
head->prev=p;
head=p;
}
else if(q==NULL)
{
tail->next=p;
p->prev=tail;
tail=p;
}
else
{
p->prev=q->prev;
q->prev->next=p;
q->prev=p;
p->next=q;
}
}
print_forward();
print_backward();
}
void delete(int val)
{
node *q;
q=head;
while(q!=NULL)
{
if(q->value==val)
{
if(q==head)
{
head->next->prev=NULL;
head=head->next;
}
else if(q==tail)
{
tail->prev->next=NULL;
tail=tail->prev;
}
else
{
q->prev->next = q->next;
q->next->prev = q->prev;
}
}
q=q->next;
}
print_forward();
print_backward();
}
int main()
{
insert(2);
insert(3);
insert(4);
insert(2);
insert(6);
insert(7);
insert(12);
insert(27);
insert(21);
insert(89);
insert(9);
insert(97);
insert(12);
insert(17);
insert(13);
insert(76);
insert(23);
insert(56);
insert(2);
insert(1);
delete(2);
delete(1);
delete(787);
return 0;
}
Insertion :
every time I traverse from the start and check if the value which is to be inserted is less that or not and insert at a appropriate place
deletion
every time i traverse from the start and check if value i equal to node value then i place the previous attached to next node and it impies the node is deleted.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.