[数据结构与算法]Java实现单链表

public class ListNode {

    /**
     * 头结点
     */
    Node head;

    /**
     * 末尾结点
     */
    Node end;

    /**
     * 已经加入结点的数量
     */
    int elementSize;

    /**
     * 构造器，传入值
     *
     * @param val
     */
    public ListNode(int val) {
        this.head = new Node(null, val);
        this.elementSize++;
    }

    /**
     * 正常追加至末尾
     *
     * @param val
     */
    public void add(int val) {
        Node node = new Node(null, val);
        // 如果为null，说明还没有元素增加过
        if (end == null) {
            // 头结点后面就是新增的元素
            head.next = node;
        } else {
            end.next = node;
        }

        end = node;
        elementSize++;
    }

    /**
     * 追加到具体某个位置
     *
     * @param index
     * @param val
     */
    public void addIndex(int index, int val) {
        if (index < 0) {
            throw new IndexOutOfBoundsException("" + index);
        }

        // 如果大于当前的size就直接放到最后就可以
        if (index > elementSize) {
            add(val);
        } else {
            // 当前节点
            Node cur = head;
            // 前一个节点
            Node pre = null;
            int i = 0;
            while (i != index) {
                pre = cur;
                cur = cur.next;
                i++;
            }

            if (pre == null) {
                Node node = new Node(head, val);
                head = node;
            } else {
                Node node = new Node(cur, val);
                pre.next = node;
            }

            elementSize++;
        }
    }

    /**
     * 根据下标获取值
     *
     * @param index
     * @return
     */
    public Integer get(int index) {
        if (index < 0 || index > elementSize - 1) {
            throw new IndexOutOfBoundsException("" + index);
        }

        // 当前节点
        Node cur = head;
        int i = 0;
        while (i != index) {
            cur = cur.next;
            i++;
        }

        if (cur == null) {
            return null;
        }

        return cur.val;
    }

    /**
     * 根据值移除元素
     *
     * @param val
     */
    public void remove(int val) {
        Node cur = head;
        Node pre = null;
        while (cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }

        if (pre == null) {
            head = cur.next;
            elementSize--;
        }

        if (cur != null) {
            pre.next = cur.next;
        }
    }

    public static void main(String[] args) {
        ListNode listNode = new ListNode(1);
        listNode.add(2);
        listNode.add(3);
        listNode.add(4);
        listNode.add(5);
        listNode.add(6);
        listNode.addIndex(5, 7);
        System.out.println(listNode.get(3));
        listNode.remove(2);
    }
}

class Node {
    Node next;
    int val;

    public Node(Node next, int val) {
        this.next = next;
        this.val = val;
    }
}