Deleting a node in double linked list by an index position

Question

I am trying to delete a node from a doubly-linked list, but I get a NullPointerException when I try to delete the 2nd item. I was able to delete the first item and the last item.

Below is my code:

@Override
public T removeElement(int index) {
    // TODO Auto-generated method stub
    T result = null;

    if (IsEmpty()) {
        throw new NoSuchElementException();
    }

    if (count == 1 && index == 0) {
        result = head.getData();
        head = null;
        tail = null;
    }
    if (index == 0) {
        result = head.getData();
        head = head.getNext();
    }
    if (count == index) {
        result = tail.getData();
        tail = tail.getPrev();
        tail.setNext(null);
    }
    int i = 1;
    for (Node<T> current = head; current != null; current = current.getNext()) {
        if (i == index){
            result = current.getData();
            Node<T> previous = current.getPrev();
            Node<T> next = current.getNext();
            previous.setNext(next);
            next.setPrev(previous); //getting null pointer exception here
        }
        i++;
    }

    count--;
    return result;
}

@Override
public void addElement(T data)//add elements in the list
{
    Node<T> newNode = new Node<T>(data);
    if (IsEmpty()) {
        head = newNode;
        tail = newNode;
    }
    else {
        newNode.setPrev(tail);
        tail.setNext(newNode);
        tail = newNode;
    }
    count++;
}

Here is my test program:

public class Test {

public static void main(String[] args) {
    DoubleListImpl<Integer> test = new DoubleListImpl<Integer>();

    test.addElement(10);
    test.addElement(20);
    test.addElement(40);
    test.addElement(50);
    test.display();
    System.out.println(test.getCount());
    test.removeElement(4);
    System.out.println();
    //test.removeElement(3);
    test.display();
    System.out.println(test.getCount());
}
}

UPDATE:

I noticed something interesting a minute ago. If i made i=0 i get a null pointer error when i pass index ==3 as an argument in the removeElement function. or when i make i=1 i get a null pointer when i pass i==2 as an argument.

Answer 1

Hello guys thanks for the input. I actually figured out my error and this works. Below is my solution to the problem. Thanks a lot guys for the help:

@Override
public T removeElement(int index) {
    // TODO Auto-generated method stub

    T result = null;
    assert(index>=1&&index<=count);

    if(index==1){
        if(count==1){
            result = head.getData();
            head = null;
            tail = null;
        }
        else{
            result = head.getData();
            head = head.getNext();
            head.setPrev(null);
        }
    }
    else if(index==count){
        result = tail.getData();
        tail = tail.getPrev();
        tail.setNext(null);
    }
    else{
        Node<T> current = head;
        int i=1;
        while(current!=null){
            if(i==index){
                Node<T> prev = current.getPrev();
                Node<T> next = current.getNext();
                prev.setNext(next);
                next.setPrev(prev);
                break;
                //current = null;
            }
            current = current.getNext();
            i++;
        }
    }   
    count--;
    return result;   
}

Answer 2

I wrote in comments that I didn't think the erroneous if(count==index) was the cause of the NPE. I see now that it isn't directly the problem, but it does contribute to the problem by not catching the case where you request to delete the actual last node (index count - 1).

Of course, your addElement() method does not set or increment count when a node is added and IsEmpty() initially returns true, so the count will also be wrong. In fact, if IsEmpty() depends on count to determine whether the list is empty then addElement() will never expand your list past one element -- new elements "added" will instead replace the previous one.

Also contributing is the fact that execution falls through to the loop at the end of your method even when deletion has already been accomplished via one of the earlier special cases, as I also observed already. Consider, then, what happens when index is exactly the right value for the loop to iterate up to, but not beyond, the last element in your list. Control enters the block conditioned on i == index, and the current element's previous and next elements are retrieved. But the element in question is the last one, so its next is null. When you attempt to invoke setPrev() on that null reference, an NPE results.

I reiterate my suggestion in comments that you add internal Node objects to serve as head and tail, so that the Nodes containing real data are all internal, and you don't need all the special cases. For example,

class DoubleListImpl<T> implements DoubleList<T> {

    private final Node<T> head = new Node<T>(null);

    {   // better to put this in a constructor, but this way I avoid writing any
        head.setNext(head);
        head.setPrev(head);
    }

    // ...

    @Override
    public T removeElement(int index) {
        int i = 0;

        // negative indexes are always invalid
        if (index < 0) {
            throw new IndexOutOfBoundsException();
        }

        for (Node<T> current = head.getNext(); current != head;
                current = current.getNext()) {
            if (i == index){
                Node<T> previous = current.getPrev();
                Node<T> next = current.getNext();

                previous.setNext(next);
                next.setPrev(previous);
                // maybe you need count for something else, but not for this
                // count -= 1;
                return current.getData();
            }

            i += 1;
        }

        // If control reaches here then the given index is invalid
        throw new IndexOutOfBoundsException();
    }
}