java - 将多个项目添加到链接列表中

Question

我正在创建链表的实现，但在使用 add 方法时遇到问题。在使用多个条目对其进行测试后，我的 size() 方法始终返回 1。我做错了什么。

public class Node {

    public int data;
    public Node next;

       public Node(int data){
        this.data = data;
    }       
}


public class LinkedList {

    public Node first;
    public Node last;

    public LinkedList(){
        first = null;
        last = null;
    } 

    public void add(int data){    
        Node newNode = new Node(data);
        if(first == null){
            first = newNode;        
        } else {
            add(first, newNode);
        }                  
    }

    public void add(Node currentNode, Node newNode){

        if(currentNode.next != null){
            add(currentNode.next, newNode);
        }
        currentNode.next = newNode;
    }   
        public int size(){        
        if(first == null){
            return 0;
        }
        else{
            return size(first);
        }        
    }
    public int size(Node currentNode){
        //Count Starts At One Because First = 1.
        int count = 1;        
        if(currentNode == null){
            return count;
        }
        else {
            count++;
            return size(currentNode.next);
        }             
    }
}

Answer 1

您忘记了 add 的 2-arg 形式中的 else。就目前情况而言，

if(currentNode.next != null){
    add(currentNode.next, newNode);
}
currentNode.next = newNode;

始终将新节点添加到列表中的第一个和所有其他节点。如果 currentNode.next = newNode 出现在 else 子句中，则只会将其正确添加到末尾。

此外，您的 size 方法始终返回 1，因为最终分支始终返回 1。要解决此问题，请更改

count++;
return size(currentNode.next);

至

return 1 + size(currentNode.next);

此外，将 return count; 替换为 return 1;。

基本上，您的实现几乎是正确的。 size(Node) 应返回从该节点开始的列表的大小。如果该节点没有 next，则大小为 1。否则，其当前节点 (1) + 剩余尾部的大小。

您应该将 add 的 2-arg 版本和 size 的 1-arg 版本设为 private，因为您不想向公众公开列表的内部结构(事实上，Node 类也应该是私有(private)类)。

此外，您永远不会使用类的 last 字段。您可以删除它，也可以使用它来完全避免 add 中的递归需要。在后一种情况下，您必须在每次添加新内容时正确更新它。