利用递归实现链表基本操作，首先要来利用递归来认识链表。从下图可知，我们可以把链表看成一个head和后面一个更短的链表，而这个链表之中又可以分出一个head和更加短的链表，以此类推，直到最后一个链表为 NULL 为止。
链表原理
我们先建立一个链表。
public class LinkedList<E> {
private Node head;
private int size;
public LinkedList(){
head=null;
size=0;
}
public int getSize(){
return size;
}
private class Node{
public E e;
public Node next;
public Node(E e,Node next){
this.e=e;
this.next=next;
}
public Node(E e){
this(e,null);
}
public Node(){
this(null,null);
}
@Override
public String toString(){
return e.toString();
}
}
}
之后，我们来探索添加操作如何实现。
所谓递归，就是把复杂问题转化为规模较小的简单问题。根据上文，我们探索出添加操作实际上是对一个个更小的链表的头进行处理。我制作了如下图助于读者理解。
添加操作原理
接下来我们来使用代码来实现。
首先构造一个递归基本操作方法。
public void add(int index,E e){
if (index <0 ||index > size)
throw new IllegalArgumentException("ADD FAILED.");
head=add(head,index,e);
size ++;
}
从head节点开始，一层层进行递归。
public Node add(Node node,int index,E e){
if(index == 0)
return new Node(e, node);
node.next = add(node.next, index - 1, e);
return node;
}
我们从最后一层递归开始理解，当我们新建一个节点时，这个节点的next属性值为node，也就是指向index=0（实际上为2）这个位置。返回上层递归，index=1的位置的next又指向这个新建的节点，以此类推，我们的添加操作就完成了。最后不要忘记将size-1。
对于删除操作，由于我们需要返回两个元素，删除后的链表的头结点和删除的值。这时候我们需引入javafx.util.Pair包。
Java中Pair键值对的使用：
当一个函数返回两个值并且两个值都有重要意义时我们一般会用Map的key和value来表达，但是这样的话就需要两个键值对，用Map映射去做处理时，此时的key相当于value的一个描述或者引用，而具体的信息都保存在value中，我们可以通过key去获取对应的value。但是当key和value都保存具体信息时，我们就需要用到Pair对了。Pair对也是键值对的形式。
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
Pair<Node, E> res = remove(head, index);
size --;
head = res.getKey();
return res.getValue();
}
private Pair<Node, E> remove(Node node, int index){
if(index == 0)
return new Pair<>(node.next, node.e);
Pair<Node, E> res = remove(node.next, index - 1);
node.next = res.getKey();
return new Pair<>(node, res.getValue());
}
其他操作在逻辑上是同理的，在此不再赘述，希望本文能帮助大家更好的理解递归。
