Deleting first element in a linked sorted list

Sexy mf Source

I'm new here and this is actually my first question. I learn for myself C (mostly in the evenings) so please don't kill if what I ask sounds stupid.

I wrote this code and I can't delete the first element of the list, somehow I can delete other elements. I have also a problem with the function reverse_list and I believe it is related to the fact that I did not pass the argument as a reference. I tried before (few times) to pass the argument as reference but it didn't work. I understood that I can't use the & in the argument in C, it that true? What would be the equivalent argument in C to this struct Node * delete_num (int wanted, struct Node * head) {bla bla bla}?

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

struct Node {
    int data;
    struct Node * next;
};


struct Node * build_sorted_list () {
    struct Node * head = NULL, * temp, * rear, * front;
    int num;
    printf ("please enter a number:");
    scanf ("%d", &num);
    while (num != 0) {
        temp = (struct Node *) malloc (sizeof (struct Node));
        if (temp == NULL) {
            printf ("god damn");
            break;
        }
        temp -> data = num;
        if (head == NULL) {
            temp -> next = NULL;
            head = temp;
        }
        else if (num <= head -> data) {
            temp -> next = head;
            head = temp;
        }
        else {
            rear = head;
            front = rear -> next;
            while (front != NULL && front -> data <= num) {
                rear = front;
                front = front -> next;
            }
            temp -> next = front;
            rear -> next = temp;
        }
        printf ("enter number please:\n");
        scanf ("%d", &num);
    }
    return head;
}


void print_list (struct Node * head) {
    while (head != NULL) {
        printf ("%d->", head -> data);
        head = head -> next;
    }
}

void free_list (struct Node * head) {
    struct Node * temp;
    while (head != NULL) {
        temp = head;
        head = head -> next;
        free (temp);
    }
}


struct Node * reverse_list (struct Node * head) {
    struct Node * rear, * mid, * front;
    if (head != NULL || head -> next == NULL) {
        return head;
    }
    rear = head;
    mid = rear ->next;
    front = mid -> next;
    while (front != NULL) {
        mid -> next = rear;
        rear = mid;
        mid = front;
        front = front ->next;
    }
    mid -> next = rear;
    head -> next = NULL;
    head = mid;
    return head;
}


struct Node * delete_num (int wanted, struct Node * head) {
    struct Node * rear, * front;
    if (head == NULL) {
        return head;
    }
    if (head -> data == wanted) {
        struct Node * temp = head;
        head = head -> next;
        temp = NULL;
        return head;
    }
    rear = head;
    front = head -> next;
    while (front != NULL) {
        if (front -> data == wanted) {
            break;
        }
        rear = front;
        front = front -> next;
    }
    if (front != NULL) {
        rear -> next = front -> next;
    }
    free (front);
    return head;
}


int main() {
    struct Node * head;
    int wanted;
    head = build_sorted_list();
    print_list (head);
    printf ("\n");
    reverse_list (head);
    printf ("\n");
    print_list (head);
    printf ("\n");
    printf ("please enter a number to delete:");
    scanf ("%d", &wanted);
    delete_num (wanted, head);
    print_list (head);
    printf ("\n");
    free_list (head);

    return 0;
}
c

Answers

answered 1 week ago Andres di Giovanni #1

As a rule of thumb with recursive functions that manage data structures. Operations on the structure should return the structure.

By definition, a linked list is either:

  • An empty list.
  • A node with a value, and a linked list as its tail.

A linked list has a recursive nature. You need to be very careful, recursive functions are very complex, despite the short amount of code.

In your main function you have a head pointer. It's not safe to assume that the head will remain the same. In fact, your problem comes when you remove the first element (head).

Your delete should be something like this:

struct Node * delete_num(int wanted, struct Node * head){
    if( head == NULL)
        return NULL;    //Reached the end of the line, nothing to do.

    if( head->data != wanted )
        head->next = delete_num(wanted, head->next);    //Haven't reached it yet, but 
                                                        //the element must be down 
                                                        //the line, I want to update
                                                        //my next in case it's the 
                                                        //next node.

    if(head->data == wanted){
         struct Node * aux = head;
         head = head->next;
         free(aux);
    }

    return head;
}

This is assuming you only want to remove one element and your list doesn't admit repeated values.

Your call to this function from main should be:

head = delete_num(wanted, head);

Andres

comments powered by Disqus