C++ delete element function in a doubly linked list

Question

I'm fairly new to C++ and it's data structures. I've made a few functions for my Doubly Linked List Class but i'm having trouble in the delete functions specifically. I've made a deleteHead() function which delete's the first node in the list, a deleteTail() function which deletes the last node in the list and finally a deleteElement(Item) function which goes over the list and deletes the node which has that the Item in it.

Problem is that whenever I try to delete the only remaining node from the list, the program crashes. i.e If I insert a node and then I call the deleteElement function on the same node (and if the node I inserted is the only node in the list) the program crashes.

here's my code.

template <class T>
void LinkedList<T>::deleteElement(T item)
{
    ListItem<T>* current = head;
    ListItem<T>* temp;
    if (head == NULL) {                         // if list is empty end the function
        return;
    }
    while (current) {
        if (current->value == item) {
            if (current == head) {              // if item is in the head
                deleteHead();
            }
            else if (current == getTail()) {    // if item is in the tail
                deleteTail();
            }
            // if item is between two nodes
            else if (current != head && current != getTail()) { 
                temp = current;
                temp->prev->next = temp->next;
                temp->next->prev = temp->prev;
                current->next = NULL;
                current->prev = NULL;
                if (current->next == NULL) {
                    deleteTail();
                }
            }
        }
        current = current->next;
    }
}

// Delete the Head Node
template <class T>
void LinkedList<T>::deleteHead()
{
    if (head != NULL) { // as long as head is not null, delete head
        ListItem<T> *current = head;
        head = head->next;
        current->next = NULL;
        head->prev = NULL;
    } else {return;} // if head is null, end the function without doing anything
}

// Delete Tail Node
template <class T>
void LinkedList<T>::deleteTail()
{
    ListItem<T> *tail = getTail();
    tail = tail->prev;
    tail->next->prev = NULL;
    tail->next = NULL;
}

Answer 1

Got the answer right. This was a question in my Data Structures assignment. Here's the code I implemented. Yes, i'm aware it has redundancies and inefficiencies but I had to work within the framework of the assignment.

This is my deleteElement() Function:

template <class T>
void LinkedList<T>::deleteElement(T item)
{
    ListItem<T>* current = head;
    ListItem<T>* temp;
    if (head == NULL) {                // if list is empty end the function
        return;
    }
    while (current) {
        if (current->value == item) {
            if (current == head) {              // if item is in the head
                deleteHead();
            }
            else if (current == getTail()) {    // if item is in the tail
                deleteTail();
            }
            else if (current != head && current != getTail()) { 
            // if item is between two nodes
                temp = current;
                temp->prev->next = temp->next;
                temp->next->prev = temp->prev;
                current->next = NULL;
                current->prev = NULL;
                if (current->next == NULL) {
                    deleteTail();
                }
            }
        }
        current = current->next;
    }
}

Answer 2

There are several issues in your code. First of all, you're not checking any pointers before you access them. For example, here:

temp = current;
temp->prev->next = temp->next;
temp->next->prev = temp->prev;

If there's only one element in the list, then its next and prev members will presumably be null. That means trying to assign something to temp->prev->next or temp->next->prev will be an access violation.

The same applies elsewhere, including this line at the end of your while loop:

current = current->next;

At that stage, current could hypothetically have been deleted, meaning trying to access its next member should fail. It probably won't fail at the moment though because of another problem...

Very importantly, you're not actually deleting anything. C++ doesn't have a garbage collector, so you can't just set a raw pointer to null and forget about it. You have to call delete on it to destroy and deallocate the object, otherwise it causes a memory leak. You'll need to fix that throughout your code, and then probably revise all your functions. You need to be very careful not to access an object after it's deleted.

With that said, instead of using raw pointers, you should really use smart pointers (i.e. std::shared_ptr). They take care of deleting the object for you when nothing else has a pointer to it. You still need to avoid accessing a deleted object, but it makes coding simpler, and hopefully more modern/robust.

Answer 3

Suggestions:

Step #1 - Add member variable ListItem<T>* tail to class ListItem<T>.

Step #2 - Replace all calls to getTail() with tail.

Step #3 - In function deleteElement, you can replace:

else if (current != head && current != tail)

with:

else

Step #4 - In function deleteElement, you should replace:

current->next = NULL;
current->prev = NULL;
if (current->next == NULL)
    deleteTail();

with:

delete current;

Step #5 - Rewrite function deleteHead as follows:

ListItem<T>* current = head;
if (head == tail)
    head = tail = NULL;
else
    head = head->next;
delete current;

Step #6 - Rewrite function deleteTail as follows:

ListItem<T>* current = tail;
if (tail == head)
    tail = head = NULL;
else
    tail = tail->prev;
delete current;