我目前正在尝试温习 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!),并获得了计算机科学学位。我目前担任软件测试员,并计划在某个时候成为一名开发人员。所以我的问题的第二部分是:我是在欺骗自己,认为这是我擅长的工作类型,还是几乎每个人都觉得这种问题具有挑战性?我知道,即使是经验丰富的开发人员,在面临实现这种方法时也会发现它具有挑战性。
感谢您对第二部分的反馈和建议。
最佳答案
我认为这是一个好的开始......一些建议:
- 我认为你的 currentNode == null 情况应该在开始时处理,然后返回。我不喜欢所有内容都在“if (currentNode != null)”内
- 您应该在某处跟踪链接列表的大小,以便您可以轻松检查 i > list_size
- 我不会费心将“i-1”重命名为 targetIndex
- 除非需要,否则不要创建 newNode
- 编写单元测试,然后您就可以轻松地进行更改并知道您的实现仍然有效。
- 不要简单地忽略非法论点。如果索引 i < 0 或 > size,则抛出 IllegalArgumentException 或 IndexOutOfBoundsException(感谢 @JB Nizet)
关于java - 链接列表 add(i, x) 方法的代码审查,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6629697/