size of linkedList

Question

我是Java的新手，我得到了这个Linkedlist设置，我需要使用递归或while循环来编写返回Linkedlist大小的size函数。我想我很困惑，如何做大小函数时，这个链表设置不初始化节点，头等。

package list;
public class LinkedList {
  public int value;
  public LinkedList next;
  public LinkedList (int value, LinkedList next) {
    this.value = value;
    this.next = next;
  }
  public static LinkedList list () {
    return new LinkedList(1, new LinkedList(2, new LinkedList(3, null)));
  }
  public int size () {
    int size = 0;
    Node Current = head;
    while(Current.next != null)
    {
      Current = Current.next;
      size++;     
    }
    return size;
  }
}

Answer 1

在您当前的公式中，您的LinkedList实例实际上是节点和列表。这没关系，但这意味着列表中没有明显的"头"…

在这种情况下，修复方法是修改:

    Node Current = head;

    LinkedList current = this;

(是的，size变量应该从1开始。在此公式中，空列表用null表示。如果在LinkedList的实例上调用size()，那么列表的大小必须至少为1。

---

@Konrad声明"列表本身应该封装节点。"

实际上这是一个设计选择。如果您遵循OO设计原则，那么应该遵循。然而，在某些情况下，你不希望这样做。有时为了获得更好的性能或减少内存使用，需要"牺牲"抽象。

Answer 2

在您创建的链表中计算大小的另一种方法是使用递归。只有两种情况:

1. 没有next的链表大小为1 -只是本身
2. 带有next的链表的大小为1加上next的大小。

因此，我们有以下函数:

public int size(){
    if(next == null){
        return 1;
    } else {
        return 1 + next.size();
    }
}

这可以用一个三元操作符写得非常简洁:

public int size(){
    return next != null ? 1 + next.size() : 1;
}

对于迭代解，不需要使用Node类，因为每个LinkedList对象既表示自身(一个值)，也表示后面的所有值(一个值列表)。从这个角度来看，我们必须从"这里"开始循环，直到无处可去。

public int size () {
   int size = 1;
   LinkedList Current = this;
   while(Current.next != null){
     Current = Current.next;
     size++;     
   }
   return size;
}

Answer 3

public int size()
{
    int size = 1;
    LinkedList head = this;
    while (head.next != null)
    {
        head = head.next;
        size++;
    }
    return size;
}

Answer 4

改成:

public int size () {
    int size = 0;
    // set the head as current note
    Node current = head;
    // while a current node is set
    while(current != null)
    {
      // increment site
      size++;     
      // and set the next as current node
      current = current.next;
    }
    return size;
}

列表本身不是列表。它是一个节点链表。列表本身应该封装节点。