Java 单链表

package linkedlist;

import java.util.NoSuchElementException;
import java.util.Stack;

/**
 * 单链表
 */
@SuppressWarnings("all")
public class SingleLinkedList {
    // 定义头结点，注意头结点只能指向链表头部，所有后续遍历和插入等操作，需要使用temp辅助完成
    private Node head = new Node(null, null);

    // 链表有效节点个数
    int size = 0;

    /**
     * 新增元素
     *
     * @param data 待添加的元素
     */
    public void add(E data) {
        Node temp = head;
        while (null != temp.next) {
            temp = temp.next;
        }

        Node newNode = new Node(data, null);
        temp.next = newNode;
        size++;
    }

    /**
     * 链表头插入新节点
     *
     * @param data
     */
    public void addFirst(E data) {
        Node newNode = new Node(data, head.next);
        head.next = newNode;
        size++;
    }

    /**
     * 链表尾部插入元素
     *
     * @param data
     */
    public void addLast(E data) {
        add(data);
    }

    /**
     * 获取列表中指定位置的元素
     *
     * @param index
     * @return
     */
    public E get(int index) {
        // 1.校验下标是否越界
        if (!checkIndex(index)) {
            throw new IndexOutOfBoundsException();
        }
        // 2.得到指定位置的元素
        Node temp = head.next;
        for (int i = 0; i ) {
            temp = temp.next;
        }
        return temp.data;
    }

    /**
     * 校验元素下标是否在合法范围内
     *
     * @param index
     * @return
     */
    private boolean checkIndex(int index) {
        if (index >= 0 && index  size) {
            return true;
        }
        return false;
    }

    /**
     * 获取指定元素在链表中的下标
     *
     * @param obj
     * @return -1：元素不在链表中 其他值：元素在链表中的下标
     */
    public int indexOf(Object obj) {
        Node temp = head.next;
        for (int i = 0; i ) {
            if (null != temp && obj.equals(temp.data)) {
                return i;
            }
            temp = temp.next;
        }
        return -1;
    }

    // 用指定元素替换列表中指定位置的元素
    public E set(int index, E data) {
        if (!checkIndex(index)) {
            throw new IndexOutOfBoundsException();
        }

        Node temp = head.next;
        for (int i = 0; i ) {
            temp = temp.next;
        }
        E oldData = temp.data;
        temp.data = data;
        return oldData;
    }


    /**
     * 从链表中移除第一次出现的指定元素
     *
     * @param obj 待移除元素
     * @return true：元素存在，移除成功；false：元素不存在，移除失败
     */
    public boolean remove(Object obj) {
        // temp指向的是待删除节点的上一个节点
        Node temp = head;
        while (null != temp.next) {
            if (obj.equals(temp.next.data)) {
                // 被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收
                temp.next = temp.next.next;
                size--;
                return true;
            }
            temp = temp.next;
        }
        return false;
    }

    /**
     * 移除并返回此链表中的第一个元素
     *
     * @return
     */
    public E removeFirst() {
        Node temp = head;
        if (null != temp.next) {
            E oldData = temp.next.data;
            size--;
            temp.next = temp.next.next;
            return oldData;
        }
        throw new NoSuchElementException();
    }

    /**
     * 移除并返回此链表的最后一个元素
     *
     * @return
     */
    public E removeLast() {
        Node temp = head;
        if (null == temp.next) {
            throw new NoSuchElementException();
        }
        while (null != temp.next.next) {
            temp = temp.next;
        }
        E oldData = temp.next.data;
        temp.next = null;
        size--;
        return oldData;
    }

    /**
     * 反转
     * 注意，链表的结构已被改变
     */
    public void reverse() {
        // 链表为空，或者只有一个元素，返回
        if (null == head.next || null == head.next.next) {
            return;
        }

        // 当前需要反转的节点
        Node temp = head.next;
        // 当前需要反转节点的下一个节点，此目的是为了断链后，能找到下一个待反转的节点
        Node tempNext = null;
        // 需要新头节点挂载后续节点
        Node reverseHeadNode = new Node(null, null);
        while (null != temp) {
            tempNext = temp.next;
            // 如果是第一个元素，reverseHeadNode.next = null，赋值后，第一个元素next=null，
            // 和原始链表断链了，故后面不需要特殊处理
            temp.next = reverseHeadNode.next;
            reverseHeadNode.next = temp;
            temp = tempNext;
        }
        head.next = reverseHeadNode.next;
    }

    public void reverseNotUserTempHead() {
        // 链表为空，或者只有一个元素，返回
        if (null == head.next || null == head.next.next) {
            return;
        }

        // 当前需要反转的节点
        Node temp = head.next;
        // 当前需要反转节点的下一个节点，此目的是为了断链后，能找到下一个待反转的节点
        Node tempNext = null;

        // 可以不用辅助头节点，断链后，用原来的头节点也可以完成反转
        head.next = null;
        while (null != temp) {
            tempNext = temp.next;
            // 如果是第一个元素，reverseHeadNode.next = null，赋值后，第一个元素next=null，
            // 和原始链表断链了，故后面不需要特殊处理
            temp.next = head.next;
            head.next = temp;
            temp = tempNext;
        }
    }

    /**
     * 反向打印单链表
     * 使用栈Stack实现
     */
    public void reversePrint() {
        Node temp = head.next;
        if (null == temp) {
            return;
        }
        Stack stack = new Stack();
        while (null != temp) {
            stack.push(temp.data);
            temp = temp.next;
        }

        while (stack.size() > 0) {
            System.out.println(stack.pop());
        }
    }

    /**
     * 遍历，打印元素
     */
    public void linkedListPrint() {
        Node temp = head.next;
        if (null == temp) {
            return;
        }
        while (null != temp) {
            System.out.println(temp.data);
            temp = temp.next;
        }
    }

}

class Node {
    E data;
    Node next;

    public Node(E data, Node next) {
        this.data = data;
        this.next = next;
    }
}