Trouble with deleting nodes in Doubly Linked List

Question

So I'm building my own doubly linked list class (not for homework, just trying to build my own libraries for later use), and I'm having some difficulties implementing a removeAll method. Here is the relevant code (if you need more, let me know):

//ptr is a pointer node that moves through the list

//removes all nodes with type data
public void removeAll(T data) {
    while (findNode(data) != null) {
        deleteNode(findNode(data));
    } // end of while
} // end of removeAll method

//deletes single node
private void deleteNode(Node<T> del) {
    // del is head node 
    if (del.prevNode == null)
        removeFirst();
    // del is tail node
    else if (del.nextNode == null)
        removeLast();
    else {
        del.nextNode.prevNode = del.prevNode;
        del.prevNode.nextNode = del.nextNode;
        size--;
    } // end of if-else
} // end of deleteNode method

//returns node that matches criteria
private Node<T> findNode(T data) {
    ptr = head; // reset pointer
    while(ptr != null) {
        if(ptr.data == data)
            break;
        else {
            ptr = ptr.nextNode;
        } // end of if-else
    } // end of while
    return ptr;
} // end of findNode method

Output trying to remove 713 (I used integers for simplicity):

[ 9 -6 -6 -6 -6 2 3 713 ] // this is just to show all elements in linked list
------------- // divider
[ 9 -6 -6 -6 -6 2 3 713 ]  // after trying to remove 713

What I think is most interesting is that if I try to remove all the -6's, the removeAll method works.

[ -6 9 -6 -6 -6 2 3 713 -6 ] //added -6 to beginning and end
-------------
[ 9 2 3 713 ] //all -6's gone

It's as if 9 and 713 are just random cases where the methods don't work. I think the problem lies within the findNode and deleteNode methods. Testing the removeFirst and removeLast methods showed that they work flawlessly and give correct outputs. Any help/guidance is greatly appreciated, I've been struggling with this for close to 6 hours.

Are you doing this to get to know Java? Otherwise: LinkedList! - https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html — Erk, Jun 20 '18 at 15:13
713 is the last node, you are calling removeLast(), but don't show the codes of that method? apart from that, what makes you think building your own library is better than the java provided ones? — Kent, Jun 20 '18 at 15:14
i don't think building your own linked list for use in other programs is a good idea but recreating a linked list for coding practice is a great idea. — RAZ_Muh_Taz, Jun 20 '18 at 15:15
What happens if you place a -6 at the end instead of 713, will reomveAll(-6) still give you the correct result?? — RAZ_Muh_Taz, Jun 20 '18 at 15:16
@Kent I didn't include the removeLast() method because I know the code works and don't think it's relevant to the problem. If you want to see it, I can add it. — Josh Brown, Jun 20 '18 at 15:17
@RAZ_Muh_Taz just a -6 to the beginning and end, it works for some odd reason — Josh Brown, Jun 20 '18 at 15:17
@JoshBrown from your output, apparently, removing 713 didn't work. — Kent, Jun 20 '18 at 15:18
@Kent that's what I'm seeing, it won't remove it regardless of where it is — Josh Brown, Jun 20 '18 at 15:22
so I did some testing and I'm seeing that it won't remove any numbers greater than 127 or less than -129. I'm thinking it might have something to do with declaring the list type as ? Correct me if I'm wrong — Josh Brown, Jun 20 '18 at 15:36

Ole V.V. · Accepted Answer · 2018-06-20T15:53:26.660

The issue is with this line:

    if(ptr.data == data)

I think you meant:

    if (ptr.data.equals(data))

Since you cannot store ints in your list, I have assumed that your element type is Integer. Java caches Integer objects for frequently used integers like -6, so when you ask to have all -6 removed, you get a reference to the same cached -6 object that is also in your list. Then comparison with == yields true because ptr.date and data are references to the same object. Deletion works. 713 is not cached, so when you ask to delete it, you get a new Integer object. ptr.data and data are references two distinct identical objects. == yields false. Nothing gets deleted.

PS You shouldn’t want to include a doubly linked list in your “own libraries for later use”. For one thing, you will never need a doubly linked list. The predefined ArrayList and ArrayDeque will serve the same purposes better in almost all cases. For another, the advantages of using classes from the standard library are huge. Those classes have proven useable through more than 20 years, and you’ve got folks to maintain them for you. Also other readers of your code will understand it more easily when you are using the standard APIs.

Link: Question: Compare two objects with .equals() and == operator

You were correct about the `Integer` type. And your solution did work. I completely forgot about the difference between == and .equals(). Thanks for the help/link! — Josh Brown, Jun 20 '18 at 16:44

Trouble with deleting nodes in Doubly Linked List

1 Answers1