基本概念

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中指针链接次序实现的。和数组相比较，链表不需要指定大小，也不需要连续的地址。
单链表的基本设计思维是，利用结构体的设置，额外开辟一个空间去做指针，指向下一个结点。

其中，DATA是需要存储的数据元素，可以为任何数据格式，可以是数组，可以是int，还可以是结构体。
NEXT作为一个空指针，其代表了一个可以指向的区域，通常是用来指向下一个结点，链表尾部NEXT指向NULL（空），因为尾部没有任何可以指向的空间了。

创建结点

private static class Node<E> {
    private E item; 
    private Node<E> next;
    Node(E element,Node<E> next){
        item = element;
        this.next = next;
    }
}

创建接口

```java
public interface BaseTab<T> {
    /**
     * 空置链表
     */
    public void clear();
    /**
     * 判断链表是否为空
     * @return true 为空
     */
    public boolean isEmpty();

    //获取链表中的元素个数
    public int length();

    //获取并返回线性表中的第i个元素
    public T get(int i);

    //添加一个元素
    public void insert(T t);

    //向第i个元素之前插入一个元素
    public void insert(int i,T t);

    //删除并返回第i个元素
    public T remove(int i);
    //返回指定元素的序号，若不存在返回-1
    public int indexOf(T t);
}

实现全部功能

public class SingleLinkedList<E> implements BaseTab<E>{
    private Node<E> mHeader; //链表头部结点,头部结点不存储数据，只存储next
    private int size = 0; //记录链表长度

    public SingleLinkedList(){
    }

    @Override
    public void clear() {
        mHeader.next = null;
        size = 0;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public int length() {
        return size;
    }

    @Override
    public E get(int index) {
        Node<E> node = mHeader;//从Header开始循环
        for(int i = 0;i < index;i++){
            node = node.next;
        }
        return node.item;
    }

    @Override
    public void insert(E data) {
        if(mHeader == null){
            mHeader = new Node<E>(data,null);
            size++;
            return;
        }
        Node<E> lastNode = mHeader;
        while (lastNode.next != null){ //通过循环找到链表的尾部
            lastNode = lastNode.next;
        }
        lastNode.next = new Node<>(data,null);
        size++;
    }

    @Override
    public void insert(int index, E data) {
        //创建新的结点用来存放数据
        if(mHeader == null){
            mHeader = new Node<E>(data,null);
            size++;
            return;
        }

        Node<E> newNode = new Node<E>(data,null);
        Node<E> preNode = mHeader;
        for(int i = 0;i <= index -1;i++){ //循环找到index位置的前一个结点
            preNode = mHeader.next;
        }
        newNode.next = preNode.next;
        preNode.next = newNode;
        size++;
    }

    /**
     * 打印出链表所有数据
     */
    public void printAll(){
        Node<E> node = mHeader;
        while (node.next != null){
            System.out.println(node.item);
            node = node.next;
        }
        System.out.println(node.item);
    }

    @Override
    public E remove(int index) {
        //1.找到指定位置的前一个Node
        Node<E> preNode = mHeader;
        for(int i = 0; i < index -1;i++){
            preNode = preNode.next;
        }
        //需要被删除的Node
        Node<E> removeNode = preNode.next;
        preNode.next = removeNode.next;
        size--;
        return removeNode.item;
    }

    @Override
    public int indexOf(E data) {
        Node node = mHeader;
        for(int i = 0;i < size;i++){
            if(node.item.equals(data)){
               return i;
            } else {
                node = node.next;
            }
        }
        return -1;
    }

    private static class Node<E> {
        private E item;
        private Node<E> next;
        Node(E element,Node<E> next){
            item = element;
            this.next = next;
        }
    }
}

反转链表

链表反转是一道比较常见的面试题
eg：链表中输入0，1，2，3，4，输出 4，3，2，1，0

实现一个结点：

public class Node<T> {
    T data; //数据
    Node<T> next; //指向下一个结点
    public Node(T value){
        data = value;
    }
}

从结点的结构上面来说，我们需要修改的是next，将next由指向下一个改成指向上一个。
链表全部反转，那就需要从尾部或者头部开始，从尾部开始的话，使用递归的思想。

    public static <T> Node<T> reversalLink(Node<T> head){
        //主要是通过head.next == null 找出最后面的一个结点
        if(head == null || head.next == null) return head;
        //通过递归找到最后的一个作为Head
        //递归执行顺序是4，3，2，1，0
        Node<T> revHead = reversalLink(head.next);
        //调整指针
        //eg:执行到3时需要做以下操作
        //1.4的next应该是3，当head = 3时， 目前head.next = 4 4.next = head，就将4的下一个结点指向3
        head.next.next = head;
        //执行上上一步后，3->4,4->3,现在需要将3->4断开
        head.next = null;
        return revHead;
    }

    public static void main(String[] args) {
        Node<Integer> head = new Node<>(0);
        Node<Integer> node1 = new Node<>(1);
        Node<Integer> node2 = new Node<>(2);
        Node<Integer> node3 = new Node<>(3);
        Node<Integer> node4 = new Node<>(4);
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        //反转前
        Node<Integer> node = head;
        while (node != null){
            System.out.print(node.data + " ");
            node = node.next;
        }
        System.out.println("");
        System.out.println("-----反转后-------");
        Node<Integer> revHead = reversalLink(head);
        while (revHead != null){
            System.out.print(revHead.data + " ");
            revHead = revHead.next;
        }
    }

从链表头部开始

思路就如上面所画，从header开始，拆成两个链表

    public static <T> Node<T> reversalLink1(Node<T> head){
        Node<T> preNode = null;
        Node<T> curNode = head;
        while (curNode != null){
            Node<T> nextNode = curNode.next;

            curNode.next = preNode;
            preNode = curNode;
            curNode = nextNode;
        }
        return preNode;
    }