Delete first element of a linked list

Hey everyone,

so I started learning C and tried to program a linked list by myself without looking anything up because I think that I will learn a lot more this way, so the code might not be optimal. But I ran into an error I didn't quite understand.

Here is my function to delete elements/nodes from the list:

Code:

---

void deleteElement(struct list *myList, int myData){
   
    struct list *currentElement = myList;
   
    if(myList->data == myData) {
        *myList = *myList->next;
        free(currentElement);
        return;
    }
   
    while(currentElement->next != NULL){
        if(currentElement->next->data == myData){
            struct list *deleteElement = currentElement->next;
            currentElement->next = currentElement->next->next;
            free(deleteElement);
        } else {
            currentElement = currentElement->next;
        }
    }
}

---

And it works fine this way, but only with a bit of trial and error, because at first I wanted to delete the first element of my list this way:

Code:

---

    if(myList->data == myData) {
        myList = myList->next;
        free(currentElement);
        return;
    }

---

Now to my question.
Why do I need to write my code like this:

Code:

---

*myList = *myList->next;

---

Instead of this:

Code:

---

myList = myList->next;

---

It seems that I didn't fully understand pointers yet. Maybe you're able to help.

Thank you in advance!

From what I see, struct list actually models a linked list node. We would more commonly name this struct node instead. If we wanted a linked list with a tail, one approach would be to create a struct list that contains a pointer to the head node and another pointer to the tail node, and then indeed this struct list object would model a tailed linked list, not a linked list node.

Consequently, instead of naming the parameter myList, we would more commonly name it head, as in pointer to the head node of the linked list. This would also make rather strange statements like this:

Code:

---

struct list *currentElement = myList; // eh, why is the current element an entire linked list?

---

into the more sensible:

Code:

---

struct node *currentElement = head; // ah, the current element pointer points to the head

---

Quote:

---

Originally Posted by Wayme

And it works fine this way, but only with a bit of trial and error

---

It is actually wrong though. What you are doing is copying the second node to the first node, so the caller's pointer to the first node now points to a copy of the second node. Consequently, it looks like the caller now has a pointer to the second node, because in fact the caller can no longer access the first node's original data and next pointer as it has been overwritten (this also means that the pointer to the second node is lost, so you have a memory leak). But, you then free the first node, so in fact attempting the access the first node's data and next pointer (which is now a copy of the second node's) results in undefined behaviour.

You could modify this approach to make it work: save the pointer to the second node, copy the second node to the first node, then free the second node. This way, the caller still has a valid pointer (to a copy of the original second node), and by freeing the original second node you eliminate the memory leak. But, there are better ways, especially since the data could be expensive to copy.

Quote:

---

Originally Posted by Wayme

Why do I need to write my code like this:

---

Basically, you have no way of returning a pointer to the second node of the linked list, that's why you had to resort to the hack of copying over the second node to the first node.

You have three options to fix this:

• Change the function return type so that you can return a pointer to the head node, whether it be the original or new head node.
• Change the node parameter to be a pointer to a pointer so that you can modify what the caller points to, i.e., you can update the caller's pointer to point to the second node as the new head.
• Instead of a node pointer parameter have a list pointer parameter. This way, you can modify the pointer to the head of the linked list without needing to modify the pointer to the entire linked list.

EDIT:
Your while loop is actually more complex than it needs to be because you are considering the next element in the loop rather than the current element. The solution is simple: make the current element actually be the current element by setting it before the loop:

Code:

---

currentElement = currentElement->next;
while(currentElement != NULL){
    if(currentElement->data == myData){
        struct list *deleteElement = currentElement;
        currentElement = currentElement->next;
        free(deleteElement);
    } else {
        currentElement = currentElement->next;
    }
}

---

EDIT #2: I note that if the head's data matches the search data, you immediately return from the function, but if not, you delete every node for which the data matches the search data. This behaviour is inconsistent. Also, you didn't consider the possibility that the linked list is empty.

I wanted the function to be void because my "addNode" function already returns a pointer and I wanted to practice both ways.
But I didn't fully think this through. The options you listed made me understand the concept a lot better.
The while loop was just the first thing that came to my mind, but what you wrote makes sense of course.
Also I already knew that the behavior of my function was inconsistent, but didn't fix it before posting here.

Thank you very much for your help!