java - 集合中的递归方法

Question

我正在尝试学习并有一个关于集合中的递归方法的问题，我在这里读到:

“在使用递归方法实现集合类时，我们通常必须为每个操作编写一对方法。第一个方法是接口(interface)中指定的公共(public)方法。它可以迭代或递归地编写。它是迭代编写的，它只是调用...第二种方法是完成所有工作的私有(private)静态方法。

例如，假设我们使用一个 front 实例变量和一个 priorityComparator 实例变量，通过链表实现一个通用优先级队列(LN 将值存储为一个对象)。我们将使用以下一对方法在此类中实现 add 方法。”

引用的代码是:

public void add (Object o)
  {front = add(front,o);}

  private static LN add (LN l, Object o)
  {
    if (l == null || priorityComparator.compare(l.value,o) < 0)
      return new LN(value,l);
    else {
      l.next = add(l.next, o);
      return l;
    }
  }

以上信息和代码的来源在这里-> link

可悲的是我只找到了一个来源 :(

QUESTION1:我想知道这样的写法对某个集合的实现有什么好处？

因此，根据示例，我编写了如下实现的 LinkedList 方法:

//insertion....
public void insert(E data) {
    first = insertEnd(first, data);
    last = getLast();
    //length++;
}

private static <E> Node insert(Node head, E data) {
    if (head == null) {
        return new Node(data);
    } else {
        head.setNext(insert(head.getNext(), data));
    }

    return head;
}

public void printList() {
    printList(first);
    System.out.println();
}

private static void printList(Node head) {
    if (head == null) {
        System.out.println("null");
        return;
    }
    System.out.print(head.getData() + "->");
    printList(head.getNext());
}

public int size() {
    return size(first);
}

private static int size(Node head) {
    if (head == null) {
        return 0;
    } else {
        return 1 + size(head.getNext());
    }
}

public boolean contains(E data) {
    return contains(first, data);
}

public static <E> boolean contains(Node head, E data) {
    if (head == null || data == null) {
        return false;
    }
    if (head.getData().equals(data)) {
        return true;
    }
    return contains(head.getNext(), data);
}
 //count occurrences of certain value
public int countIf(E t) {
    return countIf(first, t);
}

private static <E> int countIf(Node head, E t) {
    if (head == null) {
        return 0;
    }
    if (head.getData().equals(t)) {
        return 1 + countIf(head.getNext(), t);
    }

    return countIf(head.getNext(), t);
}

//TODO: WHY IM GETTING HERE AN OVERRIDE REQUEST FROM THE COMPILER??
public ListNode<E> clone() {
    first = clone(first);
    ListNode<E> copy = new ListNode<>(first);
    return copy;
}

private static Node clone(Node head) {
    if (head == null) {
        return null;
    }

    Node temp = new Node(head.getData());
    temp.setNext(clone(head.getNext()));

    return temp;
}

public ListNode<E> invert() {
    first = invert(first);
    ListNode<E> inverted = new ListNode<>(first);
    return inverted;
}

private static Node invert(Node head) {

    if (head.getNext() == null) {
        return head;
    }

    Node newHead = invert(head.getNext());

    head.getNext().setNext(head);//head.next.next=node;
    head.setNext(null);//gead.next=null;

    return newHead;
}

问题 2我对这个话题的以下原始想法是什么？因此，作为初学者，我会尝试分享我对这种方式的潜在好处的观点，如果我弄错了，请尝试纠正我，如果我遗漏了什么，请指出!

• 首先，对于断言、contains() 和countIf()，这可能会有所帮助，因为主要是用户不会' 必须将列表的头部作为参数。因为每个方法都会像这样调用 list1.method() 因此每个列表都会有另一个 head node。
• 其次，在反转和克隆的情况下，我必须返回 ListNode 而不是 Node 我可以理解创建列表必须在 invert() 或 clone() 方法中。

遗憾的是，我在网上找不到足够的信息，请随时提供您最喜欢的引用资料，并随时写下您自己的解释。

祝你好运。 :)

Answer 1

QUESTION: What benefit can this way of writing method bring to the implementation of a certain collection?

好处:有效。这是可行的。

还有什么选择？一种方法？那会是两者中的哪一个？

• 无效插入(E 数据)？那么递归是怎么实现的呢？

• 节点插入(节点头，E数据)？调用者从哪里获得 head 值？调用者将如何处理返回值？

再看看你所有的方法对。你看到一个模式吗？比如，所有私有(private)方法都有一个 Node 参数。所有公共(public)方法都不会。