How to Properly Delete Nodes of Linked List in C++

delete node(s) in a singly linked list in c

deleteNode() will remove at most the head or the first non-head node with a matching value. Note, that in the first case you need to update *head to the previous node. You should also handle head being NULL.

Here is an implementation of deleteNodes() that removes all matching nodes. To avoid the special case of the head node being removed, introduce a tmp node so we only have to deal with the non-head case:

void deleteNodes(struct NODE **n, int v) {
    if(!n) return;
    struct NODE tmp = {.prev = *n};
    for(struct NODE *p = &tmp; p->prev; ) {
        if(p->prev->value == v) {
            struct NODE *match = p->prev;
            p->prev = p->prev->prev;
            free(match);
        } else {
            p = p->prev;
        }
    }
    *n = tmp.prev;
}

How to correctly delete nodes in singly-linked-list c++

Too much code, this works

void delete_list()
{
    size = 0;
    while (first != nullptr)
    {
        Element<N>* next = first->next;
        delete first;
        first = next;
    }
}

Your version was OK for the first loop, but then for some reason you decided you had to delete iter even though it is only a working variable, not part of the list, and then you decided to delete first again. I don't know why you felt the need to do that.

Incidentally this is a serious bug

List(const List<N>& other): first(other.first), size(other.size) {}

When you copy a list you need to allocate a new set of nodes, otherwise you end up with two lists sharing the same set of nodes and no way of telling when a node is safe to delete. You probably need to read up on the rule of three.

How do I properly delete nodes of linked list in C++

Node *current  = new Node;
Node *previous = new Node;

This code causes memory leaks - you are never deleting this memory. You can declare pointers without memory allocation:

Node *current  = nullptr;
Node *previous = nullptr;

delete will delete the memory of the pointer so you will actually delete Nodes.
But using delete[] for the Node* is incorrect, it should be used only for arrays - the memory allocated with new[]. Improper use leads to undefined behaviour.
So, to properly delete nodes delete them with operator delete.

Use memory leaks detection tools to know are there memory leaks in you program.

The code to delete a list element: say, we have pHead which points to the head of the list
(but it would give you much more if you write such things yourself):

Node* pCur  = pHead;
Node* pPrev = pCur;

while (pCur && pCur->data != target) {
    pPrev = pCur;
    pCur  = pCur->next;
}

if (pCur==nullptr)  // not found
   return NOT_FOUND;

if (pCur == pHead) {   // first element matches
    pHead = pCur->next;
} else {
    pPrev->next = pCur->next;
}

// pCur now is excluded from the list

delete pCur;     // deallocate its memory

---

Alternative Using Pointer To Pointer (Community Addition)

The above can take on new light when you use the actual pointers in the list to perform the enumeration. The following starts with pp being assigned the address of the head pointer (not the node it points to; the actual pointer itself). We walk the list until pp hold the address of a pointer that is pointing to a node with the target to delete (could be the head pointer, could be a next pointer in some node, makes no difference). The pointer being addressed is set to its own node's next value, then the target node is removed.

This really should be watched in a debugger to see how it works, but the algorithm is remarkably simple given what is really going on:

Node **pp = &pHead;
while (*pp && (*pp)->data != target)
    pp = &(*pp)->next;

if (*pp)
{
    Node *victim = *pp;
    *pp = victim->next;
    delete victim;
}

Thats all of it. And you get head-node removal without having to special case it for free. Hope this helps as well.

How to delete nodes of a linked list between two indices?

It's all good to use just one struct, a node for your purpose.

struct node {
    char *string;
    struct node *next;
};

Then your loop for removing elements between two indices will not delete the right elements if you don't adjust the index according to the changing length of the list. And you must also return the new head of the list.

struct node *deleteList(struct node *head, unsigned from, unsigned to) {
    unsigned i;
    unsigned count = 0;
    for (i = from; i <= to; i++) {
        head = delete_at_index(head, i - count);
        count++;
    }
    return head;
}

The help function delete_at_index looks as follows.

struct node *delete_at_index(struct node *head, unsigned i) {
    struct node *next;

    if (head == NULL)
        return head;

    next = head->next;

    return i == 0
           ? (free(head), next)                                 /* If i == 0, the first element needs to die. Do it. */
           : (head->next = delete_at_index(next, i -
                                                 1), head); /* If it isn't the first element, we recursively check the rest. */
}

Complete program below.

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

struct node {
    char *string;
    struct node *next;
};

void freeList(struct node *head) {
    struct node *tmp;

    while (head != NULL) {
        tmp = head;
        head = head->next;
        free(tmp->string);
        free(tmp);
    }

}

struct node *delete_at_index(struct node *head, unsigned i) {
    struct node *next;

    if (head == NULL)
        return head;

    next = head->next;

    return i == 0
           ? (free(head), next)                                 /* If i == 0, the first element needs to die. Do it. */
           : (head->next = delete_at_index(next, i -
                                                 1), head); /* If it isn't the first element, we recursively check the rest. */
}

struct node *deleteList(struct node *head, unsigned from, unsigned to) {
    unsigned i;
    unsigned count = 0;
    for (i = from; i <= to; i++) {
        head = delete_at_index(head, i - count);
        count++;
    }
    return head;
}

void pushvar1(struct node **head_ref, char *new_data) {
    struct node *new_node = malloc(sizeof(struct node));
    new_node->string = strdup(new_data);
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}

void printListvar1(struct node *node) {
    while (node != NULL) {
        printf(" %s ", node->string);
        node = node->next;
    }
    printf("\n");
}

int main(int argc, char **argv) {
    struct node *head = NULL;
    for (int i = 0; i < 5; i++) {
        char str[2];
        sprintf(str, "node%d", i);
        pushvar1(&head, str);
    }

    puts("Created Linked List: ");
    printListvar1(head);
    head = deleteList(head, 0, 2);
    puts("Linked list after deleted nodes from index 0 to index 2: ");
    printListvar1(head);
    freeList(head);
    return 0;
}

Test

Created Linked List: 
 node4  node3  node2  node1  node0 
Linked list after deleted nodes from index 0 to index 2: 
 node1  node0 

Delete Node - Linked List - C

The code is removing the wrong item from the linked list:

See:

        if ( ( last->x ) == key )
        {
            printf( "value to be deleted is found" );
            node *temp = last->next;     // last->next? No, just last.
            last->next = last->next->next;
            free( temp );
            length--;
        }

last is pointing at the element to be removed. But then the code assigns temp to point at last->next (NOT last), and then cuts that from the list.

So by looking at node->next rather than the current node, it's possible to trim it out since you're starting from the pointer before the one to remove. Basically your code was almost there already.

void deletenode( u8 key )
{
    node *ptr = head;

    if ( ( ptr->x == key ) )
    {
        // Delete the first/head element
        node *temp = ptr;
        head = head->next;
        free( temp );
        length--;
    }
    else
    {
        while ( ptr->next != NULL )
        {
            if ( ( ptr->next->x ) == key )
            {
                printf( "value to be deleted is found" );
                node *temp = ptr->next;
                ptr->next = ptr->next->next;
                free( temp );
                length--;
            }
            ptr = ptr->next;
        }
    }
}

Also I took the liberty of renaming last to ptr because it was confusing me.

EDIT: Updated to remove the head cleanly too.

---

Related Topics