/**
 * 单向链表实现类
 * @Description
 * 类描述：
 * @author GaoAnQiu
 * @Date 
 * @modify
 * 修改记录：
 *
 */
public class Link {

    private int size = 0;
    private Node first;
    private Node last;

    public Node getFirst() {
        return first;
    }

    public void setFirst(Node first) {
        this.first = first;
    }

    public Node getLast() {
        return last;
    }

    public void setLast(Node last) {
        this.last = last;
    }

    public Link() {

    }

    /**
     * 返回链表长度
     * @Description
     * 方法描述:
     * @return 返回类型： int
     * @return
     */
    public int getLength() {
        return size;
    }

    public void printLink(Link link) {
        Node temp = first;
        while (temp != null) {
            System.out.print(temp.getData() + "-->");
            temp = temp.getNext();
        }
        System.out.println();
    }

    /**
     * 返回指定位置的节点
     * @Description
     * 方法描述:
     * @return 返回类型： Node
     * @param index
     * @return
     */
    public Node get(int index) {
        Node temp = first;
        for (int i = 0; i < index; i++) {
            temp = temp.getNext();
        }
        return temp;
    }

    /**
     * 插入第一个元素，头和尾都指向同一个元素
     * @Description
     * 方法描述:
     * @return 返回类型： void
     */
    private void onetNode(int element) {
        first = new Node();
        first.setData(element);
        last = first;
    }

    public void addHead(int element) {
        if (size == 0) {
            onetNode(element);
        } else {
            Node node = new Node();
            node.setData(element);
            node.setNext(first);
            first = node;
        }
        size++;
    }

    /**
     * 插入尾结点
     * @Description
     * 方法描述:
     * @return 返回类型： void
     * @param element
     */
    public void addTail(int element) {
        if (size == 0) {
            onetNode(element);
        } else {
            Node node = new Node();
            node.setData(element);
            last.setNext(node);
            last = node; //将插入的结点设置为尾结点
            size++;
        }
    }

    /**
     * 插入中间元素
     * 头尾两处需要特殊处理
     * @Description
     * 方法描述:
     * @return 返回类型： void
     * @param index
     * @param element
     */
    public void add(int index, int element) {
        if (index > size) {
            throw new IndexOutOfBoundsException("待插入的位置超过链表的最大长度。");
        } else {
            if (index == 0) {
                //下标为0时，插入头元素
                addHead(element);
            } else if (size == index) {
                //下标与链表长度一致时，插入尾元素
                addTail(element);
            } else {
                Node preNode = get(index - 1); //
                Node nextNode = get(index);
                Node newNode = new Node();
                newNode.setData(element);
                preNode.setNext(newNode);
                newNode.setNext(nextNode);
                size++;
            }
        }
    }

    /**
     * 删除头节点
     * @Description
     * 方法描述:
     * @return 返回类型： void
     */
    public void delHead() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("空链表，无元素可删除");
        } else {
            if (size == 1) {
                //只有一个节点时，清空链表
                clear();
            } else {
                Node nextNode = first.getNext();
                first = nextNode;
            }
            size--;
        }
    }

    /**
     * 清空链表
     * @Description
     * 方法描述:
     * @return 返回类型： void
     */
    public void clear() {
        first = last = null;
        size = 0;
    }

    public void delTail() {
        if (size == 0) {
            throw new IndexOutOfBoundsException("空链表，无可删除的元素。");
        } else if (size == 1) {
            clear();
        } else {
            //取出尾节点的前一个节点，next赋值为null
            Node preTail = get(size - 2);
            preTail.setNext(null);
            last = preTail;
            size--;
        }
    }

    /**
     * 删除节点
     * @Description
     * 方法描述:
     * @return 返回类型： void
     * @param index
     */
    public void del(int index) {
        if (index >= size) {
            throw new IndexOutOfBoundsException("删除位置越界");
        } else {
            if (index == 0) {
                delHead();
            } else if (index == size - 1) {
                delTail();
            } else {
                Node preNode = get(index - 1);
                Node nextNode = get(index + 1);
                preNode.setNext(nextNode);
                size--;
            }
        }
    }

}

public class Node {

    private int data;//数据
    private Node next;//指针

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

}