java - 链接列表 add(i, x) 方法的代码审查

Question

我目前正在尝试温习 ADT 实现，特别是链接列表的实现(我正在使用 Java 5 来执行此操作)。

我有两个问题:

(1) 我为 add(i, x) 编写的这个实现正确且高效吗？

public void add(int i, Object x) {

    // Possible Cases:
    //
    //     1. The list is non-empty, but the requested index is out of
    //        range (it must be from 0 to size(), inclusive)
    //
    //     2. The list itself is empty, which will only work if i = 0
    //
    // This implementation of add(i, x) relies on finding the node just before
    // the requested index i.

    // These will be used to traverse the list
    Node currentNode = head;
    int indexCounter = 0;

    // This will be used to mark the node before the requested index node
    int targetIndex = i - 1;

    // This is the new node to be inserted in the list
    Node newNode = new Node(x);

    if (currentNode != null) {

        while (indexCounter < targetIndex && currentNode.getNext() != null) {

            indexCounter++;
            currentNode = currentNode.getNext();
        }

        if (indexCounter == targetIndex) {

            newNode.setNext(currentNode.getNext());
            currentNode.setNext(newNode);

        } else if (i == 0) {

            newNode.setNext(head);
            head = newNode;
        }

    } else if (i == 0) {

        head = newNode;
    }     
}

(2) 我发现这种方法实现起来非常具有挑战性。说实话，我花了好几天的时间。这很难承认，因为我喜欢编程，并认为自己在多种语言和平台上处于中级水平。我从 13 岁起就开始编程(Apple IIc 上的 Applesoft BASIC!)，并获得了计算机科学学位。我目前担任软件测试员，并计划在某个时候成为一名开发人员。所以我的问题的第二部分是:我是在欺骗自己，认为这是我擅长的工作类型，还是几乎每个人都觉得这种问题具有挑战性？我知道，即使是经验丰富的开发人员，在面临实现这种方法时也会发现它具有挑战性。

感谢您对第二部分的反馈和建议。

Answer 1

我认为这是一个好的开始......一些建议:

• 我认为你的 currentNode == null 情况应该在开始时处理，然后返回。我不喜欢所有内容都在“if (currentNode != null)”内
• 您应该在某处跟踪链接列表的大小，以便您可以轻松检查 i > list_size
• 我不会费心将“i-1”重命名为 targetIndex
• 除非需要，否则不要创建 newNode
• 编写单元测试，然后您就可以轻松地进行更改并知道您的实现仍然有效。
• 不要简单地忽略非法论点。如果索引 i < 0 或 > size，则抛出 IllegalArgumentException 或 IndexOutOfBoundsException(感谢 @JB Nizet)