Java实现链式位置列表addBetween添加元素异常排查

addBetween方法核心问题 #

• 新节点构造参数顺序传反：Node类构造函数定义为Node(E element, Node next, Node before)，第二个参数接收后继节点、第三个参数接收前驱节点。原代码创建新节点时写为new Node(e, pred, succ)，把前驱节点传给了next字段、后继节点传给了before字段，新节点前后指针完全颠倒，直接造成链表断链。
• 关联逻辑破坏哨兵结构：当前实现用固定头哨兵header、尾哨兵trailer作为链表锚点，两个哨兵初始化后不能修改指向。原代码insertFirst、insertLast直接重新赋值header/trailer变量，彻底打乱链表基础结构，导致传入addBetween的前驱、后继节点本身就是非法值。

正确的addBetween实现 #

private Position<E> addBetween(E e, Node pred, Node succ) {
    // 严格匹配Node构造参数顺序：元素值、后继节点、前驱节点
    Node newest = new Node(e, succ, pred);
    pred.setNext(newest);
    succ.setBefore(newest);
    size++;
    return newest;
}

必须同步修正的关联方法 #

如果只改addBetween，原有错误的头尾插入逻辑依然会导致功能异常，需要把插入逻辑全部改为基于哨兵+addBetween实现，全程不修改header、trailer的指向：

• 修正头插方法：

@Override
public Position<E> insertFirst(E e) throws IllegalValueException {
    // 头插位置：头哨兵 -> 第一个元素，前驱为header，后继为header原下一个节点
    return addBetween(e, header, header.getNext());
}

• 修正尾插方法：

@Override
public Position<E> insertLast(E e) throws IllegalValueException {
    // 尾插位置：最后一个元素 -> 尾哨兵，前驱为trailer原前一个节点，后继为trailer
    return addBetween(e, trailer.getBefore(), trailer);
}

• 修正基础位置查询方法，避免后续遍历、校验失败：

@Override
public Position<E> first() throws EmptyListException {
    if (isEmpty()) throw new EmptyListException("List is Empty");
    return position(header.getNext());
}

@Override
public Position<E> last() throws EmptyListException {
    if (isEmpty()) throw new EmptyListException("List is Empty");
    return position(trailer.getBefore());
}

// 修正Node类的element方法，原实现直接返回null会导致取元素失败
@Override
public E element() throws InvalidPositionException {
    if (next == null) throw new InvalidPositionException("Position is no longer valid");
    return element;
}

实现哨兵双向链表的核心原则：header和trailer是初始化后永久存在的锚点，永远不存储业务元素、永远不被重新赋值，所有元素都插在两个哨兵之间的区域，插入删除只修改普通业务节点的前后指针。

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