0

我正在为一个作业编写一个 LinkedList 类,我正在编写我的插入方法,并且想知道是否可以查看它。

private Node first;     // start of the list

private class Node {
    private Item item;
    private Node next;
}

public boolean insert(Item item) {
    // add item to list if it doesn't already exist
    // return true if a new Node is created, otherwise false
    if ( first.next == null && first.item == item) {
        return false;
    }
    Node ptr = first;
    while (ptr.next != null) {
        if (ptr.item == item) {
            return false;
        }
        ptr = ptr.next;
    }
    Node oldFirst = first;
    first = new Node();
    first.item = item;
    first.next = oldFirst;
    return true;
}

在大多数情况下,我认为这没关系,但每次我尝试跟踪插入方法时,我最终都会让自己感到困惑并弄乱所有参考更改。有人可以告诉我我做得对吗?任何其他改进也将不胜感激。

4

2 回答 2

0

我会考虑编写一个额外的函数来检查项目是否已经在列表中。这将使插入功能更加清晰,整个参考变化只会在那里。还有你的第一个测试:

if ( first.next == null && first.item == item) {
    return false;
}

除了 while 循环的第一次迭代之外什么都不做。

您绝对应该首先初始化,以免像@threenplusone 所说的那样抛出 NullPointerExcpetion 或检查是否:first == null。(如果 first 为空,则 while 循环中的第一个 ptr.next 会引发 NPE)此外,您应该按照 @Thilo 所说的那样比较您的项目。

其余的我认为是正确的。

于 2012-11-15T06:48:13.057 回答
-1

您的 insert 方法不是 OO - 您正在使用while循环遍历列表,因此此方法可能是一种static方法(如果您还传入了第一个节点)。

更优雅的方式是:

在伪代码中:

insert(item) {
    if (next == null)
        add item to "this" // we are at end of list
    else
        next.insert(item) // hand item to the next node
}
于 2012-11-15T05:12:09.353 回答