java - 递归插入到双向链表的末尾

Question

我有一个双向链表，我想递归地在列表末尾插入一个元素。我现在有一个无需递归即可完成此操作的方法，并且它有效。我似乎无法理解如何用递归来做到这一点。我认为用递归在单链表的末尾插入是很容易理解的，所以我希望有人能解释当列表是双向链表时如何做到这一点。这是我想要递归的正常插入方法:

public void insert(T element) {
    Node in = new Node(element);

    if (in == null) {
        first = in;
    } else {
        Node tmp = first;
        while (tmp.next != null) {
            tmp = tmp.next;
        }
        tmp.next = in;
        in.prec = tmp;
    }
}

Answer 1

这个想法只是用函数调用重写 while 循环:

public void insert(T element) {
    insert(element, first);    // initialization
}

private void insert(T e, Node n) {
    if(n == null) {            // if the list is empty
        first = new Node(e);
    } else if(n.next == null) {       // same condition as in the while loop
        None newNode = new Node(e);
        n.next = newNode;
        newNode.prec = n;
    } else {
        insert(e, n.next);    // looping
    }
}