LinkedList源码解析一

基本属性

     transient int size = 0;// 存储数据量

    /**
     * Pointer to first node.
     */
    transient Node<E> first;// 指向第一个节点的指针

    /**
     * Pointer to last node.
     */
    transient Node<E> last;// 指向最后一个节点的指针。

数据单位

private static class Node<E> {
        E item;
        Node<E> next;// 下一个节点
        Node<E> prev;// 上一个节点

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

方法

LinkedList(Collection<? extends E> c) 构造方法

 public LinkedList(Collection<? extends E> c) {this();
        addAll(c);
    }

addAll(Collection<? extends E> c) 将指定集合中的所有元素追加到末尾

public boolean addAll(Collection<? extends E> c) {return addAll(size, c);
    }

addAll(int index, Collection<? extends E> c) 将指定集合中的所有元素，插入到指定索引处

 public boolean addAll(int index, Collection<? extends E> c) {checkPositionIndex(index);// 下标在范围内

        Object[] a = c.toArray();// 转化为对象数组
        int numNew = a.length;
        if (numNew == 0)
            return false;// 长度为 0 直接返回 false

        Node<E> pred, succ;
        if (index == size) {// 如果是尾插入
            succ = null;
            pred = last;// 上一个节点设置成 last
        } else {succ = node(index);// 获取指定索引的节点
            pred = succ.prev;// 指定索引的节点的前一个元素
        }

        for (Object o : a) {// 循环对象数组
            @SuppressWarnings("unchecked") E e = (E) o;
            Node<E> newNode = new Node<>(pred, e, null);// 构造方法（前一个节点，当前节点，下一个节点）if (pred == null)
                first = newNode;// 上一个节点为空，那么头结点等于新的节点
            else
                pred.next = newNode;// 上一个节点不为空，上一个节点的下一节点为创建的节点
                
            pred = newNode;// 上一个节点等于当前节点
        }

        if (succ == null) {last = pred;} else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }

node(int index) 返回指定元素索引处的（非 null）节点

Node<E> node(int index) {// assert isElementIndex(index);

        if (index < (size >> 1)) {// 小于一半
            Node<E> x = first;
            for (int i = 0; i < index; i++)// 从 0 往后循环到 index
                x = x.next;
            return x;
        } else {// 大于一半
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)// 从 size 往前循环到 index
                x = x.prev;
            return x;
        }
    }