数据结构学习笔记：利用递归实现链表基本操作

利用递归实现链表基本操作，首先要来利用递归来认识链表。从下图可知，我们可以把链表看成一个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());
    }

其他操作在逻辑上是同理的，在此不再赘述，希望本文能帮助大家更好的理解递归。