链表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 ii上使用Applesoft BASIC)，并获得了计算机科学学位。我目前是一名软件测试人员，并计划在某个时候成为一名开发人员。所以我问题的第二部分是:我是在欺骗自己，以为这就是我擅长的工作，还是说几乎每个人都觉得这类问题很有挑战性?有些东西告诉我，即使是经验丰富的开发人员，面对实现这种方法，也会发现它具有挑战性。

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

Answer 1

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

• 我认为你的currentNode == null的情况应该在开始时照顾，然后返回。我不喜欢所有东西都在if (currentNode != null)里面
• 你应该在某个地方跟踪链表的大小，这样你就可以很容易地检查i> listrongize
• 我不会费心将" I -1"重命名为targetIndex
• 不创建newNode直到你需要
• 写单元测试，然后你可以很容易地改变周围的东西，并知道你的实现仍然有效。
• 不要简单地忽略非法参数。如果索引i <0或> size，抛出一个IllegalArgumentException或IndexOutOfBoundsException(感谢@JB Nizet)

Answer 2

我建议您从编写一些单元测试开始。特别是，尝试在列表末尾之外添加一个节点，看看会发生什么。;)

我认为大多数开发人员会发现写一个LinkedList很困难，因为a)有很多实现它的方法，b)它不是你通常会自己写的东西。您通常会使用现有的实现之一。;)

作为练习，这仍然是一个好主意。我建议你阅读一下内置LinkedList的代码，并考虑一下你可以如何做不同的事情。例如，你如何简化它可以作为一个开始。

Answer 3

这个实现效率不高，但部分原因是add(i, x)操作在普通链表上效率不高。链表不是用于随机访问的。我想如果你创建一个哈希表或者别的什么你可能会创建一个更有效的列表索引。以Map为例。然后你的map.ContainsKey(i-1) map.get(i-1)的插入例程(显然有一个i=0的特殊情况)，你马上就有了先前的索引。如果i = 0，而你没有那个索引的键，那么你马上就知道出错了。如果没有太多的冲突，Map在理论上是O(1)，所以这比每次迭代列表要有效得多(但要花费一些磁盘空间)。这还是要看情况，因为纯链表对于add(i, x)来说效率不是很高。

我不是特别喜欢这个方法，因为如果你输入add(32, x)，而列表中只有15个项目，它就会无声地失败。它至少应该抛出一个异常、返回false或其他什么，以表明插入失败。

也可以合并这两个特殊情况。假设newNode. setnext (NULL)工作，您只需要检查i==0，然后您可以执行newNode. setnext (head)， head=newNode，因为无论列表是空的还是不工作。如果列表为空，则将下一个指针设置为NULL。这至少消除了重复的代码。

花一个星期似乎有点多，但有些人有很多麻烦，首先包装他们的头在指针(好吧，在javaspeak类引用....)。事实上，你最终得到了一些工作，这是朝着正确方向迈出的一大步。