双链表没有进口

Question

我目前正在进行Junit测试，以便在java中实现Doubly Linked列表。我理解它需要一遍又一遍地处理绘制的图片，但我不能让我的removeFirst方法工作。 addLast();工作直到removeFirst被调用。

private Link<I> first;
private Link<I> last;

public boolean isEmpty() {
    return size() == 0;
}

public int size() {
    int count = 0;
    Link<I> aLink = first;
    while (aLink != null) {
        count++;
        aLink = aLink.getAfter();
    }
    return count;
}

public I get(int index) {
    Link<I> aLink = first;
    int count = 0;
    while (count != index) {
        aLink = aLink.getAfter();
        count++;
    }
    return aLink.getItem();

}

public void addLast(I anItem) {
    Link<I> aLink = new Link<I>(anItem);
    if (isEmpty()) {
        first = aLink;
        first = last;
    } else {
        last.setAfter(aLink);
        aLink.setBefore(last);
        last = aLink;

    }
}

public void addFirst(I anItem) {
    Link<I> aLink = new Link<I>(anItem);
    if (isEmpty()) {
        first = aLink;
        last = first;
    } else {
        aLink.setAfter(first);
        first.setBefore(last);
        first = aLink;
    }

}

public I removeFirst() {
    I removed = first.get(0);
    if(size()==3) {
        first = first.getAfter();
        first.setBefore(null);
        first.setAfter(last);
        return removed;
    } else if(size()==2) {
        first = first.getAfter();
        first.setBefore(null);
        first.setAfter(null);
        return removed;
    }else {
        first = null;
        first.setBefore(null);
        first.setAfter(null);
        return removed;
    }

}

public I removeLast() {
    I removed = last.getItem();
    if (isEmpty()) {
        removed = null;
        return removed;
    } else {
        last = last.getBefore();
        removed = last.getItem();
        return removed;
    }

}

}

public class Link<I> {
private Link<I> after;
private Link<I> before;
private I item;

public Link(I anItem) {
    item = anItem;
}

public Link<I> getAfter(){
    return after;
}

public void setAfter(Link<I> aLink) {
    after = aLink;
}

public Link<I> getBefore(){
    return before;
}

public void setBefore(Link<I> aLink) {
    before = aLink;
}

public I getItem() {
    return item;
}

public void setItem(I anItem) {
    item = anItem;
}

}

这是测试单元

void testAddLast() {
    notes.addLast("do");
    notes.addLast("re");
    notes.addLast("mi");
    String note = notes.removeFirst();
    assertTrue(notes.size()==2);
    assertTrue("do".equals(note));
    note = notes.removeFirst();
    assertTrue(notes.size()==1);
    assertTrue("re".equals(note));
    note= notes.removeFirst();
    assertTrue(notes.isEmpty());
    assertTrue("mi".equals(note));
    note = notes.removeFirst();
    assertTrue(note == null);
    assertTrue(notes.isEmpty());
    assertTrue(notes.size() == 0);
}

我觉得我现在拥有的是让我接近，但I removed = first.get(0);不断给我一个空指针异常。两个多星期前，我在这项任务中获得了额外的时间，而且我仍然非常努力。我在调试器之后尝试了一堆removeFirst（）方法的变体来帮助。

任何见解都会对我有所帮助。我有更多的测试用例可以添加到帖子中。

Answer 1

这似乎是给你带来麻烦的方法

public I removeFirst() {
    I removed = first.get(0);
    if(size()==3) {
        first = first.getAfter();
        first.setBefore(null);
        first.setAfter(last);
        return removed;
    } else if(size()==2) {
        first = first.getAfter();
        first.setBefore(null);
        first.setAfter(null);
        return removed;
    }else {
        first = null;
        first.setBefore(null);
        first.setAfter(null);
        return removed;
    }

}

你说当你调用first.get(0)时你得到一个NullPointerException。这意味着first为空。

这是添加节点的方式：

public void addLast(I anItem) {
    Link<I> aLink = new Link<I>(anItem);
    if (isEmpty()) {
        first = aLink;
        first = last;
    } else {
        last.setAfter(aLink);
        aLink.setBefore(last);
        last = aLink;
    }
}

您分配给first aLink，然后用last覆盖该赋值，该值为null。

你可能意味着在那里说last = first。

试试这个测试用例：

void testAddOne() {
    assertTrue(notes.count() == 0);
    notes.addLast("do");
    assertTrue(notes.count() == 1);
}

通常，您的测试用例非常复杂。您希望更简单的测试来检查操作的后置条件。例如，插入一个元素应该将计数增加一。删除元素应该将计数减少一个。添加两个元素，check get返回第一个索引0，第二个返回索引1，依此类推。