Removing element from `LinkedList`

Question

folks, my code has to remove a certain element from the list. It has to remove all of the occurences of the list. For example, if I'd like to remove "3" and the input is:

1
2
3
4
3
5

then the output should be:

1
2
4
5

But my code only removes the last occurence of the element as it can be seen when I run my code:

3
4
3
2
1

After removing element 3 


 4
 3
 2
 1

Could smb please help me out with that? THanks in advance!

public void removeElements(String number){
        if(isEmpty()){
            System.out.println("The list is empty!");
        }
        else{
            if(firstLink.data.equals(number)){
                firstLink = firstLink.next;
            }
            else{
                Link current = firstLink.next;
                Link previous = firstLink;
                while(current != null){
                    if(current.data.equals(number)){
                        previous.next = current.next;
                        break;
                    }
                    else{
                        previous = current;
                        current = current.next;
                    }
                }
            }
        }
    }

Answer 1

You can use a recursive approach to remove the nodes with given value.

1. Base condition -> return NULL if currentNode=NULL
2. At currentNode, we will check if its valid node or not,
   • if its valid Node (i.e currentNode's value != given value) then we will set its "next" by nextValidNode from the list ahead of it and then will return currentNode
   • if its not a valid node((i.e currentNode's value == given value) then, we have to simply return the nextValidNode from the list ahead of it

Here is the C++ implementation of the approach I discussed above, just pass head of list and value to the function:

ListNode* removeElements(ListNode* currentNode, int val) {

    // base condition
    if (currentNode == NULL) return NULL;

    // find nextValidNode
    ListNode* nextValidNode = removeElements(currentNode->next, val);

    // currentNode is NOT VALID node
    if (currentNode->val == val) {
         return nextValidNode;
    }

    // currentNode is VALID node
    else {
        currentNode->next = nextValidNode;
        return currentNode;
    } 
}

where ListNode is defined like this:

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

Answer 2

public void removeElement(String number) {
    if (head == null) {
        return; // The list is empty, nothing to remove
    }
    
    // Handle removal if the element to remove is at the head
    while (head != null && head.data.equals(number)) {
        head = head.next;
        size--;
    }
    
    // Now ensure the head is not the target, move on to the rest of the list
    Node prev = head;
    Node current = head.next;

    while (current != null) {
        if (current.data.equals(number)) {
            // Skip the current node to remove it
            prev.next = current.next;
            size--; // Update the size of the list
            if (prev.next == null) { // If removed node was the tail
                tail = prev; // Update the tail
            }
        } else {
            // Move prev to current if current node is not removed
            prev = current;
        }
        current = current.next; // Move to the next node
    }
}

Answer 3

What you could do is make a new collection containing all the values you want to remove from the LinkedList, and then call removeAll on the list:

ArrayList<String> numbersToRemove = new ArrayList<String>();
numbersToRemove.add("3");

list.removeAll(numbersToRemove);

This way, if you want to remove multiple numbers later on, you can just add them to numbersToRemove.

Some of the other answers are a bit simpler and more straightforward, though, so use them if they make sense, like iterating through the list and removing any elements that match the element you are removing. The only problem with this is that you will get a ConcurrentModificationException if you modify the list while iterating through the list using the object : list syntax, and will probably get an index out of range exception if you iterate through it using indices, so you will probably need to do something like this instead:

while (list.contains("3")) {
    ll.remove("3");
}

Answer 4

What you can do is iterate through the entire loop and check if the value of the element matches the searched value. If it does then you can use remove that element. I won't give away the solution to this but I can provide you with the algorithm.

for(int i = 0; i < length of list; i++)
{
    if(ith element of the list == value to be removed)
        //remove the ith term using .remove(i) method     
}

Answer 5

Remove the break, your loop is breaking after it gets into it for the first time.

Another point is, it is falling in your if(firstLink.data.equals(number)) and completely ignoring the else block. You should not have that block in else. It should be outside.

    if(firstLink.data.equals(number)){
        firstLink = firstLink.next;
    }
    Link current = firstLink.next;
    Link previous = firstLink;
    while(current != null){
       if(current.data.equals(number)){
          previous.next = current.next;
       } else {
            previous = current;
            current = current.next;
       }
   }

Answer 6

Your loop to remove elements is breaking on the first match. Maybe something like the following would work better. When current is a match, update previous.next but leave previous pointing at the previous node, and when it's not a match, update previous to point to the current node.

while (current != null) {
    if (current.data.equals(number)) previous.next = current.next;
    else previous = current;
    current = current.next;
}