将多个项目添加到链表

Question

我正在创建链表的实现，但在使用 add 方法时遇到了问题。在使用多个条目对其进行测试后，我的 size() 方法总是 returns 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

代替return size(currentNode.next);试试这个return count + size(currentNode.next);

它将解决计数问题，因为列表没问题。但是乍一看你的代码似乎列表添加代码也有问题。

Answer 2

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

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

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

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

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

至

return 1 + size(currentNode.next);

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

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

你应该制作 add 的 2-arg 版本和 size private 的 1-arg 版本，因为你不想将列表的内部暴露给public（事实上，Node class 也应该是私有 class）。

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

将多个项目添加到链表

Adding Several Items To A Linked-List

java

linked-list

data-collection