数据结构—单向链表

概述：实现一个带头节点的单向链表
单向链表：
    所谓单向链表，指的是只能从头部往尾部遍历的链表。
    单向链表的每个节点有两个区域，一个用来存储数据，另一个用来指向下一个节点。

实现：
 

public class LinkList<T> {
    /**
     * 节点类
     */
    private class Node<T> {
        T data;
        Node<T> next;

        public Node() {
        }

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

    private Node<T> head;
    private Node<T> tail;
    private int size;

    public LinkList() {
        head = new Node<T>();
        tail = head;
        size = 0;
    }

    /**
     * 在尾部添加一个元素
     */
    public boolean add(T data) {
        Node<T> temp = new Node<T>(data);
        tail.next = temp;
        tail = temp;
        size++;
        return true;
    }

    /**
     * 从尾部移除一个元素
     */
    public boolean remove() {
        if (size == 0) {
            return true;
        }
        Node<T> node = head;
        int index = size - 1;
        while (index > 0) {
            node = node.next;
            index--;
        }
        tail = node;
        node.next = null;
        size--;
        return true;
    }

    /**
     * 删除指定位置的元素
     */
    public boolean delete(int index) {
        isCrossing(index);
        if (index == size - 1) {
            remove();
        } else {
            Node<T> node = head;
            while (index > 0) {
                node = node.next;
                index--;
            }
            node.next = node.next.next;
            size--;
        }
        return true;
    }

    /**
     * 在指定位置插入一个元素
     */
    public boolean insert(int index, T data) {
        // 这里先判断，是为了可以在链表末尾插入数据
        isCrossing(index == 0 ? 0 : index - 1);
        if (index == size) {
            add(data);
        } else {
            Node<T> temp = new Node<T>(data);
            Node<T> node = head;
            while (index > 0) {
                node = node.next;
                index--;
            }
            temp.next = node.next;
            node.next = temp;
            size++;
        }
        return true;
    }

    /**
     * 更改指定位置的元素
     */
    public boolean modify(int index, T data) {
        isCrossing(index);
        Node<T> node = head;
        while (index > 0) {
            node = node.next;
            index--;
        }
        node = node.next;
        node.data = data;
        return true;
    }

    /**
     * 获取指定位置的元素
     */
    public T get(int index) {
        isCrossing(index);
        Node<T> node = head;
        while (index > 0) {
            node = node.next;
            index--;
        }
        return node.next.data;
    }

    /**
     * 获取链表长度
     */
    public int getSize() {
        return size;
    }

    /**
     * 将当前链表逆序
     */
    public void reverse() {
        if (size == 0) {
            return;
        }
        Node<T> dest = null;
        Node<T> now = null;
        // 用于记录头节点，因为该链表带头节点，所以头节点是不变的
        Node<T> first = head;
        head = head.next;
        tail = head.next;
        while (head != null) {
            now = head;
            head = head.next;
            now.next = dest;
            dest = now;
        }
        first.next = dest;
        head = first;
    }

    /**
     * 校验下标是否越界
     * 
     * @param index
     *            下标
     */
    private void isCrossing(int index) {
        if (!(index >= 0 && index < size)) {
            throw new IndexOutOfBoundsException();
        }
    }
}