Java: Good algorithm for removing an element from a linked list?

Question

I have a pretty basic question here. I am implementing a few operations on a linked list as an exercise. One such operation is removal:

/**
 * Removes the element at index.
 * @param index
 * @throws IndexOutOfBoundsException    If index is greater than the list's length.
 */
public void remove(int index) throws IndexOutOfBoundsException;

The class's only instance variable:

private Node<T> first;

Node class:

public class Node<T> {

    public T datum;
    public Node<T> next;

    public Node(T datum) {
        this.datum = datum;
    }

    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + ((datum == null) ? 0 : datum.hashCode());
        result = prime * result + ((next == null) ? 0 : next.hashCode());
        return result;
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        Node<T> other = (Node<T>) obj;
        if (datum == null) {
            if (other.datum != null)
                return false;
        } else if (!datum.equals(other.datum))
            return false;
        if (next == null) {
            if (other.next != null)
                return false;
        } else if (!next.equals(other.next))
            return false;
        return true;
    }
}

Here is my implementation of remove():

@Override
public void remove(final int index) throws IndexOutOfBoundsException {

    if (null == first) {
        throw new IndexOutOfBoundsException();
    }

    Node<T> current = first;
    int nodesExamined = 0;

    if (0 == index) {
        first = first.next;
        return;
    }

    while (null != current) {
        if (nodesExamined + 1 == index) {
            current.next = null == current.next ? null : current.next.next;
            return;
        }
        nodesExamined++;
        current = current.next;
    }

    throw new IndexOutOfBoundsException();
}

It passes a few tests, but probably has a few bugs left. Is the overall approach correct, though? It feels like I'm over-complicating.

Answer 1

I wouldn't go as far as to say you're wrong, as the basic functionality is there. I do however recommend rather using an iterator and going about it that way.

Have a look at this code here, which implements a linked list using an iterator for all search / remove functionality. You can also expand it from there using some fail-fast code to make it a bit cleaner.

Answer 2

(edit: to clarify, nothing wrong with an iterative approach, just thinking out aloud.)

Since it's a singly-linked list, you should be able to express the remove operation quite succinctly using a recursive function taking a node and an index, and returning a node. As a rough outline, you'd:

1. check that the passed node is not null (throwing an exception otherwise)
2. then branch on the value of index: if it is 0, return the node in next; otherwise, call the recursive function again with the next node and index decremented by 1, and assign the result to next.

Just a hunch, might still have a fencepost error in there..

Answer 3

Why not use a for loop to control exit?

@Override
public void remove(final int index) throws IndexOutOfBoundsException {

    if (first == null) {
        throw new IndexOutOfBoundsException();
    }

    int nodesExamined = 0;

    for( Node<T> current = first; current != null; current = current.next ){
       if( nodesExamined == index ){
           current.next = current.next == null ? null : current.next.next;
           return;
       }
       nodesExamined++;
    }

    throw new IndexOutOfBoundsException();
}

This is assuming you don't have any sort of linkedList.size() function available to you. If you did, you could place a check at the beginning to make sure your index < your size.

Answer 4

How about simplifying that equals function? You said:

public boolean equals(Object obj) {
    if (this == obj)
        return true;
    if (obj == null)
        return false;
    if (getClass() != obj.getClass())
        return false;
    Node<T> other = (Node<T>) obj;
    if (datum == null) {
        if (other.datum != null)
            return false;
    } else if (!datum.equals(other.datum))
        return false;
    if (next == null) {
        if (other.next != null)
            return false;
    } else if (!next.equals(other.next))
        return false;
    return true;

when you could have said:

  public boolean equals(Object obj) {
    Node<T> other = (Node<T>) obj;
    return (other != null) &&
         (getClass() == other.getClass()) &&
         ((datum == other.datum) || datum.equals(other.datum)) &&
         ((next == other.next) || next.equals(other.next));
  }

Note that the x == y || x.equals(y) handles the null case and also shortcircuits quicky for refs to the same object.