调试链表add(int index, T data)方法：未触发预期的IndexOutOfBoundsException

调试链表的add(int index, T data)方法时，预期传入非法索引会抛出IndexOutOfBoundsException，但方法开头的条件判断未能捕获该异常，导致以下测试用例失败：

@Test(expected = IndexOutOfBoundsException.class)
public void testDSListAddInsertInvalidIndexHigh2() {
    DSListInterface<String> list = createStringList(3);
    list.add(3, "Hello");
}

原异常捕获条件判断代码 #

if(index < 0) throw new IndexOutOfBoundsException(); // invalid index, must be greater than zero 
if(isEmpty()) throw new IndexOutOfBoundsException();
if(index > size() + 1) throw new IndexOutOfBoundsException();

完整DSList类代码 #

public class DSList<T> implements DSListInterface<T> {
    private DSNode<T> first;
    
    public DSList() {
        super();
        this.first = null;
    }

    public void add(int index, T data) {
        if(index < 0) throw new IndexOutOfBoundsException(); // invalid index, must be greater than zero
        if(isEmpty()) throw new IndexOutOfBoundsException();
        if(index > size() + 1) throw new IndexOutOfBoundsException();
         
        DSNode<T> newNode = new DSNode<>();
        newNode.setData(data);
        
        if(index == 0) {
            newNode.setNext(first);
            first = newNode;
        }
        else {
                DSNode<T> beforeNode = null;
                DSNode<T> afterNode = first;
                
                 // empty list
        
                for(int i = 0; i < index; i++) {
                    if(afterNode == null) {
                        throw new IndexOutOfBoundsException(); // invalid index, too big
                    }
                    else {
                        if(i < index -1) {
                            beforeNode = afterNode.getNext();
                        }
                        afterNode = afterNode.getNext();
                    }
                }
                beforeNode.setNext(newNode);
                newNode.setNext(afterNode);
        }      
    }
}

DSNode节点类代码 #

public class DSNode<T> {
    private T data;
    private DSNode<T> next;
    
    public DSNode() {
        super();
        this.data = null;
        this.next = null;
    }
    
    public T getData() {
        return this.data;
    }
    
    public void setData(T data) {
        this.data = data;
    }
    
    public DSNode<T> getNext() {
        return this.next;
    }
    
    public void setNext(DSNode<T> next) {
        this.next = next;
    }
}

问题分析与修复方案 #

1. 索引判断逻辑错误

测试用例中，列表大小为3，调用add(3, "Hello")时，原条件index > size() + 1即3 > 3+1不成立，因此未触发异常。但实际上，链表插入的合法索引范围是0 ≤ index ≤ size()（index=size()时表示插在末尾），当index > size()时即为非法索引。

同时，原代码中if(isEmpty()) throw new IndexOutOfBoundsException();完全错误——空列表允许插入index=0的位置，这个条件会直接阻断空列表的插入操作。

修正后的索引判断条件：

// 合并判断，覆盖所有非法索引情况
if (index < 0 || index > size()) {
    throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size());
}

2. 插入逻辑的空指针隐患

原代码中else分支的循环逻辑存在错误，当index=1时，beforeNode会保持为null，执行beforeNode.setNext(newNode)会抛出空指针异常。正确的遍历逻辑应该是找到目标位置的前一个节点：

修正后的else分支代码：

else {
    DSNode<T> beforeNode = first;
    // 遍历到目标位置的前一个节点
    for (int i = 0; i < index - 1; i++) {
        beforeNode = beforeNode.getNext();
        // 中途遇到null说明索引超出范围
        if (beforeNode == null) {
            throw new IndexOutOfBoundsException();
        }
    }
    DSNode<T> afterNode = beforeNode.getNext();
    beforeNode.setNext(newNode);
    newNode.setNext(afterNode);
}

内容的提问来源于stack exchange，提问作者Jonas Calderhead