Java集合3-LinkedList-结构

LinkedList的节点由Node类实现，它通常是一个私有内部类。Node类通常包含三个字段：item用于存储数据元素，prev用于指向前一个节点，next用于指向后一个节点。

LinkedList还包含指向链表头部和尾部的引用。这些引用使得在链表的开头和末尾进行操作更加高效。

LinkedList不支持通过索引直接访问元素。要访问特定位置的元素，必须从头节点或尾节点开始遍历列表，直到找到所需位置的元素。因此，索引访问的时间复杂度是O(n)，其中n是列表的长度。

查询方法

    public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }
    
    Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

上述代码，利用了双向链表的特性，如果index离链表头比较近，就从节点头部遍历。否则就从节点尾部开始遍历。使用空间（双向链表）来换取时间。

迭代器： LinkedList实现了java.util.List接口，因此支持使用迭代器进行遍历操作。迭代器在LinkedList中的实现是双向的，因此可以在任一方向上进行迭代，使得在列表中移动元素非常高效。

线程不安全： LinkedList的实现不是线程安全的，如果需要在多线程环境下使用，需要手动保证同步。