链表的大小

Question

我是 Java 的新手，我得到了这个 Linkedlist 设置，我需要使用递归或 while 循环来编写 return 大小的大小函数链表。我想当这个链表设置没有初始化 Node、head 等时，我对如何执行大小函数感到很困惑。

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

改成：

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;
}

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

Answer 2

在您当前的表述中，您的 LinkedList 实例实际上是节点和列表。没关系，但是这意味着列表中没有区分"head" ...

在此上下文中，解决方法是更改：

    Node Current = head;

到

    LinkedList current = this;

（是的，size 变量应以 1 开头。在此公式中，空列表由 null 表示。如果您调用 size() 在 LinkedList 的实例上，则列表的大小必须至少为 1。）

@Konrad 说 "A list itself should encapsulate the nodes."

实际上这是一种设计选择。如果您遵循 OO 设计原则，那么它应该遵循。但是，在某些情况下，您实际上并不想这样做。有时需要 "sacrifice" 抽象以获得更好的性能或降低内存利用率。

Answer 3

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

    return size;
}

Answer 4

计算链表大小的另一种方法（如您创建的链表）是使用递归。只有两种情况：

一个没有 next 的链表有大小 1 - 只有它本身
带有 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 class，因为每个 LinkedList 对象都代表其自身（一个单一值）和所有后续值（值列表）。从这个角度来看，我们必须从 "here" 开始循环，直到无处可去。

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

链表的大小

size of linkedList

java

linked-list