Segmentation fault deleting nodes from singly linked list

Question

this is the case i am working on

[11] -> [12] -> [13] -> NULL

I am trying to delete the elements from the liked list above(example) but I keep getting segfault and on running GDB doesnot help much. I am not looking for an answer but and explanation on where I am going wrong logically.

here is the code

int
List:: remove( int val )
{
    ListNode *headNode = _head;
    ListNode *tempNode = NULL;

    if(headNode->_value == val){
        tempNode = headNode->_next;
        delete headNode;
        _head = tempNode;
    }
    else
    {
        while(headNode->_value != val){
            tempNode = headNode;
            headNode = headNode->_next;
        }
        tempNode->_next = headNode->_next;
        delete headNode;

    }
}

do you intend to remove everything with val or the node at val? ordinality vs cardinality... — Grady Player
– Grady Player, Commented Jun 19, 2014 at 20:19
@GradyPlayer, so if the value is 12, 12 gets removed from the list and so on. — Maddy
– Maddy, Commented Jun 19, 2014 at 20:21
This is guaranteed to segfault if (a) the list is empty or (b) you're searching for a value not in the list. Think what happens when you're on the last element, then set headNode to headNode->_next (presumably NULL), then loop around and look at headNode->_value — Paul Roub
– Paul Roub, Commented Jun 19, 2014 at 20:22
Place while before if and add a condition for value not found. — haccks
– haccks, Commented Jun 19, 2014 at 20:23

WhozCraig · Accepted Answer · 2014-06-19 20:41:15Z

3

You're not accounting for the following conditions:

The list may be empty; i.e. _head is NULL;
The value may not be in the list at all.
Your function is declared to return int, but makes no such return

Assuming the rest of your code is correct (and that is a big assumption), I'm all-but-certain this is what you're trying to do:

void List::remove( int val )
{
    ListNode *headNode = _head;
    ListNode *tempNode = NULL;

    while (headNode && headNode->_value != val)
    {
        tempNode = headNode;
        headNode = headNode->next;
    }

    if (headNode)
    {
        if (tempNode)
            tempNode->next = headNode->next;
        else
            _head = headNode->next;

        delete headNode;
    }
}

Alternatively, if so inclined this can get (arguably) simpler utilizing a pointer-to-pointer to traverse the pointers in the list, not just their values. It is worth investigating how the following works, which still covers all the bases described previously, but does so using the actual pointers in the list nodes themselves, including _head, by-address rather than by-value, thereby eliminating the need for a walk-behind temporary pointer:

void List::remove( int val )
{
    ListNode **pp = &_head;

    while (*pp && (*pp)->_value != val)
        pp = &(*pp)->next;

    if (*pp)
    {
        ListNode *p = *pp;
        *pp = p->next;
        delete p;
    }
}

edited Jun 19, 2014 at 20:41

answered Jun 19, 2014 at 20:35

WhozCraig

66.5k11 gold badges82 silver badges148 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

haccks Over a year ago

Yes. That's what I wanted to answer but you beat me.

Andrew_CS · Accepted Answer · 2014-06-19 20:31:05Z

0

In your remove method you are assuming there are always elements in your list. - What if it is empty?
What if the value isn't in the list? You need to handle this case as well.

You're headed in the right direction - there are just a few cases that you haven't considered that can lead you to seg fault.

edited Jun 19, 2014 at 20:31

answered Jun 19, 2014 at 20:23

Andrew_CS

2,5601 gold badge20 silver badges40 bronze badges

Comments

sircodesalot · Accepted Answer · 2014-06-20 13:42:08Z

0

Example of forward traversal with deletion (forward-only linked list):

// Start from the beginning (head), then while the current isn't null, 
// move to the next node.
for (ListNode* current = head; current != null; current = current->next) {

    // Check the next item if there is one, and remove it if it matches the value.
    // We check the next one because you can't delete the current node in a 
    // forward only linked list (can in a doubly-linked list however)
    if (current->_next != nullptr && current->_value == value) {

        // Make this item point to the next next item 
        // (Since we're gonna delete the next item)
        current->_next = current->_next->next;

        // Delete the next item.
        delete current->_next;
     }

}

edited Jun 20, 2014 at 13:42

answered Jun 19, 2014 at 20:24

sircodesalot

11.5k9 gold badges55 silver badges86 bronze badges

2 Comments

user3629249 Over a year ago

this line: if (current->_next != nullptr && current->_next = value) has a small error and should be: if (current->_next != nullptr && current->_value = value) <== check for value match, not 'next' match to 'value'. BTW: it is a VERY bad idea to use field/variable names with a leading underscore as they can easily match the compiler generated names.

sircodesalot Over a year ago

Fixed. Also: C++ reserves names beginning with two underscores or an underscore and an uppercase letter, as per ISO C++ 17.4.3.1.2

Collectives™ on Stack Overflow

Segmentation fault deleting nodes from singly linked list

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related