java - 双链表不导入

Question

我目前正在从事 Junit 测试，以便在 Java 中实现双向链表。我了解它需要如何一遍又一遍地绘制图片，但我无法让我的 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);
}

我觉得我现在拥有的东西让我接近了，但是 我删除了 = 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 的第二个元素，依此类推。