1. 单链表

public class Node<T> {
    T data;
    Node next;

    public Node(T data) {
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
                "data=" + data +
                '}';
    }
}

public class SingleList<T> {
    private Node head = null;
    private int size;

    /**添加至头结点**/
    public void addToHead(T data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            size++;
            return;
        }
        //新节点的next指向原头节点
        newNode.next = head;
        //新节点成为头结点
        head = newNode;
        size++;
    }

    /**添加至尾结点**/
    public void addToTail(T data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            size++;
            return;
        }

        Node temp = head;
        //找到最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
        size++;
    }

    /**添加指定位置结点**/
    public void addToIndex(T data, int index) {
        if (index < 0 || index > size) {
            throw new InvalidParameterException("invalid index!");
        }

        if (index == 0) {
            addToHead(data);
        } else if (index == size) {
            addToTail(data);
        } else {
            Node newNode = new Node(data);
            int i = 0;
            Node preNode = head;
            //获取插入位置的前一个节点
            while (i < index - 1) {
                preNode = preNode.next;
                i++;
            }

            Node nextNode = preNode.next;
            preNode.next = newNode;
            newNode.next = nextNode;
            size++;
        }
    }

    /**删除指定节点**/
    public void deleteAtIndex(int index) {
        if (index < 0 || index > size - 1) {
            throw new InvalidParameterException("invalid index!");
        }
        if (size == 0) {
            return;
        }
        if (size == 1) {
            head = null;
            size = 0;
            return;
        }

        if (index == 0) {
            head = head.next;
            size--;
            return;
        } else {
            Node preNode = head;
            int i = 0;
            //获取删除位置的前一个节点
            while (i < index - 1) {
                preNode = preNode.next;
                i++;
            }
            Node deleteNode = preNode.next;
            Node nextNode = deleteNode.next;
            preNode.next = nextNode;
            //断开删除节点的连接
            deleteNode.next = null;
            size --;
        }
    }

    /**
     * 反转链表
     * 思路-遍历节点，当前节点的next指向前一个节点, 遍历时用临时变量记录下一个节点，然后当前节点和前一个节点依次后移。
     * */
    public void reverse() {
        if (size <= 1) {
            return;
        }
        Node cur = head;
        Node pre = null;
        Node next = null;
        while (cur != null) {
            //记录下一个节点
            next = cur.next;
            //当前节点的next指向前一个节点
            cur.next = pre;

            //pre cur继续后移
            pre = cur;
            cur = next;
        }

        head = pre;
    }

    public void print() {
        Node temp = head;
        while (temp != null) {
            System.out.println(temp.toString());
            temp = temp.next;
        }
    }

    public int size() {
        return this.size;
    }
}