CODEWITHSUNDEEP
javadata-structureslinked-listdoubly-linked-list
Josh Brown
Josh Brown

Reputation: 67

Trouble with deleting nodes in Doubly Linked List

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.

Upvotes: 0

Views: 172

Answers (1)

Anonymous
Anonymous

Reputation: 86203

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

Upvotes: 1

Related Questions