C++ get previous node to matching node in singly linked list

Question

To start: this is part of a homework problem so feel free to just hint at the answer or point me in the right direction instead of directly answering.

I am creating a single linked list in c++ one of the required functions is void remove(const T& key) where a given node is removed if the value matches that of the key passed into the function.

My current thinking is to do that I must first, find the node to be deleted, find the node before the one to be deleted, and find the node after the one to be deleted. From there I can delete the node that needs deleted and set the previous node to point toward the node that came after the deleted node.

Here are the relevant functions:

LinkedList.h

//Returns the node with passed in value key
ListNode<T>* find(const T& key) {
    ListNode<T>* currentNode = _head;
    while(currentNode != NULL && currentNode->data() != key){
        currentNode = currentNode->next();  
    }
    return currentNode; 
}

//Returns the node before the key
ListNode<T>* findPreviousNode(const T& key){
    ListNode<T>* previousNode;
    ListNode<T>* currentNode = _head;

    while(currentNode != NULL && currentNode->data() != key){
        previousNode = currentNode;
        currentNode = currentNode->next();  
    }
    return previousNode;
}

// Removes and deletes the first node in the linked list that has data
// equal to the  key
void remove(const T& key) {
    ListNode<T>* nodeToDelete = find(key);
    ListNode<T>* previousNode = findPreviousNode(key);
    ListNode<T>* nextNode = nodeToDelete->next();
    delete nodeToDelete;
    previousNode->setNext(nextNode);

}

I have tested my find(const T& key) function extensively and it works so I believe the issue is in my findPreviousNode function, however when I walk through the code it seems to work fine.

It seems to me that previousNode will always have the last checked element and when a match is found it returns previousNode which hasn't been updated yet so it still contains the node directly before the matching node, however this clearly isn't correct and I am not sure why. When I run the code I get a

segmentation fault (core dumped)

error message

Here are some pastebins with the entire code:

LinkedList.h http://pastebin.com/b4miZBzA

main.cpp(the method that calls the test functions) http://pastebin.com/0QGtUhjC

Answer 1

From the code you've posted here in the question, it looks like you have the right idea.

Two tips:

1. Defensive programming. Check that nodeToDelete and previousNode are not NULL. Currently, if the key is not found, you will end up dereferencing a NULL pointer, which could be the cause of your segmentation fault.

2. Efficiency. Why traverse the list twice (once in 'find', and once in 'findPrevious'), when you could just traverse it once and get both values? I.e. combine the find() and findPrevious() functions to reduce the amount of work the program has to do.

Answer 2

You're clearly missing a lot of Edge Cases in there.

Your find() function is not handling the case where key is not found. In that case it's returning null, for which the findPreviousNode() returns garbage value for previousNode.

Assuming find() returns pointer to head. Then again your findPreviousNode() returns uninitialized previous Node pointer.

Try to handle the Edge cases in your code.

Your remove() function should work fine assuming those are handled.

Also you don't really require to call find() function, then you can really improve the runtime by just returning appropriate values from findPreviousNode(), as you're running two loops which is unnecessary and thus you can save on your runtime.