1

I previously needed help debugging my deleteNode method. It works now (updated version posted below) but I want it to provide for the case when it has to delete the head node. At the moment, it returns a NullPointerException where I've inserted * in deleteNode. I don't know how any of my variables can be null at that point, seeing as my while loop requires both position and head to not be null in the first place.

public class LinkedList
{
private class Node
{
    int item;
    Node link;

    @SuppressWarnings("unused")
    public Node()
    {
        item = Integer.MIN_VALUE;
        link = null;
    }
    public Node(int x, Node p)
    {
        item = x;
        link = p;
    }
}

private Node head;

public LinkedList()
{
    head = null;
}

public boolean deleteNode (int target)
{
    Node position = head;
    boolean isGone = false;

    while(position != null && head != null)
    {
        if(position.link == head && position.link.item == target)
        {
            head = head.link;
            isGone = true;
            return isGone;
        }
    *** else if(position.link.item == target && position.link != head)
        {
            position.link = position.link.link;
            isGone = true;
            return isGone;
        }
        position = position.link;
    }
    return isGone;
}

public void printList()
{
    System.out.println("Your list is: ");
    Node position = head;
    while(position != null)
    {
        System.out.println(position.item + " ");
        position = position.link;
    }
    System.out.println();
}
}
Improve this question
1
  • 1
    Use a debugger and find out what it's not doing correctly Commented Nov 29, 2011 at 3:03

4 Answers 4

Reset to default
1

LinkedList.deleteNode(int) never modifies any node's link, so it doesn't remove any element from the list.

Suppose that nodeA.link == nodeB, and nodeB.item == target. Then you need to set nodeA.link = nodeB.link, so that nothing is pointing to nodeB anymore.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Here is a list of the problems I see:

  1. The enumerator you actually want to use, position, is never updated. The enumerator that is updated, counter is not needed.

  2. You are never actually removing the node. In order to remove the node, you need to set the previous node's link to the matching node's link, thus removing it out of the chain.

  3. You aren't dealing with special cases. What happens if the list passed is null? What happens if the matching node is the first node? The last node?

  4. You should be returning the head of the linked list from the calling function. This is required for when removing the head node of the linked list.

Since this is a homework question, try to work it out for yourself but hopefully those points will help.

Improve this answer

4 Comments

Thanks for the points, but could you explain the second bit, please? If I understand things correctly, my code position=position.link just continues on to the next link, basically traversing the list but not actually doing anything. I guess I'm not sure how to delete the link without using both position and counter.
That is correct. If this is a singly-linked list, what you should be doing is actually comparing against current.next, which in this case is position.link.item, then if that is the match, remove the links around position.link, i.e. position.link = position.link.link. Just make sure you account for the special case where the head node is the node to be deleted before you get to this while loop.
Thank you so much! I found the bug and now the loop works perfectly.
Glad to hear. Make sure you test for the special cases I mentioned in point 3, that will prove whether it really works perfectly or not :)
0

Look at your deleteNode() while loop code.

while(position != null && counter != null)
    {
        itemAtPosition = position.item;
        if(itemAtPosition == target)
        {
            position = position.link;
            isGone = true;
        }
        counter = counter.link;
    }

you update counter, but never refer to it. position never changes, so the 

if(itemAtPosition == target)

line never returns true. I suspect somewhere you need to check on counter.item!

Improve this answer

1 Comment

I agree, position & counter you just need to use one. The idea here is using only a node as current node and keep assigning current_node = current_node.link until target is found.
0

First, you didn't write code for the case where the target item is located at the beginning, in which the field head should be updated accordingly. Second, the compared item is never updated during traversing the list.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.