LinkedList小抄

public class LinkedList {
    // 双向链表实现，无容量限制，但每个元素都要构造Node对象，使用了更多空间
    transient Node<E> first;
    transient Node<E> last;
    
    // 通过下标寻找元素，是从头遍历的
    // 所以get(index) 和 set(index, element)效率低
    // 总而言之，凡是带有index查找逻辑的方法，都需要遍历
    // 相比ArrayList，免去了复制移动的操作
    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;
        }
    }
    
    // 插入元素到链表头
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode; // 整个链表的first指向新元素
        if (f == null)
            last = newNode;
        else
            f.prev = newNode; //原来的头结点prev指向新元素
        size++;
        modCount++;
    }
    
    // 插入元素到链表末尾，不用遍历，效率高
    void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode; // 整个链表的last指针指向新元素
        if (l == null)
            first = newNode;
        else
            l.next = newNode; // 原来的last节点next指向新元素
        size++; // 增加链表长度
        modCount++;
    }

    // 删除头元素
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // help GC
        first = next;  // 链表的头指针指向元素的next节点
        if (next == null)
            last = null;
        else
            next.prev = null;  // 元素的next节点的prev置null
        size--;
        modCount++;
        return element;
    }

    // 删除尾元素
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        final E element = l.item;
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;  // 链表的last指向元素prev的节点
        if (prev == null)
            first = null;
        else
            prev.next = null;  // prev节点的next置null
        size--;
        modCount++;
        return element;
    }
}