CODEWITHSUNDEEP
c++
ArbitraryLines
ArbitraryLines

Reputation: 11

Removing Element from LinkedList (C++)

I'm currently struggling to understand why my removeElement() function is not actually removing the node from the LinkedList. Here is my code:

template<typename T>
void LinkedList<T>::remove(T element)  {
if (isEmpty()) {
    cout << "List is empty.";
}
else if (head == tail) {
    cout << "Only One" << endl;
    head == NULL;
    tail == NULL;
}
else {
    cout << "Multiple in List" << endl;
    Node<T>* curr = head;
    Node<T>* prev = curr;

    while (curr != NULL) {
        if (curr->element == element) {
            cout << "deleting " << element << endl;
            prev = curr->next;
            delete curr;
        }
        else {
            prev = curr;
            curr = curr->next;
        }

    }
 if(curr == NULL) {
 cout << element << " is not in list" << endl;
    }   
 }
}

This code effectively locates the element in the linked list, but for whatever reason deleting the current node doesn't actually remove the element from the list; even after having reassigned my previous to the next node. I'm going to keep looking for documentation in the meantime which may shed some light on what is almost certainly a dumb oversight on my side, but any help would be greatly appreciated.

Updated code now gives me a bounty of wonderful string_alloc errors:

template<typename T>
void LinkedList<T>::remove(T element)  {
Node<T>* current = head;
Node<T>* previous = current;

if (isEmpty()) {
    cout << "List is empty.";
}
else if (head == tail) {
    cout << "Only One" << endl;
}
else {
    cout << "Multiple Nodes in List" << endl;
    while (current != NULL) {
        if (current->element == element) {
            previous->next = current->next;
            delete current;
            break;

        }
        else {
            previous = current;
            current = current->next;
        }
    }
  }
}

I suspect at this point that it has more to do with the way I'm transitioning from node to node, specifically:

previous = current;
current = current -> next;

I still have not properly created a case for single-elements in the list, the errors are only thrown when I attempt to delete any node.

Upvotes: 0

Views: 367

Answers (1)

scohe001
scohe001

Reputation: 15446

You have a few problems:

Problem 1

else if (head == tail) {
    cout << "Only One" << endl;
    head == NULL;
    tail == NULL;
}

If your list only has one element, you set head and tail to null1, but never deallocate the element itself. Further, what if that one element in the list isn't the element you're trying to delete??

1. See problem 2.

Problem 2

You're never actually setting head or tail to null.

head == NULL; is a boolean expression that checks whether head is equal to NULL. This should be head = NULL;2

2. See problem 3.

Problem 3

Don't use NULL.

Problem 4

prev = curr->next;

This is only changing the local pointer prev to point to a different node. You need to change that node's next pointer instead. It should be:

prev->next = curr->next;

Problem 5

You don't consider the special case where you have more than 1 element in the list, but the element you are trying to delete is the first or last (meaning that head or tail will have to be reassigned).

There are a couple more little things, like possibly returning immediately after you find the node you want to delete (unless you're trying to delete all nodes that match the criteria. Your intent is ambiguous without a comment). Further, the readability/maintainability could be increased by splitting this into two functions, a Node<T> find(T element) and a void remove(Node<T> n). That should also make the edge cases easier to handle. But other than the little things, the list above should get your code working like you expect it at the least.

Upvotes: 6

Related Questions