日拱一卒：链表（LinkedList）

单向链表

• 单向链表包含两个值: 当前节点的值和一个指向下一个节点的链接

class LinkedList<T> implements Iterable<T> {
    private Node head;
    private int N;

    public LinkedList() {
        // 初始化头节点
        this.head = new Node(null, null);
        this.N = 0;
    }

    class Node {
        private T data;
        private Node next;

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

    public void clear() {
        // 将头节点与后面断开
        head.next = null;
        this.N = 0;
    }

    /**
     * head -> data -> data
     *   0  ->  1   ->  2
     */
    public Node get(int index) {
        Node node = head;
        for (int i = 0; i <= index; i++) {
            node = node.next;
        }
        return node;
    }

    public Node get(T data) {
        if (data == null) {
            return head;
        }
        Node node = head;
        while (node.next != null) {
            if (node.data == data) {
                return node;
            }
            node = node.next;
        }
        return null;
    }

    public void insert(T data) {
        // 1. 找最后一个节点
        Node node = head;
        while (node.next != null) {
            node = node.next;
        }

        // 2. 创建新节点，并加到最后
        Node end = new Node(data, null);
        node.next = end;
        N++;
    }

    /**
     * 指定 index 位置插入
     */
    public void insert(int index, T data) {
        // 1. 找出 index 的前一个节点
        Node pre = head;
        for (int i = 0; i < index; i++) {
            pre = pre.next;
        }

        // 2. index 位置的节点
        Node curr = pre.next;

        // 3. 新建一个Node, 插入 curr
        Node node = new Node(data, curr);
        pre.next = node;
    }

    public void insert(T current, T data) {
        Node curr = get(current);

        Node node = new Node(data, null);
        if (current == null) {
            // 头节点
            node.next = head.next;
            head.next = node;
        } else {
            node.next = curr.next;
            curr.next = node;
        }
        N++;
    }


    @Override
    public Iterator<T> iterator() {
        return new IteratorImpl();
    }

    private class IteratorImpl implements Iterator<T> {
        private Node node;
        public IteratorImpl() {
            this.node = head;
        }

        @Override
        public boolean hasNext() {
            return node.next != null;
        }

        @Override
        public T next() {
            node = node.next;
            return node.data;
        }
    }
}

双向链表

• 一个双向链表有三个整数值: 数值、向后的节点链接、向前的节点链接