I am trying to insert/delete the first element in a linked list but in case of insertion it is not adding it and in case of deletion it starts a infinite chain, I am unable to identify the issue. I am currently learning DSA so please ignore any unnecessary comments added in code
The code I created, (in C Language)
#include <stdio.h>
#include <stdlib.h>
struct Linked_List //structure has to be defined first
{
int number;
struct Linked_List *next;
};
typedef struct Linked_List node;
void create(node *p);
int count(node *p);
void print(node *p);
node *insert(node *head);
node *find(node *p, int key);
node *delete(node *head);
int main() {
node *head;
head = (node *)malloc(sizeof(node));
create(head);
printf("\n");
print(head);
printf("\n\nThe total number of elements in the linked list are :- %d",count(head));
printf("\n");
insert(head);
printf("\n");
print(head);
printf("\n");
delete(head);
printf("\n");
print(head);
}
void create(node *p) {
printf("\nInput number (Input -999 to end) :- ");
scanf("%d", &p->number);
if (p->number == -999) {
p->next = NULL;
} else {
p->next = (node *)malloc(sizeof(node));
create(p->next);
}
}
int count(node *p) {
if (p->next == NULL) { //using the if we are not counting the last element (-999)
return 0; //return 1 will add the last element to total count
} else {
return 1 + count(p->next);
}
//return 1 + count(p->next); //FAIL (as at last returns null pointer pointing to nowhere) returns total elements including -999,
}
void print(node *p) {
// printf("%d --> ", p->number); //this fails as in the end it will pass a null pointer which doesn't points to anywhere
// print(p->next);
if (p->next != NULL) { //this works as it first checks if pointer is null or not
printf("%d --> ", p->number); //if not it prints the number and recursion occurs
if (p->next->next == NULL) { //this if statement is used to print the last value which holds null pointer as outer if will not process it,
printf("%d", p->next->number); //it checks for next value if null pointer then prints its value
}
print(p->next);
}
}
node *insert(node *head) {
node *new; //structure of list
node *preceding; // preceding -> new -> key
int x, key;
printf("\nEnter the new value to be added :- ");
scanf("%d", &x);
printf("\nValue of key item (-999 if last) {-> new -> key}:- ");
scanf("%d", &key);
if (head->number == key) { //case for first position
new = (node *)malloc(sizeof(node));
new->number = x;
new->next = head;
head = new;
} else {
preceding = find(head, key);
if (preceding == NULL) {
printf("\nKey not found!!\n");
} else {
new = (node *)malloc(sizeof(node));
new->number = x;
new->next = preceding->next;
preceding->next = new;
}
}
return head;
}
node *delete(node *head) {
int key; //item to be deleted
node *preceding;
node *p; //temporary node
printf("\nEnter the item to be deleted :- ");
scanf("%d",&key);
if (head->number == key) {
p = head->next;
free(head);
head = p;
} else {
preceding = find(head, key);
if (preceding == NULL) {
printf("\nKey not found!!\n");
} else {
p = preceding->next->next;
free(preceding->next);
preceding->next = p;
}
}
return head;
}
node *find(node *p, int key) {
if (p->next->number == key) { //we know it is not the first so checking 2nd from head
return p;
} else { //checking 3rd from head
if (p->next->next == NULL) {
return NULL;
} else {
find(p->next, key); //recursive call
}
}
}
I tried to get the pointer to save the new location but for some reason it doesn't work as in case of the insert function as follows
new->next = head;
head = new;
Your approach with the dummy last node that contains the value -999 can only confuse users of the list.
For example why the user itself shall allocate a dummy node when there is the function create?! Who does actually create the list the user or the function create?!
This prompt in the function create
printf("\nInput number (Input -999 to end) :- ");
is supposed that the value -999 will not be stored in the list.
In this case for example the behavior of the function print is unpredictable.
Let's consder the situation when the list contains only one dymmy node with the value -999.
In this case nothng will be outputted due to this if statement
if (p->next != NULL) { //this works as it first
Now let's assume that the lst contains two nodes with for example values 1 and -999. In this case the both values will be outputted due to the nested if statement
if (p->next->next == NULL) {`
The function find has a bug. There is absent a return statement.in this part
} else {
find(p->next, key); //recursive call
}
Also the function find can invoke undefined behavior when the list contains only one node with the value -999 due to this statement
if (p->next->number == key) { //we know it is not the first so checking 2nd from head
Why do you decde that we know that it is not the first node of the list?! The functon is called within the function insert like
preceding = find(head, key);
And how to insert a node if the list contans only one dummy node? Why do you decide that the user knows in any time that the list contains only the single dummy node? Do he has to call the function count every time when he is going to insert a new node?
And at last the function insert has to be called like
head = insert( head );
The same way the function delete also has to be called
head = delete( head );
Also you need to write a function that will free all the allocated memory when the list is not rquored any more.
You should rewrite all your code anew removing the dummy node from the list implementaton.