I'm trying to learn linked lists from King (2008) "C Programming: A Modern Approach", 2nd ed and I'm puzzled by the behaviour of the deletion operation as compared to the insertion operation.

The author writes (p. 429):

Note that add_to_list doesn't modify the list pointer. Instead, it returns a pointer to the newly created node....Getting add_to_list to update first, turns out to be tricky.

Now while deleting the first node doesn't modify the original list, deleting nodes in the interior or the end does modify the original list. But delete_from_list is also making a copy of the first pointer, so why can it modify first (while add_to_list cannot)?

What am I missing here?

#include <stdio.h>
#include <stdlib.h>

struct node {
  int value;
  struct node *next;
};

struct node *delete_from_list(struct node *, int);
struct node *add_to_list(struct node *, int n);

int main(int argc, char **argv) {

  // setup a linked list
  
  // list's head
  struct node *first= NULL;

  // first node
  struct node *new_node= malloc(sizeof(struct node));
  new_node->value= 10;
  new_node->next= first;
  first= new_node;

  //second node
  new_node = malloc(sizeof(struct node));
  new_node->value= 20;
  new_node->next= first;
  first= new_node;

  //third node
  new_node= malloc(sizeof(struct node));
  new_node->value= 40;
  new_node->next= first;
  first= new_node;

  //fourth node
  new_node= malloc(sizeof(struct node));
  new_node->value= 30;
  new_node->next= first;
  first= new_node;

  int i;
  struct node *head= first;

  
  printf("\n------------------------\n");
  printf("    Original nodes: ");
  for(i=0; head!= NULL; head= head->next, i  )
    printf("\n%d-ith value: %d ", i, head->value);
  printf("\n------------------------\n");


  struct node *first_no20= delete_from_list(first, 20);
  struct node *head_no20= first_no20;
  
  printf("\n------------------------\n");
  printf("    Nodes without 20: ");
  for(i=0; head_no20!= NULL; head_no20= head_no20->next, i  )
    printf("\n%d-ith value: %d ", i,head_no20->value);
  printf("\n------------------------\n");

  
  printf("\n------------------------\n");
  head=first;
  printf("    Original nodes: ");
  for(i=0; head!= NULL; head= head->next, i  )
    printf("\n%d-ith value: %d ", i, head->value);
  printf("\n------------------------\n");


  struct node *first_no30= delete_from_list(first, 30);
  struct node *head_no30= first_no30;
 
  printf("\n------------------------\n");
  printf("    Nodes without 30: ");
  for(i=0; head_no30!= NULL; head_no30= head_no30->next, i  )
    printf("\n%d-ith value: %d ", i,head_no30->value);
  printf("\n------------------------\n");
  

  printf("\n------------------------\n");
  printf("    Original nodes: ");
  head=first;
  for(i=0; head!= NULL; head= head->next, i  )
    printf("\n%d-ith value: %d ", i, head->value);
  printf("\n------------------------\n");

  return 0;

}


struct node *delete_from_list(struct node *list, int n) {
  struct node *cur, *prev;

  for(cur=list, prev=NULL;
      cur != NULL && cur->value !=n;
      prev= cur, cur= cur->next)
    ;

  if(cur == NULL)
    return list;
  if(prev== NULL)
    list= list->next;
  else
    prev->next= cur->next;
  free(cur);

  return list;
}

struct node *add_to_list(struct node *list, int n) {
  struct node *new_node;

  new_node= malloc(sizeof(struct node));
  if(new_node == NULL) {
    printf("Error: malloc failed in add_to_list\n");
    exit(EXIT_FAILURE);
  }

  new_node->value = n;
  new_node->next= list;

  return new_node;
}

CodePudding user response：

I think that this quote

Note that add_to_list doesn't modify the list pointer. Instead, it returns a pointer to the newly created node....Getting add_to_list to update first, turns out to be tricky.

denotes the following.

When a new node is added to the list then all pointers to nodes (as for example the passed pointer and values of the data member next) that already exist in the list are not changed.

On the other hand, when a node is deleted then pointers to nodes (as for example the pointer that points to the deleted node or the value of the data member next of the preceding node) can be changed.

CodePudding user response：

Having tried, in the comments under the OP, to teach that the plethora of pointers in the OP code was the source of the problem, there is little else one can do but demonstrate the correct use of ONE pointer to the first node of the evolving LL (and one useful pointer that can traverse the LL.)

Here is the main() function written to perform the apparently desired task.

int main( void ) {
    struct node *first = NULL;
    struct node *p = NULL;

    // first node
    p = malloc(sizeof(struct node));
    p->value = 10;
    p->next = first; first = p;

    //second node
    p = malloc(sizeof(struct node));
    p->value = 20;
    p->next = first; first = p;

    //third node
    p = malloc(sizeof(struct node));
    p->value = 40;
    p->next = first; first = p;

    //fourth node
    p = malloc(sizeof(struct node));
    p->value = 30;
    p->next = first; first= p;


    puts( "Created nodes:" );
    for( p = first; p != NULL; p = p->next )
        printf( "[%d] ", p->value );
    puts( "\n------------------------" );

    first = delete_from_list( first, 20 );
    puts( "Nodes without 20:" );
    for( p = first; p != NULL; p = p->next )
        printf( "[%d] ", p->value );
    puts( "\n------------------------" );


    first = delete_from_list( first, 30 );
    puts( "Nodes without 30:");
    for( p = first; p != NULL; p = p->next )
        printf( "[%d] ", p->value );
    puts( "\n------------------------" );


    first = delete_from_list( first, 10 );
    puts( "Nodes without 10:");
    for( p = first; p != NULL; p = p->next )
        printf( "[%d] ", p->value );
    puts( "\n------------------------" );

    printf( "There are no \"original nodes\". There are only those nodes on the list." );

    return 0;
}

Omitted is the verification of the success of those multiple malloc() calls. An exercise for the reader.