代码审查链接列表中添加（I，X）方法

我目前正在努力刷上ADT实现，专门为链表（我使用Java 5的做到这一点）的实现。代码审查链接列表中添加（I，X）方法

我有两个问题：

（1）这是实现我为加法书面（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岁起就开始编程（Applesoft BASIC在Apple IIc上！）并拥有CS学位。我目前是一名软件测试员，并计划在某个时候成为开发人员。所以我的问题的第二部分是：我是否在愚弄自己，这是我擅长的工作类型，还是几乎每个人都觉得这种问题具有挑战性？有些事情告诉我，即使经验丰富的开发人员，面对实施这种方法，会发现它具有挑战性。

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

来源

2011-07-08 dvanaria

@dvanaria：我认为这个问题更适合http://codereview.stackexchange.com。 –

属于http://codereview.stackexchange.com/ –

好的谢谢，我从来没有听说过codereview.stackexchange，它听起来像一个更好的地方。我会考虑现在移动它。 – dvanaria

我认为这是一个良好的开端...几点建议：

我觉得你currentNode == NULL的情况下，应采取照顾起步，然后返回。我不喜欢里面的所有内容“if（currentNode！= null）”
您应该跟踪链接列表的大小，以便您可以轻松地检查是否我> list_size
我wouldn 't打扰重命名“i-1”到targetIndex
不要创建newNode，直到你需要
编写单元测试，然后你可以很容易地改变事物并知道你的实现仍然有效。
不要简单地忽略非法参数。如果索引i < 0或>大小，抛出IllegalArgumentException或IndexOutOfBoundsException异常（感谢@JB Nizet）

来源

2011-07-08 20:00:58 dgrant

好的，谢谢，我确实写了一个单元测试，试图打所有的边界情况。我尝试在允许的范围外添加元素，将元素添加到空列表中，在非空列表范围内添加元素，在位置0添加元素以及添加元素i = size（）（即，在当前列表）。 – dvanaria

另外，不要简单地忽略非法参数。如果索引i < 0 or >大小，请抛出IllegalArgumentException。否则，调用者不知道没有任何东西被添加到列表中。 –

我大多数人都同意，但我不同意不将i-1重命名为targetIndex。我会说改变targetIndex priorindex或priorToInsertionIndex，因为它使你的意图更清晰。 targetIndex具有误导性，i-1根本不清楚。 – Cervo

我建议你先写一些单元测试。特别是，尝试在列表末尾添加一个节点，看看会发生什么。 ;）

我想大多数开发商会发现写一个LinkedList困难的，因为一）有实现它很多方面和b）它不是你通常会自己写。您通常会使用其中一个现有的实现。 ;）

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

来源

2011-07-08 20:00:06

此实现的效率不高，但是这是部分因为操作加（I，x）是不高效的一个正常的链表。链接列表不适用于随机访问。我想如果你创建了一个哈希表或者你可能创建一个更有效的索引到列表中。例如考虑地图。然后你的插入例程（显然是i = 0的特殊情况）map.ContainsKey（i-1）map.get（i-1），你立即拥有了先前的索引。如果我！= 0，并且你没有那个索引的键，那么你马上就知道一个错误。如果没有太多碰撞，Map理论上是O（1），所以这比每次遍历列表更有效率（但是以一些磁盘空间为代价）。再次，它真的取决于，因为纯链接列表不是非常有效的添加（i，x）。

我并不特别喜欢这种方法，因为如果你说add（32，x）并且列表中只有15个项目，它会默默地失败。它至少应该抛出一个异常，返回false或其他内容，以表明插入失败。

你也可以合并这两种特殊情况。假设newNode.setNext（NULL）有效，你只需要一次检查i == 0，然后你可以执行newNode.setNext（head），head = newNode，因为这个列表是否为空或者是否为空。如果列表为空，则将下一个指针设置为NULL。这至少消除了重复的代码。

花了一个星期看起来似乎有点多，但有些人首先围绕着指针（在javaspeak中的良好的类引用....），有很多麻烦。事实上，你最终得到的东西是正确的方向迈出的一大步。

来源

2011-07-08 20:04:44 Cervo

代码审查链接列表中添加（I，X）方法

回答

相关问题