Remove adjacent duplicates in doubly linked list in C
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;
}
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)
{
// Remove nodes from prev to current->prev inclusive.
current->prev = prev->prev;
prev->next = NULL;
if (prev->prev == NULL)
{
head = current;
}
else
{
prev->prev->next = current;
}
do
{
next = prev->next;
free(prev);
prev = next;
}
while (prev != NULL);
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;
}
}