Suppose we define a linked list of ints using the following struct. /* *struct f
ID: 3850657 • Letter: S
Question
Suppose we define a linked list of ints using the following struct.
/*
*struct for a single node in a linked list. info contains the data
*stored in this node. next contains a pointer to the node with * the next piece of data.
*/ struct node
{ int info; struct node *next;
} ;
typedef struct node node;
Write the recursive function deleteNode which deletes the first node in the linked list whose member variable info equals x.
Outline of the function:
If Head is NULL return NULL.
Else, if the member variable info of the node pointed to by Head equals x, deleteNode deletes the node pointed to by Head. And returns a pointer to the next node in the linked list.
Else, it should recursively call deleteNode on the next node in the linked list. It sets Head’s next to the pointer returned by this recursive call. It then returns Head.
1)
node* deleteNode(node *head, int x){
Now suppose we define a doubly linked list of ints using the following struct.
/*
*struct for a single node in a linked list. info contains the data
*stored in this node. next contains a pointer to the node with * the next piece of data. prev contains a pointer to the node with * the previous piece of data.
*/ struct node
{ int info; struct node *next; struct node *prev;
} ;
typedef struct node node;
How does this change the function deleteNode? Rewrite it below with the required modifications:
2)
node* deleteNode(node *head, int x){
Explanation / Answer
Answer 1: for singly linked list
struct node
{
int info; struct node *next;
};
typedef struct node node;
node* deleteNode(node *head, int x){
if(head == NULL)
return head;
// if this node is the node to be deleted
if(head->info == x) {
return head->next;
}
// recursively call the list starting from next node
// in this case, head doesn't change
head->next = deleteNode(head->next, x);
return head;
}
Answer 2: For doubly linked list
struct node
{
int info;
struct node *next;
struct node *prev;
};
typedef struct node node;
node* deleteNode(node *head, int x){
if(head == NULL)
return head;
// if this node is the node to be deleted
if(head->info == x) {
head->next->prev = NULL;
return head->next;
}
// recursively call the list starting from next node
// in this case, head doesn't change
head->next = deleteNode(head->next, x);
head->next->prev = head;
return head;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.