集合中的递归方法

Question

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

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

例如，假设我们正在通过链表实现一个通用优先级队列（LN 将值存储为一个对象），使用一个 front 实例变量和一个 priorityComparator 实例变量。我们将使用以下一对方法在此 class 中实现 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我对这个话题的以下原始想法是什么？因此，作为初学者，我会尝试分享我对这种方式的潜在好处的看法，如果我弄错了，请尝试纠正我，如果我遗漏了什么，请指出！

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

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

玩得开心。 :)

Answer 1

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

好处：有效。可行。

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

void insert(E data)？那么递归如何工作？
Node insert(Node head, E data)？调用者从哪里获得 head 值？调用者将如何处理 return 值？

再看看你所有的方法对。你看到一个模式吗？比如，所有私有方法都有一个 Node 参数。 None 的 public 方法可以。

集合中的递归方法

Recursive Methods in Collections

java

recursion

implementation

linked-list