如何在不使用构造函数的情况下在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

需要对代码进行一个更改:您希望新链接以"next"的形式指向您的旧头部(而不是反过来)，因为您希望将其插入到开头。

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

另外，您需要更改您的测试，因为现在您将字符串与链接实例进行比较，而不是字符串与字符串

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

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

Answer 2

您不需要构造函数将null, 0和false分配给对象字段。字段自动获得这些值。只要删除只做这种赋值的构造函数，执行起来就不会有任何区别。

您也可以直接在声明中指定其他默认值，如int a = 17，并且您也可以包含int b = a + 1这样的表达式，假设a字段之前已经声明过。但是，您不能为不同的实例传递必须具有不同值的参数。这就是构造函数的作用。

您可能仍然存在其他错误，但这将不是构造函数的责任。

大多数情况下，开发人员只是使用现成的解决方案，LinkedList。