As the title mentioned, I have to remove adjacent duplicates in doubly linked list such that if input is 'google', the adjacent duplicates removal is google-->ggle-->le and hence output should be 'le'. I'm supposed to code it in C. I tried to perform delete operation as shown in this image-
, except that I don't know how to continuously loop till all adjacent duplicates are removed (I don't know how to use recursion). I'm removing adjacent duplicates in remove_adjacent_duplicates() function, and since I don't know how to put terminating condition in loop, I've merely used while loop. I also don't know how to assign modified doubly linked list to original linked list named 'head', and so head=current; in while loop (line 63 of code) is a wrong assignment as it finally prints empty(?) list. Please rectify my mistakes and give correct solution. Here's my code-
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct node {
char data;
struct node *next;
struct node *prev;
};
struct node *head, *tail = NULL; //Represent the head and tail of the doubly linked list
int len;
void addNode(char data) {
struct node *newNode = (struct node*)malloc(sizeof(struct node)); //Create new node
newNode->data = data;
if(head == NULL) { //If dll is empty
head = tail = newNode; //Both head and tail will point to newNode
head->prev = NULL; //head's previous will point to NULL
tail->next = NULL; //tail's next will point to NULL, as it is the last node of the list
}
else {
tail->next = newNode; //newNode will be added after tail such that tail's next points to newNode
newNode->prev = tail; //newNode's previous will point to tail
tail = newNode; //newNode will become new tail
tail->next = NULL; //As it is last node, tail's next will point to NULL
}
}
void remove_adjacent_duplicates() {
struct node *current, *index, *temp;
if(head == NULL) {
return;
}
else
{
current=head;
while(current != NULL)
{
if(current->data == current->next->data)
{
index = current->prev; //noting data previous to duplicate data
//printf("%c\n",index->data);
while(current->data == current->next->data && current!=NULL)
{
current=current->next; //iterating till all adjacent duplicates are found
//printf("*%c\n",current->data);
}
temp=current->next; //temp points to character next to latest adjacent duplicate
//printf("!%c\n",temp->data);
index->next=temp; //the 'next' pointer of struct node of data before duplicate points to node after all adjacent duplicates found currently
//printf("@%c\n",index->data);
temp->prev=index; //data's 'prev' pointer (right after adjacent duplicates) points to data present just before adjacent duplicates
//printf("#%c\n",temp->data);
head=current; //logical error
//printf("$%c\n",head->data);
free(current);
free(index);
free(temp);
break;
}
else
{
current=current->next;
}
}
}
}
void display() {
struct node *current = head; //head the global one
while(current != NULL) {
printf("%c<->", current->data); //Prints each node by incrementing pointer.
current = current->next;
}
printf("NULL\n");
}
int main()
{
char s[100];
int i;
printf("Enter string: ");
scanf("%s",s);
len=strlen(s);
for(i=0;i<len;i ){
addNode(s[i]);
}
printf("Doubly linked list: \n");
display();
remove_adjacent_duplicates()
printf("Doubly linked list after removing adjacent duplicates: \n");
display();
return 0;
}
CodePudding user response：
Here is a possible implementation that keeps a running count of adjacent nodes still to be removed. This will have the value 0, 1 or 2. It mostly advances forwards through the list except when the running count reaches 0 and a previous node exists, in which case it steps backwards one position:
EDIT: This does not work for all cases. See reason why and a fix further down.
void remove_adjacent_duplicates(void) {
struct node *current = head;
struct node *next;
struct node *prev;
int remove = 0;
while (current != NULL)
{
next = current->next;
if (next != NULL && next->data == current->data)
{
// Need to remove the current node and the next node.
remove = 2;
}
if (remove != 0)
{
// Remove the current node.
prev = current->prev;
if (prev == NULL)
{
head = next;
}
else
{
prev->next = next;
}
if (next == NULL)
{
tail = prev;
}
else
{
next->prev = prev;
}
free(current);
remove -= 1; // Reduce running count of adjacent nodes to be removed.
if (remove != 0)
{
// Next node will also be removed.
// Step forward to next node.
current = next;
}
else if (prev == NULL)
{
// No current plan to also remove the next node.
// No previous node to step back to,
// so step forwards to the next node.
current = next;
}
else
{
// No current plan to also remove the next node.
// Step backwards to the previous node.
current = prev;
}
}
else
{
// Not removing current node. Step forwards to the next node.
current = next;
}
}
}
EDIT: The problem with the above code.
The above code fails to reduce ggoogle to le. The reason is that it has already removed the gg and the oo before it sees the next g.
EDIT: A possible fix follows.
One way to fix the problem is to extend struct node to include a flag which can be used as a temporary marker to defer the removal of one of the duplicate nodes. The first pass through the list can refer back to previous nodes that were duplicates.
struct node {
char data;
char flag;
struct node *next;
struct node *prev;
};
Here is a version of remove_adjacent_duplicates() that uses the flag to mark duplicates that have not been removed yet, and which searches back when it encounters a node that isn't a duplicate to check if it can be paired up with an earlier node and marked for removal. A second pass then removes the nodes marked for removal:
void remove_adjacent_duplicates(void) {
struct node *current = head;
struct node *next;
struct node *prev;
int remove = 0;
// First pass.
while (current != NULL)
{
if (remove == 0)
{
prev = current->prev;
while (prev != NULL && prev->flag != 0 &&
prev->data != current->data)
{
prev = prev->prev;
}
if (prev != NULL && prev->data == current->data)
{
prev->flag = 1;
current->flag = 1;
}
else
{
current->flag = 0;
}
}
next = current->next;
if (next != NULL && next->data == current->data)
{
// Need to remove the current node and the next node.
remove = 2;
}
switch (remove)
{
case 2:
// Remove the current node.
prev = current->prev;
if (prev == NULL)
{
head = next;
}
else
{
prev->next = next;
}
if (next == NULL)
{
tail = prev;
}
else
{
next->prev = prev;
}
free(current);
remove--;
break;
case 1:
// Mark the current node to be removed later.
current->flag = 1;
remove--;
break;
}
current = next;
}
// Second pass - remove marked nodes.
current = head;
while (current != NULL)
{
next = current->next;
if (current->flag != 0)
{
prev = current->prev;
if (prev == NULL)
{
head = next;
}
else
{
prev->next = next;
}
if (next == NULL)
{
tail = prev;
}
else
{
next->prev = prev;
}
free(current);
}
current = next;
}
}
CodePudding user response：
Truly speaking the task is very difficult for beginners as you and me.
Firstly it seems you think that in this declaration
struct node *head, *tail = NULL; //Represent the head and tail of the doubly linked list
the both pointers are initialized explicitly by the specified initializer NULL.
Actually this declaration is not the same as
struct node *head = NULL, *tail = NULL; //Represent the head and tail of the doubly linked list
In the original declaration the pointer head will be initialized implicitly as a null pointer only because the declaration has the file scope. Otherwise you have to write
struct node *head = NULL, *tail = NULL; //Represent the head and tail of the doubly linked list
to initialize the both pointers with NULL.
Further it is a bad idea when functions depend on global variables.
You should introduce one more structure as for example
struct list
{
struct node *head;
struct node *tail;
};
that indeed will define a doubly linked list.
Also the declaration of the global variable len that is used only in main also is a bad style of programming and actually along with the call of strlen is redundant. You should declare variables in minimal scopes where they are used.
Your function remove_adjacent_duplicates is invalid at least because it does not change the pointers head and tail. They stay unchanged.
Or for example this while loop
while(current != NULL)
{
if(current->data == current->next->data)
//...
can invoke undefined behavior when the list contains only one node because in this case you are dereferencing a null pointer in the condition of the if statement
current->next->data
The function can be defined the following wat as shown in the demonstration program below. I introduced one more structure as I already pointed out. The program does not use global variables.
Here you are.
#include <stdio.h>
#include <stdlib.h>
struct node
{
char data;
struct node *next;
struct node *prev;
};
struct list
{
struct node *head;
struct node *tail;
};
int addNode( struct list *list, char data )
{
struct node *newNode = malloc( sizeof( *newNode ) );
int success = newNode != NULL;
if (success)
{
newNode->prev = list->tail;
newNode->next = NULL;
newNode->data = data;
if (list->head == NULL)
{
list->head = newNode;
}
else
{
list->tail->next = newNode;
}
list->tail = newNode;
}
return success;
}
void display( const struct list *list )
{
for (const struct node *current = list->head; current != NULL; current = current->next)
{
printf( "%c -> ", current->data );
}
puts( "null" );
}
void reverse_display( const struct list *list )
{
for (const struct node *current = list->tail; current != NULL; current = current->prev)
{
printf( "%c -> ", current->data );
}
puts( "null" );
}
void remove_adjacent_duplicates( struct list *list )
{
struct node **current = &list->head;
while (*current != NULL)
{
if (( *current )->next && ( *current )->data == ( *current )->next->data)
{
struct node *tmp;
// remove adjacent nodes with data equal to data of the current node
while (( *current )->next && ( *current )->data == ( *current )->next->data)
{
tmp = ( *current )->next;
if ( tmp->next != NULL)
{
tmp->next->prev = tmp->prev;
}
( *current )->next = tmp->next;
free( tmp );
}
// remove the current node
if (( *current )->next == NULL)
{
list->tail = ( *current )->prev;
}
tmp = *current;
if (tmp->next != NULL)
{
tmp->next->prev = tmp->prev;
}
*current = tmp->next;
free( tmp );
// step one back in the list
if ( *current && ( *current )->prev)
{
current = ( *current )->prev->prev
? &( *current )->prev->prev
: &list->head;
}
}
else
{
current = &( *current )->next;
}
}
}
int main( void )
{
struct list list = { .head = NULL, .tail = NULL };
char s[100];
printf( "Enter string: " );
scanf( "