Removing element from linked list (if found) without deleting it from memory

Question

I have understood how deletion works in linked list, however the implementation is harder than I thought. I have written this below but it is not working sadly

My node:

struct DLinkedList
{
    double  sensorData;
    struct  DLinkedList *prev;
    struct  DLinkedList *next;
};

And this is my delete function:

void delete(struct DLinkedList **first, struct DLinkedList *el)
{
    struct DLinkedList* temp = *first;

    if (temp != NULL && temp->sensorData == el->sensorData)
    {
        (*first) = temp->next;
        free(temp);
        return;
    }

    while (temp != NULL && temp->sensorData == el->sensorData)
    {
        temp->prev = temp;
        temp = temp->next;
    }

    if (temp == NULL)
    {
        return;
    }

    free(temp);
}

Is there something wrong with the code itself? The compiler is not giving me any errors but the function doesn't seem to work properly, the way I call it in main() is delete(&first, el);

Here is my main, I have added 3 elements excluding el so that I can see the list more clearly:

int main()
{
    //Adding 3 nodes
    struct DLinkedList* first = NULL;
    struct DLinkedList* second = NULL;
    struct DLinkedList* last = NULL;
    
    struct DLinkedList* el = NULL;

    //Allocating 3 nodes
    first = malloc(sizeof(struct DLinkedList));
    second = malloc(sizeof(struct DLinkedList));
    last = malloc(sizeof(struct DLinkedList));

    el = malloc(sizeof(struct DLinkedList));

    first->sensorData = 1; //Assigning data for 'first' node
    first->next = second; //Link first node with second node
    first->prev = NULL;

    second->sensorData = 2;
    second->next = last;
    second->prev = first;

    last->sensorData = 3;
    last->next = NULL;
    last->prev = second;

    el->sensorData = 10;
    el->next = first;
    el->prev = NULL;

    insertFirst(&first, el);
    printList(first);
    isMember(&first, el);
    delete(&first, el);

    return 0;
}

//Printing contents of the linked list starting from the 'first' node
void printList(struct Node* first)
{
    while (first != NULL)
    {
        printf("  %f  ", first->data);
        first = first->next;
    }
}

Here below is my minimal example, I have made some changes in the names and main in order to be more readable

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

//A linked list node
struct Node
{
    double  data;
    struct  Node* prev;
    struct  Node* next;
};

void delete(struct Node** first, struct Node* el)
{
    if (*first == el)
    {
        *first = el->next;
    }

    if (el->prev)
    {
        el->prev->next = el->next;
    }

    if (el->next)
    {
        el->next->prev = el->prev;
    }

    free(el);
}

int main()
{
    struct Node* first = NULL;
    struct Node* el = NULL;

    el = malloc(sizeof(struct Node));

    el->data = 10;
    el->next = NULL;
    el->prev = NULL;

    delete(&first, el);
    print(first);
    return 0;
}

As I wrote in comments to my answer, this is not a [mre]. Please fix that. Furthermore, this main function does not make much sense. You're manually altering the next and prev pointers, and AFTER that you call `insertFirst`. That makes no sense. — klutt, Nov 22 '20 at 17:34
It also seems like you would benefit from reading https://ericlippert.com/2014/03/05/how-to-debug-small-programs/ and https://github.com/klutt/debug-small-c-programs — klutt, Nov 22 '20 at 17:38
@klutt I have made a minimal example, hopefully it's more readable now. Thanks for the links I will read them in a minute! About the previous main, I only wanted to add 3 elements in my linked list so that I can see that it is working, after that I wanted to use `insertFirst` and it worked, the `el` was put at the beginning! — Maso, Nov 22 '20 at 17:47
This is what happens when I try to compile your minimal example: https://onlinegdb.com/S12PEmd9D Maybe it's minimal, but you missed the "reproducible" part. — klutt, Nov 22 '20 at 17:48
Ok, so now it compiles. What makes you think that something is wrong? — klutt, Nov 22 '20 at 17:53
I edited it! You know I am lowkey dumb it was working all along but I forgot to call printList after delete... I was calling it before!! — Maso, Nov 22 '20 at 17:55
@klutt If you have got time, would you like to help me in the isMember() function? I can't get it to work properly. I know it is off from this post but it is the same program. — Maso, Nov 22 '20 at 18:01
Post a new question, but make sure that it is a [mre] where you state expected and actual behavior. — klutt, Nov 22 '20 at 18:02
@klutt thank you! I have asked the question before but I am still unable to get it to work. I have edited my question with a minimal reproducible example to test. Here is the question: [link](https://stackoverflow.com/questions/64944590/c-function-checks-if-element-is-member-of-linked-list-return-0-if-true-return) — Maso, Nov 22 '20 at 18:13

klutt · Accepted Answer · 2020-11-22T17:26:29.890

0

You're complicating it much more than necessary. If you have a doubly linked list, use it's abilities.

void delete(struct DLinkedList **first, struct DLinkedList *el) {
    // We only need to change the pointer to the first element
    // if that's the element we're deleting
    if(*first == el)
        *first = el->next;

    // The old switcheroo
    if(el->prev)
        el->prev->next = el->next;
    if(el->next)
        el->next->prev = el->prev;

    // Free and we're done. Skip this line if you want to keep the node
    // and only remove it from the list.
    free(el);
}

This could be combined with a convenient find function:

struct DLinkedList *find(struct DLinkedList **first, double val) {
    struct DLinkedList ret = *first;
    while(ret && ret->sensorData != val)
        ret = ret->next;
    return ret;
}

However, you should be careful comparing float numbers. Read more here: What is the most effective way for float and double comparison?

edited Nov 22 '20 at 17:26

answered Nov 22 '20 at 16:48

klutt

30,332
17
55
95

I think your element unlinking code is better, but I think you [still] have to pass the list header. That's because if you're removing either the head or tail of the list, the list struct needs to change as well. If OP is reusing the element struct as a list header, it doesn't need to be a double pointer. – Craig Estey Nov 22 '20 at 16:55
I don't completely understand your point, do you mean that I shouldn't store the head (first) node? Also why did you remove the first argument from the function? It is supposed to be `void delete(struct DLinkedList **first, struct DLinkedList *el)` – Maso Nov 22 '20 at 17:00
Thanks for the answer, you code seems so simple yet I am having hard time understanding it, what happens if I don't want to delete the first element? What I need is to delete the el element from the list not just any element. – Maso Nov 22 '20 at 17:09
@Maso What do you mean? Isn't `el` the node you want to delete? – klutt Nov 22 '20 at 17:10
Yes exactly, but you wrote that we only need to change the pointer to the first element if thats the element we are deleting, but I don't want to just delete the first element. I need to delete `el` – Maso Nov 22 '20 at 17:12
If `el` happens to be the first element, then you need to delete the first element. – klutt Nov 22 '20 at 17:13
Correct! But what if `el` isn't the first element, does it not get deleted then? – Maso Nov 22 '20 at 17:14
@Maso Then we delete it without altering the pointer to the first element. – klutt Nov 22 '20 at 17:15
I have used your code but it's not working with the way I have written my main() Is that correct? ` int main(){` `struct DLinkedList* el = NULL;` `el->sensorData = 10;` `el->next = first;` `el->prev = NULL;` `delete(&first, el); } ` – Maso Nov 22 '20 at 17:20
Hard to say why it does not work in your main function, because you have not provided a [mre]. Also, that code you provided now is very wrong. – klutt Nov 22 '20 at 17:22
I have edited my original post and added my main function, I don't understand why it is wrong? It is printing el as the first element plus the other three elements that I have provided manually, but the number 10 (el) is still not getting deleted from the list when I run the program. – Maso Nov 22 '20 at 17:26
Well, in the post you posted in comments did not have a malloc call ;) – klutt Nov 22 '20 at 17:27
Ah, my bad I missed it. But I am still unable to get it working. Is there anything else that I am missing in my main()? – Maso Nov 22 '20 at 17:30
Well, as I mentioned. You have not provided enough to reproduce the problem. Fix a [mre], and state actual and expected behavior. – klutt Nov 22 '20 at 17:32

Craig Estey · Answer 2 · 2020-11-22T17:21:22.407

It seems you're trying to reuse an "element" struct as the "list" struct for a doubly linked list.

Although you can reuse next/prev as head/tail, I recommend a separate header struct:

Here's what I mean. Note that I renamed the struct slightly to be more descriptive of purpose:

// element of list
typedef struct element Element;
struct element {
    double sensorData;
    Element *next;
    Element *prev;
};

// list header
typedef struct list List;
struct list {
    Element *head;
    Element *tail;
};

void
delete(List *list,Element *el)
{
    Element *next;
    Element *prev;

    next = el->next;
    prev = el->prev;

    if (next != NULL)
        next->prev = prev;

    if (prev != NULL)
        prev->next = next;

    if (list->head == el)
        list->head = next;
    if (list->tail == el)
        list->tail = prev;
}

Removing element from linked list (if found) without deleting it from memory

2 Answers2