如何在不使用构造函数的情况下手动实现 Java 中的链表？

Question

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

public LinkList() {
    Link = null;
}

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

我有一个名为 Link 的 class，其中包含以下代码，请注意没有像上面显示的那样的任何构造函数：

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 class，其中包含以下代码：

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

需要对您的代码进行更改：您希望新的 link 指向您的旧头部 "next"（而不是相反），因为您希望将其插入开头.

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 方法）。

Answer 2

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

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

您可能仍然存在其他错误，但这不应该归咎于构造函数。

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

如何在不使用构造函数的情况下手动实现 Java 中的链表？

How to manually implement a Linked List in Java without using a Constructor?

java

linked-list

singly-linked-list