Thread: Delete first element of a linked list

  1. #1
    Registered User
    Join Date
    Feb 2019
    Posts
    2

    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!

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    26,319
    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.
    Last edited by laserlight; 2 Weeks Ago at 05:13 AM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Feb 2019
    Posts
    2
    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!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Linked List/Adding Element To Beginning of List
    By EricRoberts in forum C Programming
    Replies: 8
    Last Post: 01-01-2015, 11:13 AM
  2. Minimum element value of a linked list
    By RBCC in forum C Programming
    Replies: 31
    Last Post: 01-20-2011, 03:49 PM
  3. delete an element from a linked list
    By hinman in forum C Programming
    Replies: 6
    Last Post: 10-17-2007, 08:30 PM
  4. finding an element in a linked list from the end.
    By anoopks in forum C Programming
    Replies: 9
    Last Post: 04-08-2004, 09:00 AM
  5. How to add element to the end of a linked list?
    By Yin in forum C++ Programming
    Replies: 3
    Last Post: 04-22-2002, 03:04 PM

Tags for this Thread