LinkedList源码分析

概览

1
2
3

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

值得注意的时LinkedList除了实现了List还实现了Deque.也就是说LinkedList也可以当作队列来使用。LinkedList的底层是基于双向链表来实现的。所以它不支持随机访问，但也正是因为采用了双向链表实现，所以它有很高的插入和删除效率。

属性分析

1	transient int size = 0;

size记录了链表中有效元素的个数。

1 2	transient Node<E> first; transient Node<E> last;

双向链表的头指针和尾指针。这里有一个需要注意的地方，他们都使用了transient修饰，也就是说，他们不会被序列化。那么反序列化的时候怎么知道链表头和链表尾呢？其实在序列化的时候，只将链表本身和size进行了序列化，在反序列化的时候，首先获得size的值（此时firse和last为null），然后再将Node一个个读取出来，使用linkLast(E e)重构整个链表。而在这个方法中完成了first和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;
        }
    }

其实这个内部类对于学过数据结构的人来说一点也不会陌生。如果Node是头结点。那么prev==null。如果Node是尾节点，那么next==null&&prev!=null。

重要方法分析

1.add

public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

add方法的实现也是比较简单，首先记录last的旧值，然后为新结点分配空间，因为新结点是接在链表最后的，所以新结点成为了新的尾节点。再这里还会判断一次旧的last的值是否为null。如果为空，说明这个链表还从未添加过结点，所以在这之前first和last的值都为空，本次add已经给last赋值了，现在也同样应该给first赋值，因为当前只有一个结点，所以first和last都指向同一个结点。完成链表的增添后，完成size++,并将modCount++表示List的结构又改变了一次了。

2.体现双向链表小技巧的一个方法

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的结点并返回。这个方法首先会判断这个结点是前半段链表还是后半段链表。如果是前半段，就从头结点开始遍历，否者从后半段开始遍历。这种写法充分利用了双向链表的优势。

3.remove操作

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

//检查index的正确性
private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

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

    x.item = null;
    size--;
    modCount++;
    return element;
}

首先检查index的正确性。如果正确则调用 unlink(Node<E> x)移除结点。在删除的时候要注意判断删除的结点是否是头结点或者是尾节点。删除操作还是比较简单的。

4.addAll操作

public boolean addAll(int index, Collection<? extends E> c) {
        checkPositionIndex(index);

        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = 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;
    }

首先还是检查index的合法性。接下来将待插入的集合转换为了数组。然后依次插入。那么问题来了。为什么要先转换为数组呢？为什么不直接一个个取出来然后一个个插入呢？对于这个问题我也查了一些资料，感觉从多线程的角度解释比较好。如何直接遍历待插入的集合的话，那么就会一直占用这个集合，如果正确的同步话，其它线程将会一直等待。如果先转为数组，只需要遍历集合。而遍历集合过程中不需要额外的操作，所以占用的时间相对较短，利于减少其它线程的等待时间。