双链表不导入

Question

我目前正致力于在 java 中实现双向链表的 Junit 测试。我了解它需要如何工作一遍又一遍地绘制图片，但我无法让我的 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() 方法的变体来提供帮助。

任何见解都会对我有很大帮助。我还有更多测试用例可以添加到 post。

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 覆盖该分配，它是空的。

你可能想说 last = first 那里。

试试这个测试用例：

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

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

双链表不导入

Doubly Linked List no imports

java

doubly-linked-list