I wrote three algorithms for delete item/items from a single-linked list. Number 1 works fine. Also number 2 works fine. Number 3 doesn't work, and I know. But why number 3 is incorrect and what is the difference with the number 2 and the double pointer?
Number 1:
struct nodo * delete1(struct nodo * top, int data) {
struct nodo *current, *temp;
if(top->valore == data ) {
current = top->next;
free(top);
top = current;
}
current = top;
while (current->next)
{
if (current->next->valore == data)
{
temp = current->next->next;
free(current->next);
current->next = temp;
}
else
current = current->next;
}
return top;
}
Number 2:
void delete2(struct nodo **p, int k) {
while(*p) {
if ((*p)->valore == k)
{
struct nodo * tmp = (*p)->next;
free(*p);
(*p) = tmp;
}
else
{
p = &(*p)->next;
}
}
}
Number 3:
struct nodo * delete3(struct nodo * top, int k) {
struct nodo * curr = top;
while(curr) {
if(curr->d == k) {
struct nodo * tmp = curr->next;
free(curr);
curr = tmp;
}
else curr = curr->next;
}
return top;
}
For starters the three functions have different behaviors.
In the first function if the first node of the list has the value equal to the specified value then only this first node is deleted. Otherwise all nodes with the specified value are deleted.
But in any case even after you updated the function it can invoke undefined behavior for example when is called for an empty list or when a single node of the list was deleted.
In the second function all nodes (independent on whether the first node has the value equal to the specified value) with the value equal to the specified value are deleted.
The third function is entirely wrong because it changes the local variable curr
instead of for example the variable top or any data member next of a node. That is in any case the function returns the previous value of the pointer top independent on whether the pointed node was deleted.
To make the behavior of the first function similarly to the behavior of the second function it should be defined the following way.
struct nodo * delete1(struct nodo * top, int data)
{
while ( top && top->valore == data )
{
struct nodo *temp = top->next;
free( top );
top = temp;
}
if ( top )
{
struct nodo *current = top;
while (current->next)
{
if ( current->next->valore == data )
{
struct nodo *temp = current->next->next;
free( current->next );
current->next = temp;
}
else
{
current = current->next;
}
}
}
return top;
}