java - 如何在Java中不使用构造函数手动实现链表？

Question

我意识到已经有一些很好的线程讨论如何在 Java 中实现链表，但是我似乎找不到不使用这样的构造函数的线程，

public LinkList() {
    Link = null;
}

或者类似的东西。但是，我没有在代码中这样做，因此我在编写一些方法时遇到了麻烦。

我有一个名为 Link 的类，其中包含以下代码，请注意，没有任何类似于上面显示的构造函数:

public class Link {
private Link next = null;
private String value = null;

public Link getNext(){
    return next;
}

public void setNext(Link nextLink){
    next = nextLink;
}

public String getValue(){
    return value;
}

public void setValue(String aValue){
    value = aValue;
}
}

然后我有我的 LinkedList 类，其中包含以下代码:

public class LinkedList {
private Link head = null;
private Link tail = null;

public Link getHead(){
    return head;
}

public void setHead(Link aLink){
    head = aLink;
}

public Link getTail(){
    return tail;
}

public void setTail(Link aLink){
    tail = aLink;
}

public boolean isEmpty(){
    return(head == null && tail == null);
}

public void addLast(String aString){
    Link link = new Link();
    link.setValue(aString);
    //tail.setNext(link);
    if(isEmpty()){
        head = link;
    }else{
        tail.setNext(link);
    }
    tail = link;

    }

public void addFirst(String aString) {
    Link link = new Link();
    link.setValue(aString);

    if(isEmpty()){  
        tail = link;
    }else{
        head.setNext(link);
    }
    head = link;        
}

public Link removeFirst(){
    Link temp = head;
    head = temp.getNext();
    temp.setNext(null);

    return temp;
}

}

我的 addFirst 方法和我的 isEmpty 方法似乎都有效，但我的 addLast 和 removeFirst 方法不是。我画了图，查看了伪代码，并在互联网上进行了搜索，但我似乎无法弄清楚这一点。

我需要知道如何让我的 addLast 和 removeFirst 方法正常工作，而不必像我保留的所有其他示例代码一样在开头添加构造函数看见了。

以下是他们需要通过的测试:

    @Test
public void testRemoveFirst(){
    list.addFirst("three");
    list.addFirst("two");
    list.addFirst("one");
    assertTrue("one".equals(list.removeFirst()));
    assertTrue("two".equals(list.removeFirst()));
    assertTrue("three".equals(list.removeFirst()));
}

@Test
public void testAddLast(){
    list.addFirst("three");
    list.addFirst("two");
    list.addFirst("one");
    assertTrue( "three".equals(list.removeLast()));
    assertTrue( "two".equals(list.removeLast()));
    assertTrue( "one".equals(list.removeLast()));
    assertNull(list.removeLast());
}

Answer 1

您的代码需要进行一项更改:您希望新链接作为“下一个”指向您的旧标题(而不是相反)，因为您想将其插入到开头。

public void addFirst(String aString) {
        Link link = new Link();
        link.setValue(aString);

        if (isEmpty()) {
            tail = link;
        } else {
            link.setNext(head);
        }
        head = link;
    }

此外，您需要更改测试，因为现在您将 String 与 Link 实例进行比较，而不是 String 与 String

    assertTrue("one".equals(list.removeFirst().getValue()));
    assertTrue("two".equals(list.removeFirst().getValue()));
    assertTrue("three".equals(list.removeFirst().getValue()));

在这些更改之后，测试通过了(第一个，您没有为第二个实现removeLast 方法)。