一、什么是链表

一种常见的数据存储结构，是一种线性表，但是不会按照线性的顺序存储数据，而是每一个节点存储下一个节点的指针。

二、什么是递归算法

在链表的数据结构中，我们经常会使用到递归算法。

递归算法

是一种直接或者间接调用算法的过程，其特点有

1. 描述简洁，便于理解。
2. 必须要有出口，否则就是死循环。
3. 递归内存消耗大，容易发生内存溢出。
4. 层级调用越多， 越危险。

下列为用递归算法实现的阶乘

public static long factorial(long num){
          if(num == 1)return 1;
          return num*factorial(num - 1);
}

三、如何手写实现链表

链表结构如图所示

屏幕快照 2019-10-26 下午10.59.46.png

每一个链表都是由节点构成的，我们要先定义节点的数据结构。

private class Node{
        // 节点存储的数据
        private int data;
        // 把当前自己的类型当作属性
        private Node next, head;
        // 有参的构造方法
        public Node(int data){
            this.data = data;
        }
        // 设置数据
        public void setData(int data){
            this.data = data;
        }
        // 获取数据
        public int getData(){
            return data;
        }
}

为了减少代码量，我们采用内部类的形式，直接将节点类定义在链表类之中，并且采取尾插法的方式来建立链表。

增加节点代码如下:

public void addTailNode(int data){
            // 后面为空直接添加
            if (this.next == null){
                this.next = new Node(data);
            }else {
                // 递归操作
                this.next.addTailNode(data);
            }
}

删除节点代码如下:

public void deleteNode(int data){
            // 如果该节点后面不为空
            if (this.next != null){
                // 如果数据域相等
                if (this.next.data == data){
                    // 隔空相连
                    this.next = this.next.next;
                }else {
                    // 递归操作
                    this.next.deleteNode(data);
                }
            }
 }

向前添加节点代码如下:

public boolean insetFrontNode(int index, int data){
            if (this.next != null){
                // 进入下一个节点
                currentIndex += 1;
                if (currentIndex == index){
                    // 新建一个节点
                    Node node = new Node(data);
                    // 新节点的下一个节点为原来节点的下一个节点
                    node.next = this.next;
                    // 原节点的下一个节点为新节点
                    this.next = node;
                    return true;
                }else {
                    return this.next.insetFrontNode(index, data);
                }
            }else {
                // 如果为空则到达链表末尾 直接添加元素
                this.addTailNode(data);
                return true;
            }
 }

具体代码可参考:
https://github.com/JacksonMike/Java_ultimate/blob/master/LinkedListDemo.java

四、链表的特点和适用场景

1. 链表和数组都属于线性结构。
2. 链表适合插入和删除。
3. 但是查找元素时需要遍历，不支持随机查找，不宜过长，否则会导致性能降低。
4. 链表可以实现栈或者队列等数据结构。