链表（单向链表，双向链表）

class SingleNode {
    public Object object; //节点数据
    public SingleNode next; //指向下一个节点

    public SingleNode() {

    }

    public SingleNode(Object object, SingleNode next) {
        this.object = object;
        this.next = next;

    }
}

/**
 * 单链表的实现
 */
public class SingleLinkList {
    private SingleNode first; //定义头结点
    private SingleNode last;  //定义尾节点
    private int size;   //定义链表的节点数

    /**
     * 判断链表是否为空
     * @return
     */
    public boolean isEmpty() {
        return first == null;
    }

    /**
     * 在链表的头部和尾部添加元素
     * 思路分析：当链表为空时，就相当于在链表的头部添加数据，所以把新添加的节点赋值给头结点（尾节点）,
     * 当链表不为空时，就相当于于在链表的尾部添加数据，这时候我们就是把尾部的指针指向新添加的节点（即last.next=node）,然后把新添加的节点赋值到
     * 最后节点 （即last=node）         
     */
    public void add(Object object) {
        SingleNode node = new SingleNode(object, null);
        if (isEmpty()) {
            first = node;
        } else {
            last.next = node;
        }
        last = node;
        size++;

    }

    /**
     * 在指定的节点增加元素
     * 思路分析：首先我们需要判断添加的位置是否满足条件（index>0 && index<size）,然后我们需要找到指定索引位置的元素和它的上一个位置的元素，所以用到
     * 两个指针来记录索引位置的元素和它上一个位置的元素，最后把 (before.next=node,node.next=temp)，这就相当于把before指向node,node指向当前节点（temp）即可。
     * @param index
     * @param object
     */
    public void addElement(int index, Object object) {
        SingleNode node = new SingleNode(object, null);
        if (index > 0 && index < size) {
            SingleNode temp = first;
            SingleNode before = null;
            for (int i = 0; i < index; i++) {
                before = temp;
                temp = temp.next;
            }
            before.next = node;
            node.next = temp;
            size++;
        }
    }

    /**
     * 展示链表中的节点元素
     */
    public void show() {
        if (!isEmpty()) {
            SingleNode current = first;
            while (current != null) {
                System.out.println(current.object);
                current = current.next;
            }
        }

    }

    /**
     * 获得指定节点的元素
     * 思路分析：定义一个指针，循环到指定位置，把元素取出即可
     * @param index
     * @return
     */
    public Object get(int index) {
        if (index > 0 && index < size) {
            if (!isEmpty()) {
                SingleNode temp = first;
                for (int i = 0; i < index; i++) {
                    temp = temp.next;
                }
                return temp.object;
            }
        }
        return null;
    }

    /**
     * 删除指定节点的元素
     * 思路分析：需要定义两个指针来记录要删除的节点和要删除节点的上一个节点，然后 把before.next=temp.next即可。
     * @param index
     */
    public void remove(int index) {
        if (index > 0 && index < size) {
            if (!isEmpty()) {
                SingleNode temp = first;
                SingleNode beforeTemp = null;
                for (int i = 0; i < index; i++) {
                    beforeTemp = temp;
                    temp = temp.next;
                }
                beforeTemp.next = temp.next;
            }
        }

    }

    /**
     * 修改指定节点的指定元素
     *
     * @param index
     * @param object
     */
    public void update(int index, Object object) {
        if (index > 0 && index < size) {
            if (!isEmpty()) {
                SingleNode temp = first;
                for (int i = 0; i < index; i++) {
                    temp = temp.next;
                }
                temp.object = object;
            }
        }
    }

    /**
     * 实现链表的反向打印
     * 思路分析：利用栈先进后出的特点，首先把元素放到栈中，然后再取出，即可。
     */
    public void rePrint() {
        Stack<SingleNode> stack = new Stack<SingleNode>();
        if (!isEmpty()) {
            SingleNode current = first;
            while (current != null) {
                stack.push(current);
                current = current.next;
            }
            while (stack.size() > 0) {
                System.out.println(stack.pop().object);
            }
        }
    }

    /**
     *  将单链表反转
     */
    public void reversetList() {
        SingleNode current = first;
        SingleNode before = null;
        while (current != null) {
            last = before;
            before = current;
            current = current.next;
            before.next = last;
        }
        current = before;
        while (current != null) {
            System.out.println(current.object);
            current = current.next;
        }

    }