I have written a program that can can add char characters to the start of a doubly linked list. Now once I have this list, the aim of my program is to remove certain char character(s) from the list entirely. For example (using curly brackets only for representative purposes): if list consists of { a, b, b, a, c }, then my program can remove all "b" from the list to make it { a, a, c}. Moreover, if my list is {b, a, c, a} or {a, c, a, b} and if I want to remove "b" then the program works fine for both cases and gives me {a, c, a}.
But there's a number of issues (for all cases assume I want to remove "b"):
Here is the code I am using:
#include<stdio.h>
#include<stdlib.h>
struct list
{
int data;
struct list* next;
struct list* prev;
};
struct list* head; // global variable - pointer to head node of list.
struct list* last; // global variable - pointer to last node of list
//Creates a new list and returns pointer to it.
struct list* GetNewNode(char x)
{
struct list* newNode
= malloc(sizeof(struct list));
newNode->data = x;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
}
//Inserts a list at head of doubly linked list
void InsertAtHead(char x)
{
struct list* newNode = GetNewNode(x);
if(head == NULL)
{
head = newNode;
return;
}
head->prev = newNode;
newNode->next = head;
head = newNode;
struct list* temp = head;
while (temp->next != NULL) temp = temp->next;
last = temp;
}
void remove_element (char character)
{
struct list * cursor, *previous, *store_el;
//int boolean = 0;
if (head == NULL) return;
else
{
cursor = head;
while(cursor != NULL)
{
if (cursor->data == character)
{
if (cursor->prev == NULL)
{
// printf("deleting from front\n");
previous = head;
head = head->next;
head->prev = NULL;
//boolean = 1;
//free(previous);
}
if (cursor->next == NULL)
{
//printf("deleting from back\n");
previous = last;
last = last->prev;
last->next = NULL;
//boolean = 1;
//free(previous);
}
else
{
// printf("deleting from middle\n");
previous = cursor;
cursor = cursor->next;
cursor->prev = previous->prev;
store_el = previous->prev;
store_el->next = cursor;
cursor = head;
}
free(previous);
//printf("head data = %c\n", cursor->data);
}
cursor = cursor->next;
}
}
}
//Prints all the elements in linked list in forward traversal order
void Print()
{
struct list* temp = head;
printf("Forward: ");
while(temp != NULL)
{
printf("%c ",temp->data);
temp = temp->next;
}
printf("\n");
}
int main()
{
char character;
/*Driver code to test the implementation*/
head = NULL; // empty list. set head as NULL.
// Calling an Insert and printing list before and after deletion of character
InsertAtHead('c');
InsertAtHead('a');
InsertAtHead('b');
InsertAtHead('b');
InsertAtHead('a');
Print();
printf("After deletion:\n");
remove_element ('b');
Print();
}
/*
*I changed the name of your variable 'last' to 'tail'
*I removed the code at the end of your InsertAtHead function
*I added "tail = newNode;"
*I changed the name of your variable 'previous' to 'garbage'
*I removed your variable 'store_el' completely.
*I could have changed the whole code in your remove element function because the 3 cases are unnecessary but anyway.
*/
//Inserts a list at head of doubly linked list
void InsertAtHead(char x){
struct list* newNode = GetNewNode(x);
if (head == NULL){
head = newNode;
tail = newNode;
return;
}
head->prev = newNode;
newNode->next = head;
head = newNode;
}
void remove_element (char character){
struct list * cursor, *garbage;
cursor = head;
while(cursor != NULL){
if (cursor->data == character){
garbage = cursor;
if (cursor->prev == NULL){
head = head->next;
If (head!=NULL) head->prev = NULL;
cursor=head;
}else if (cursor->next == NULL){
tail = tail->prev;
tail->next = NULL;
cursor=NULL;
}else{
garbage->prev->next = garbage->next;
garbage->next->prev = garbage->prev;
cursor=cursor->next;
}
free(garbage);
} else cursor=cursor->next;
}
}
Try it now.
The problem with your code was that you were using the memory you freed.
/*
*cursor and previous point to the same memory address
*you free the memory that the variable previous points so the cursor points to that freed memory
*when you save the next address to the cursor using that freed memory you create an undefined behaviour (your code may work or may not)
*/
cursor = head;
while(cursor != NULL)
{
if (cursor->data == character)
{
if (cursor->prev == NULL)
{
previous = head;
head = head->next;
head->prev = NULL;
free(previous);
...
cursor=cursor->next;
The Improved Code:
#include<stdio.h>
#include<stdlib.h>
//The type of your variable data was wrong. I changed it to char
struct list{
char data;
struct list *prev, *next
};
void remove_element (char character){
struct list * cursor, *garbage;
cursor = head;
while(cursor != NULL){
if (cursor->data == character){
garbage = cursor;
if (garbage->prev!=NULL ) garbage->prev->next = garbage->next;
if (garbage->next!=NULL ) garbage->next->prev = garbage->prev;
cursor=cursor->next;
if (head==garbage) head=cursor;
//Basically the tail variable has no use for your current program.
//if (tail==garbage) tail=garbage->prev;
free(garbage);
} else cursor=cursor->next;
}
}