实现单项链表

单项链表和数组的最大区别是，数组在内存中的空间是连续的，如果要开辟一个数组一定要先找到空间大小够用的连续空间。而链表则不同，他的各个节点通过引用指向确定关联关系。

必须要有的一个头节点，在链表中做的大量操作都需要依赖头节点。尾节点则没有next。

 

public class MonomialLinkedList<T> {

    // 头节点
    private Node first;

    // 元素个数
    private int size = 1;

    // 增加元素
    public void add(T t) {
        if (first == null) {
            first = new Node(t, null);
        } else {
            Node temp = first;
            while (true) {
                if (temp.next == null) {
                    temp.next = new Node(t, null);
                    size++;
                    break;
                }
                temp = temp.next;
            }
        }
    }

    // 返回元素个数
    public int size() {
        return size;
    }

    // 遍历链表
    public void show() {
        if (first == null) {
            throw new RuntimeException("链表为空");
        } else {
            Node temp = first;
            while (true) {
                System.out.println(temp);
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }

        }
    }

    // 根据下标获取节点
    public T get(int index) {
        if (first == null) {
            throw new RuntimeException("链表为空，没有对应节点");
        } else if (index >= size) {
            throw new RuntimeException("链表长度为：" + size + ",index为" + (size - 1));
        } else if (index < 0) {
            throw new RuntimeException("下标不能<0");
        } else {
            Node temp = first;
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            return temp.item;
        }
    }

    // 在指定位置插入
    public void add(int index, T t) {
        if (index > size) {
            throw new RuntimeException("链表长度为：" + size + ",index为" + size);
        } else if (index < 0) {
            throw new RuntimeException("下标不能<0");
        } else if (index == 0) {
            Node newNode = new Node(t, null);
            newNode.next = first;
            first = newNode;
        } else {
            Node temp = first;
            for (int i = 0; i < index - 1; i++) {
                temp = temp.next;
            }
            Node newNode = new Node(t, null);
            newNode.next = temp.next;
            temp.next = newNode;
        }
        size++;
    }

    // 更改指定位置的元素
    public void set(int index, T t) {
        if (index >= size) {
            throw new RuntimeException("链表长度为：" + size + ",index为" + (size - 1));
        } else if (index < 0) {
            throw new RuntimeException("下标不能<0");
        } else {
            Node temp = first;
            for (int i = 0; i < index; i++) {
                temp = temp.next;
            }
            temp.item = t;
        }
    }

    // 删除指定位置的元素
    public void remove(int index) {
        if (index >= size) {
            throw new RuntimeException("链表长度为：" + size + ",index为" + (size - 1));
        } else if (index < 0) {
            throw new RuntimeException("下标不能<0");
        } else if (index == 0) {
            first = first.next;
        } else {
            Node temp = first;
            for (int i = 0; i < index - 1; i++) {
                temp = temp.next;
            }
            temp.next = temp.next.next;
        }
        size--;
    }

    // 返回头节点
    public T getFirst() {
        return first.item;
    }

    // 从尾部获取 新浪面试题
    public T lastGet(int index) {
        if (index > size) {
            throw new RuntimeException("链表长度为：" + size + ",index为" + (size));
        } else if (index <= 0) {
            throw new RuntimeException("下标不能<0");
        }

        Node temp = first;
        // 计算输入下标正着数是第几个。例如size=3
        // index是1其实是获取最后一个，3-1=2 就获取下标为2的Node
        for (int i = 0; i < size - index; i++) {
            temp = temp.next;
        }
        return temp.item;
    }

    // 反转链表 腾讯面试题
    public void reverse() {
        if (size == 0 || size == 1) {
            return;
        }
        // 整体思路：创建一个新的节点当作头节点
        // 在循环中先临时保存下一个元素，用于下一次用。
        // 然后将头节点next给当前元素next
        // 将当前元素添加到头节点的next
        // 最后删除临时头节点，反转完成
        // 老的链表A B C
        // N
        // N A
        // N B A
        // N C B A
        Node reverseNode = new Node(null, null);
        Node temp = first;
        for (int i = 0; i < size; i++) {
            // 临时下一个Node
            Node t = temp.next;
            temp.next = reverseNode.next;
            reverseNode.next = temp;
            temp = t;
        }
        // 重置头节点
        first = reverseNode;
        // 删除临时头节点
        remove(0);
    }

    // 节点对象
    class Node {
        private T item;
        private Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node [item=" + item + "]";
        }

    }
}