CODEWITHSUNDEEP
javalinked-list
murkyo0ocrimson
murkyo0ocrimson

Reputation: 11

How to delete a specific node in a linked list

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();
}
}

Upvotes: 1

Views: 8798

Answers (4)

dnatoli
dnatoli

Reputation: 7012

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.

Upvotes: 1

kevinhyunilkim
kevinhyunilkim

Reputation: 864

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.

Upvotes: 0

user949300
user949300

Reputation: 15729

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!

Upvotes: 0

ruakh
ruakh

Reputation: 183301

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.

Upvotes: 1

Related Questions